Một phương pháp tính toán tương quan giữa xung nhịp máy và phép cộng hai số nguyên khi thực hiện trên phần cứng

Nghiªn cøu khoa häc c«ng nghÖ<br /> <br /> <br /> MéT PH¦¥NG PH¸P TÝNH TO¸N T¦¥NG QUAN<br /> GI÷A XUNG NHÞP M¸Y Vµ PHÐP CéNG HAI Sè<br /> NGUYªN KHI THùC HIÖN TR£N PHÇN CøNG<br /> LỀU ĐỨC TÂN*, HOÀNG VĂN QUÂN**, HOÀNG NGỌC MINH*<br /> Tóm tắt: Trong việc thực hiện các hệ mật mã khóa công khai, các phép tính<br /> toán số học trên các số nguyên lớn luôn là phép tính quan trọng và nặng nề<br /> nhất. Để đánh giá được mức độ tiêu tốn tài nguyên cũng như tốc độ thực hiện<br /> của các phép toán này, nội dung bài báo trình bày một phương pháp tính toán<br /> tính tương quan giữa xung nhịp máy và phép cộng hai số nguyên khi thực hiện<br /> trên phần cứng.<br /> Từ khóa: Phép cộng, Xung nhịp máy, ECC.<br /> 1. MỞ ĐẦU<br /> Khi thực hiện tính tổng hai số nguyên X, Y  [0, 2k) bằng mạch cộng m-bits thì<br /> số nhịp máy cần thiết để thực hiện phép cộng này, được ký hiệu là flops(X,Y), sẽ<br /> là một số xác định. Tuy nhiên nếu ký hiệu F(k) là số nhịp máy để thực hiện phép<br /> cộng hai số nguyên trong miền [0, 2k) thì đây sẽ là một đại lượng ngẫu nhiên [1,2].<br /> Bài báo này trình bày kết quả nghiên cứu về số nhịp máy trung bình được ký hiệu<br /> là AAF(k) để thực hiện phép cộng hai số nguyên trong miền [0, 2k) và đó cũng<br /> chính là giá trị kỳ vọng của đại lượng F(k). Mục 2 mô tả hoạt động của mạch cộng<br /> làm cơ sở cho việc xác định các giá trị flops(X,Y) cũng như phân phối xác suất của<br /> đại lượng F(k), trong mục này trình bày thêm cách tiếp cận và các công cụ được sử<br /> dụng để tìm các giá trị AAF(k). Mục 3 liệt kê các kết quả tính toán được về các giá<br /> trị AAF(k) và quan trọng nhất là thu được kết quả AAF(k) trình bày trong kết quả 1<br /> và đã được chứng minh trong mục 3.4.<br /> 2. MẠCH CỘNG HAI SỐ NGUYÊN<br /> VÀ PHÂN PHỐI XÁC SUẤT CỦA ĐẠI LƯỢNG F(k)<br /> 2.1. Hoạt động của mạch cộng m-bits và trạng thái các thanh ghi sau mỗi nhịp<br /> máy<br /> Mạch cộng bao gồm thanh ghi A được gọi là thanh ghi tổng (theo nghĩa giá trị<br /> tổng sẽ được lưu trong thanh ghi này khi mạch dừng hoạt động) còn C được gọi là<br /> thanh ghi điều kiển (mạch sẽ dừng khi tất cả các bít trong thanh ghi này bằng 0)<br /> [2]. Cho A và C là hai thanh ghi m-bits với m>k. Để tính tổng X+Y với X, Y <br /> [0, 2k), xâu m bít biểu diễn nhị phân của hạng tử thứ nhất đưa vào thanh ghi A còn<br /> của hạng tử thứ hai đưa vào thanh ghi C. Tức là nếu biểu diễn nhị phân của X và Y<br /> lần lượt là<br /> X = (xm1, ..., xk, xk1, ..., x1, x0)2 và (2.1)<br /> Y = (ym1, ..., yk, yk1, ..., y1, y0)2 (2.2)<br /> thì bít thứ i (i=0, ..., k) của các thanh ghi A và C tương ứng, ký hiệu là A[i] và C[i],<br /> là<br /> A[i] = xi và C[i] = yi. (2.3)<br /> <br /> <br /> <br /> <br /> T¹p chÝ Nghiªn cøu KH&CN qu©n sù, Sè 33, 10 - 2014 75<br />  Kỹ thuật điện tử & Khoa học máy tính<br /> <br /> Chú ý: Do X, Y  [0, 2k) nên trong vế phải của (2.1) và (2.2) ta luôn có xs = ys<br /> = 0 với mọi sk.<br /> Mỗi nhịp máy các giá trị ở bít thứ i của A và C được xử lý tại một khâu tương<br /> ứng, bit tổng (không nhớ) được đưa vào bít thứ i của A còn bit tràn được đưa vào<br /> bit thứ i+1 của C. Khi thanh ghi C có trị tất cả các bít bằng 0 thì giá trị X+Y có<br /> biểu diễn nhị phân chính là các bít tương ứng của thanh ghi A. Ký hiệu A', C' và<br /> A", C" là trạng thái của hai thanh ghi A và C trước và sau một nhịp máy nào đó thì<br /> C "[0]  0<br /> <br />  C "[i ]  A '[i  1]C '[i  1] (0  i  m ) (2.4)<br />  A "[i ]  A '[i ]  C '[i ] (0  i  m )<br /> <br /> 2.2. Phân phối xác suất của đại lượng F(k)<br /> Tính chất: F(k) là một đại lượng ngẫu nhiên nhận giá trị nguyên từ 0 đến k+1 có<br /> phân bố<br /> Prob(F(k)=f) = N(k, f ) (f=0, 1, ..., k+1). (2.5)<br /> 4k<br /> k<br /> trong đó, N(k,f) = #{(X,Y): X, Y  [0, 2 ) và flops(X,Y) = f}.<br /> Chứng minh: Với Y = 0 thì trạng thái của thanh ghi C có giá trị tất cả các bít bằng<br /> 0 vì vậy mạch dừng và điều này có nghĩa<br /> flops(X,0) = 0. (2.6)<br /> f1<br /> Với mọi f = 1, 2, ..., k+1; lấy X = 1 và Y = 2  1 thì trạng thái đầu tiên của C là<br /> có đúng f1 bít 1 từ các vị trí thấp nhất còn của A chỉ có đúng một bít 1 ở vị trí<br /> thấp nhất. Dễ dàng nhận ra rằng<br /> flops(1, 2f1  1) = f (f = 1, 2, ..., k+1). (2.7)<br /> k<br /> Bây giờ ta sẽ chứng tỏ với mọi X, Y  [0, 2 ) thì<br /> flops(X,Y)  k+1. (2.8)<br /> Thật vậy, từ X, Y < 2k nên X + Y < 2k+1 vì vậy trong suốt quá trình thực hiện<br /> của mạch cộng thanh ghi C có các bít 1 chỉ xuất hiện ở k+1 vị trí thấp nhất. Theo<br /> công thức (2.4) thì sau mỗi nhịp máy thì số bít thấp nhất bằng 0 của C sẽ tăng thêm<br /> 1 (do phép dịch trái 1 vị trí) cho nên nhiều nhất là k+1 nhịp thì C sẽ không còn bít<br /> 1 và đương nhiên phép cộng đã hoàn thành. Như vậy, các kết quả (2.6), (2.7) và<br /> (2.8) đã chứng minh tính đúng đắn của tính chất. Từ X, Y  [0, 2k) nên ta có 2k2k<br /> = 4k cặp (X,Y) khác nhau và từ định nghĩa của giá trị N(k,f) ta có ngay (2.5) và<br /> tính chất đã được chứng minh.<br /> 2.3. Cách tiếp cận và công cụ để tính giá trị AAF(k)<br /> Để tính AAF(k) có hai tiếp cận để thực hiện đó là tính đúng giá trị này trong<br /> trường hợp k0 nhỏ tùy ý thì<br />  1 M  =1 (2.10)<br /> lim Pr ob   xi  E ( X )   <br /> M   M i 1 <br /> Áp dụng cho X=F(k) ta có<br />  1 M  =1 (2.11)<br /> lim Pr ob   Fi ( k )  AAF ( k )   <br /> M   M i 1 <br /> M<br /> Từ (2.11) thì ta có thể lấy (1 / M ) Fi (k ) là giá trị gần đúng của AAF(k) và chứng<br /> i 1<br /> minh tương tự như cho công thức (2.9) ta có công thức tính gần đúng giá trị<br /> AAF(k)<br /> AAF(k)  Total ( k , M ) (2.12)<br /> M<br /> trong đó, Total(k,M)=  flops( xi , yi ) là tổng số nhịp máy cần thiết để thực hiện<br /> i 1.. M<br /> M phép cộng các số nguyên được lấy một cách ngẫu nhiên trong miền [0, 2k).<br /> Biểu thức vế phải Total (k , M ) = 1 M F ( k ) trong công thức (2.12) được ký hiệu là<br /> M M i 1 i<br /> AAF(k,M).<br /> 2.4. Đánh giá |AAF(k)AAF(k,M)|<br /> 2.4.1. Cơ sở lý thuyết<br /> Trong [1] cho biết với M khá lớn ta có thể sử dụng công thức đánh giá sau:<br /> <br /> Pr ob X  E ( X )  t D ( X ) = 2(t).  (2.13)<br /> M<br /> trong đó X   Xi / M với Xi là các đại lượng cùng phân phối và độc lập với nhau.<br /> i 1<br /> Theo tính chất của kỳ vọng và phương sai ta có: E( X )=m ; D( X ) =  2 M<br /> Nên (2.13) trở thành<br />    = 2(t). (2.14)<br /> Pr ob  X  m  t <br />  M <br /> <br /> <br /> <br /> <br /> T¹p chÝ Nghiªn cøu KH&CN qu©n sù, Sè 33, 10 - 2014 77<br />  Kỹ thuật điện tử & Khoa học máy tính<br /> <br /> Đại lượng F(k) chỉ nhận hữu hạn giá trị do đó kỳ vọng AAF(k) và phương sai<br /> của nó, ký hiệu là (k)2, đều hữu hạn dó đó theo công thức (2.14) ta có công thức<br /> đánh giá tương ứng đó là:<br />   (k )  = 2(t). (2.15)<br /> Pr ob  AAF (k , M )  AAF (k )  t <br />  M <br /> Ví dụ 1: Với t = 3.1, giá trị (3.1) tra được trong bảng 1A (trang 72 [5]) (chú ý:<br /> với cùng một ký hiệu (t) nhưng trong tài liệu [5] chính là 2(t) trong [1] là<br />  <br /> 0.999032 và điều này có nghĩa nếu lấy (k)= 3.1 / M  ( k ) thì theo công thức<br /> (2.15) ta có Pr ob  AAF ( k , M )  AAF ( k )   ( k )  = 0.9990322.<br /> 2.4.2 Ước lượng giá trị (k)<br /> Để áp dụng được công thức (2.15) việc quan trọng tiếp theo là xác định được<br /> giá trị (k). Trong điều kiện F(k) chưa biết phân bố nên chúng ta chỉ có thể ước<br /> lượng giá trị (k), mà điều cần thiết để ước lượng là một cận trên của nó. Trong<br /> mục này chúng ta sẽ đưa ra cách ước lượng nói trên, chúng ta cần chứng minh một<br /> bổ đề sau:<br /> Bổ đề: Cho sự kiện ngẫu nhiên A có phân phối xác xuất Prob(A)=p, nếu trong M<br /> phép thử độc lập ta thấy sự kiện này xuất hiện đúng M lần thì với mọi >0 cho<br /> trước ta có<br /> M 1<br /> Prob(1p > ) = 1    (2.16)<br /> Chứng minh: Biết rằng xác suất để sự kiện A xuất hiện M lần trong M phép thử là<br /> pM , do đó,<br /> 1 1 M 1<br /> Prob(1p > ) =  p M dp /  p M dp = 1    .<br /> 0 0<br /> Ví dụ 2. Với M=10 và =0.0000006908 ta có 1  M 1 = 0.001.<br /> 7<br /> <br /> Từ bổ đề trên ta dễ dàng thu được kết quả sau dùng để ước lượng cận trên cho<br /> giá trị .<br /> Hệ quả: Cho đại lượng ngẫu nhiên X có miền giá trị là {0, 1, ..., n}. Nếu thực hiện<br /> M phép thử độc lập X chỉ nhận giá trị trong miền [s,e] và E(X) s  e n .<br /> min  ; <br />  2 2<br /> Khi đó với mọi 0