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 - Lều Đức Tân

Tài liệu 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 - Lều Đức Tân: Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 33, 10 - 2014 75 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 LỀU ĐỨC TÂN*, HOÀNG VĂN QUÂN**, HOÀNG NGỌC MINH* 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 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ề nhất. Để đỏnh giỏ được mức độ tiờu tốn tài nguyờn cũng như tốc độ thực hiện 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 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 trờn phần cứng. Từ khúa: Phộp cộng, Xung nhịp mỏy, ECC. 1. MỞ ĐẦU 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ỡ 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ẽ 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 cộng hai số nguyờn trong miền [0, 2k) ...

pdf7 trang | Chia sẻ: quangot475 | Ngày: 12/01/2021 | Lượt xem: 5 | Lượt tải: 0download
Bạn đang xem nội dung tài liệu 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 - Lều Đức Tân, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
Nghiªn cøu khoa häc c«ng nghÖ T¹p chÝ Nghiªn cøu KH&CN qu©n sù, Sè 33, 10 - 2014 75 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 LỀU ĐỨC TÂN*, HOÀNG VĂN QUÂN**, HOÀNG NGỌC MINH* 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 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ề nhất. Để đánh giá được mức độ tiêu tốn tài nguyên cũng như tốc độ thực hiện 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 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 trên phần cứng. Từ khóa: Phép cộng, Xung nhịp máy, ECC. 1. MỞ ĐẦU 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ì 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ẽ 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 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]. 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 là AAF(k) để thực hiện phép cộng hai số nguyên trong miền [0, 2k) và đó cũng 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 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 đạ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ử 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á 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 và đã được chứng minh trong mục 3.4. 2. MẠCH CỘNG HAI SỐ NGUYÊN VÀ PHÂN PHỐI XÁC SUẤT CỦA ĐẠI LƯỢNG F(k) 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 máy Mạch cộng bao gồm thanh ghi A được gọi là thanh ghi tổng (theo nghĩa giá trị 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à 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) [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  [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 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 lần lượt là X = (xm1, ..., xk, xk1, ..., x1, x0)2 và (2.1) Y = (ym1, ..., yk, yk1, ..., y1, y0)2 (2.2) 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], là A[i] = xi và C[i] = yi. (2.3) Kỹ thuật điện tử & Khoa học máy tính L. §. T©n, H. V. Qu©n, H. N. Minh, " Mét ph­¬ng ph¸p tÝnh to¸n ... trªn phÇn cøng." 76 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 = 0 với mọi sk. 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 ứ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 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ó 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à 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ì "[0] 0 "[ ] '[ 1] '[ 1] (0 ) "[ ] '[ ] '[ ] (0 ) C C i A i C i i m A i A i C i i m               (2.4) 2.2. Phân phối xác suất của đại lượng F(k) 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ó phân bố Prob(F(k)=f) = k4 )f,k(N (f=0, 1, ..., k+1). (2.5) trong đó, N(k,f) = #{(X,Y): X, Y  [0, 2k) và flops(X,Y) = f}. 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 0 vì vậy mạch dừng và điều này có nghĩa flops(X,0) = 0. (2.6) Với mọi f = 1, 2, ..., k+1; lấy X = 1 và Y = 2f1  1 thì trạng thái đầu tiên của C là 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í thấp nhất. Dễ dàng nhận ra rằng flops(1, 2f1  1) = f (f = 1, 2, ..., k+1). (2.7) Bây giờ ta sẽ chứng tỏ với mọi X, Y  [0, 2k) thì flops(X,Y)  k+1. (2.8) 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 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 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 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 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à (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 = 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à tính chất đã được chứng minh. 2.3. Cách tiếp cận và công cụ để tính giá trị AAF(k) Để tính AAF(k) có hai tiếp cận để thực hiện đó là tính đúng giá trị này trong trường hợp k<15 và tính gần đúng nó trong trường hợp ngược lại. 2.3.1. Công thức tính đúng giá trị AAF(k) Theo công thức (2.5) ta có công thức sau để tính đúng giá trị AAF(k): Công thức tính đúng giá trị AAF(k) AAF(k) = ( ) 4 Total k k (2.9) Nghiªn cøu khoa häc c«ng nghÖ T¹p chÝ Nghiªn cøu KH&CN qu©n sù, Sè 33, 10 - 2014 77 trong đó   , [0,2 ) ( , ) kx y Total k flops x y    là tổng số nhịp máy cần thiết để thực hiện toàn bộ 4k phép cộng các số nguyên trong miền [0, 2k). Thật vậy, AAF(k)= E(F(k)) 1 0 ( , ) 4 k j N k f j k    =     1k 0j k )f,k(Nj 4 1 = k4 )k(Total . Như vậy công thức (2.9) đã được chứng minh. 2.3.2. Công thức tính gần đúng giá trị AAF(k) Theo [1] khi khảo sát một đại lượng ngẫu nhiên X nào đó người ta tiến hành M phép thử (quan sát giá trị nhận được của X), giả sử trong phép thử thứ i, giá trị nhận được của X là xi (i=1, ..., M). Khi này 1 (1/ ) M i i M x   được gọi là kỳ vọng mẫu, M được gọi là kích thước mẫu và như một hệ quả của định lý Markov ta có với mọi >0 nhỏ tùy ý thì 1 lim Pr ( ) 1 M ob x E XiM M i           = 1 (2.10) Áp dụng cho X=F(k) ta có 1 lim Pr ( ) ( ) 1 M ob F k AAF kiM M i           = 1 (2.11) Từ (2.11) thì ta có thể lấy 1 (1 / ) ( ) M i i M F k   là giá trị gần đúng của AAF(k) và chứng 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ị AAF(k) AAF(k)  ( , )Total k M M (2.12) trong đó, Total(k,M)= 1.. ( , ) i M flops x yi i  là tổng số nhịp máy cần thiết để thực hiện 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). Biểu thức vế phải ( , )Total k M M = 1 ( ) 1 M F kiM i   trong công thức (2.12) được ký hiệu là AAF(k,M). 2.4. Đánh giá |AAF(k)AAF(k,M)| 2.4.1. Cơ sở lý thuyết Trong [1] cho biết với M khá lớn ta có thể sử dụng công thức đánh giá sau:  Pr ( ) ( )ob X E X t D X  = 2(t). (2.13) trong đó 1 / M i 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. Theo tính chất của kỳ vọng và phương sai ta có: E( X )=m ; D( X ) = 2 M Nên (2.13) trở thành Pr ob X m t M          = 2(t). (2.14) Kỹ thuật điện tử & Khoa học máy tính L. §. T©n, H. V. Qu©n, H. N. Minh, " Mét ph­¬ng ph¸p tÝnh to¸n ... trªn phÇn cøng." 78 Đại lượng F(k) chỉ nhận hữu hạn giá trị do đó kỳ vọng AAF(k) và phương sai 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 đánh giá tương ứng đó là: ( ) Pr ( , ) ( ) k ob AAF k M AAF k t M        = 2(t). (2.15) Ví dụ 1: Với t = 3.1, giá trị (3.1) tra được trong bảng 1A (trang 72 [5]) (chú ý: 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à 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 (2.15) ta có  Pr ( , ) ( ) ( )ob AAF k M AAF k k   = 0.9990322. 2.4.2 Ước lượng giá trị (k) Để áp dụng được công thức (2.15) việc quan trọng tiếp theo là xác định được 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 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 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 bổ đề sau: 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 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 trước ta có Prob(1p > ) =   1 1 M    (2.16) 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à pM , do đó, Prob(1p > ) = 1 1 0 0 /M Mp dp p dp    =   1 1 M    . Ví dụ 2. Với M=107 và =0.0000006908 ta có   1M1  = 0.001. Từ bổ đề trên ta dễ dàng thu được kết quả sau dùng để ước lượng cận trên cho giá trị . 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 M phép thử độc lập X chỉ nhận giá trị trong miền [s,e] và E(X) min ; 2 2 s e n      . Khi đó với mọi 0<<1 ta đánh giá 2     2 2 (1 ) (1 ) (1 )e s n s           . (2.17) Thì xác suất sai lầm loại 2 của đánh giá trên là  =   1M1  . 3. KẾT QUẢ TÍNH TOÁN SỐ AAF(k) VÀ AAF(k,M) 3.1. Cách tính giá trị AAF(k) Chúng ta sử dụng hàm flops(X,Y) để tính số nhịp máy. Trong trường hợp k nhỏ, cụ thể k14, và tiến hành đếm toàn bộ số nhịp máy cho tất cả 22k phép cộng, giá trị thu được ký hiệu là Total(k) và khi này ta có AAF(k) = Total(k)22k. (3.1) Ngược lại, chọn phương pháp thống kê đó là tiến hành lấy ngẫu nhiên M=107 Nghiªn cøu khoa häc c«ng nghÖ T¹p chÝ Nghiªn cøu KH&CN qu©n sù, Sè 33, 10 - 2014 79 cặp số nguyên X, Y  [0, 2k), tính Total(k,107) tổng của 107 giá trị flops(X,Y) trong mỗi lần lấy ngẫu nhiên đó và khi này AAF(k,107) = Total(k,107)107 (3.2) Để phục vụ cho việc đánh giá sai số như đã đưa ra trong mục 2.4, ngoài việc tính Total(k) chúng ta còn phải xác định hai tham số fs(k) và fe(k) (dùng trong công thức 3.3) với fs(k) là giá trị đầu tiên và fe(k) là giá trị cuối cùng có N(k,f)0. 3.2. Kết quả duyệt toàn bộ 22k phép cộng khác nhau với k từ 0 đến 14 Total(1) = 3, AAF(1) = 0.750000 Total(2) = 21, AAF(2)= 1.312500 Total(3) = 113, AAF(3)= 1.765625 Total(4) = 547, AAF(4)= 2.136719 Total(5) = 2509, AAF(5)= 2.450195 Total(6) = 11135, AAF(6)= 2.718506 Total(7) = 48373, AAF(7)= 2.952454 Total(8) = 206991, AAF(8)= 3.158432 Total(9) = 876061, AAF(9) =3.341908 Total(10)=3677047, AAF(10)=3.506705 Total(11)=15334149, AAF(11)=3.655946 Total(12)=63619791, AAF(12)=3.792035 Total(13)=262861101, AAF(13)=3.91693 Total(14)=1082389767, AAF(14)=4.032216 3.3. Kết quả thống kê với 107 mẫu cho mỗi k từ 15 đến 4096 Bảng 3.1 dưới đây ghi kết quả thống kê được của 112 giá trị k bao gồm k từ 15 đến 64; k từ 96 đến 1024 trong dạng k=32i (i=1,..., 30); k từ 1088 đến 2048 trong dạng k=64i (i=1,..., 16) và ; k từ 2176 đến 4096 trong dạng k=128i (i=1,..., 16). Các số liệu được ghi trong bảng bao gồm: k, AAF(k,107), fs(k), fe(k) và (k). Các số liệu AAF(k,107), fs(k), fe(k) có được từ thống kê còn (k) được ước lượng theo ví dụ 1 mục 2.4.1 (để đạt được độ tin cậy 0.999032), giá trị 2 được đánh giá theo công thức (2.17) còn  = 0.0000006908 được lấy theo ví dụ 2 mục 2.4.2 (để đảm bảo xác suất sai không quá 0.001). Tóm lại (k) được tính theo công thức sau (k) = 2 2 (1 )( (1 ) ) ( 1 (1 ) ) 3.1 7 10 f f k fe s s            (3.3) Bảng 3.1. Kết quả thống kê 112 giá trị của k. k AAF(k,107) fs (k) fe (k) (k) k AAF (k,10 7) fs(k) fe (k) (k) 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 4.1399501 4.2386532 4.3320945 4.4200825 4.5026766 4.5807384 4.6553482 4.7249131 4.7923977 4.8568043 4.9183709 4.9770195 5.0349873 5.0876514 5.1409723 5.1919811 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 16 17 18 19 20 21 22 23 23 24 23 24 25 24 25 24 0.016039 0.017042 0.018044 0.019046 0.020049 0.021051 0.022054 0.023056 0.022054 0.024059 0.022054 0.023056 0.024059 0.023056 0.024059 0.023056 288 320 352 384 416 448 480 512 544 576 608 640 672 704 736 768 8.4977167 8.6502339 8.7886398 8.9146046 9.0295142 9.1369311 9.2362259 9.3298887 9.4175886 9.5004907 9.5784751 9.6527988 9.7229998 9.7910969 9.8535831 9.9160444 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 30 34 33 31 31 30 31 31 30 32 33 32 34 31 34 34 0.026065 0.030074 0.029072 0.027068 0.027068 0.025064 0.026067 0.026067 0.025065 0.027070 0.028073 0.027071 0.029076 0.026070 0.029077 0.029078 Kỹ thuật điện tử & Khoa học máy tính L. §. T©n, H. V. Qu©n, H. N. Minh, " Mét ph­¬ng ph¸p tÝnh to¸n ... trªn phÇn cøng." 80 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 96 128 160 192 224 256 5.2410299 5.2881423 5.3332005 5.3778501 5.4209489 5.4637941 5.5035587 5.5434711 5.5817211 5.6189158 5.6558295 5.6920440 5.7259800 5.7601316 5.7937005 5.8254527 5.8576532 5.8874458 5.9189435 5.9480496 5.9780568 6.0063450 6.0338280 6.0620954 6.0884972 6.1156798 6.1410676 6.1666951 6.1914261 6.2161775 6.2402992 6.2647414 6.2882122 6.3104244 6.9032910 7.3216611 7.6464142 7.9104545 8.1340866 8.3274409 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 2 1 2 2 2 2 2 3 3 3 3 4 26 27 25 25 28 27 26 27 26 26 26 28 27 31 27 27 26 29 28 27 33 27 26 27 29 28 28 33 27 28 33 29 29 27 29 29 29 28 29 30 0.025061 0.026063 0.024059 0.024059 0.027066 0.026064 0.025061 0.026064 0.025061 0.025061 0.025061 0.027066 0.026064 0.030073 0.026064 0.026064 0.025061 0.028068 0.027066 0.026064 0.032078 0.026064 0.025061 0.026064 0.028068 0.026064 0.026064 0.032078 0.025061 0.027066 0.031076 0.027066 0.027066 0.025061 0.027066 0.026064 0.026064 0.025062 0.026064 0.026064 800 832 864 896 928 960 992 1024 1088 1152 1216 1280 1344 1408 1472 1536 1600 1664 1728 1792 1856 1920 1984 2048 2176 2304 2432 2560 2688 2816 2944 3072 3200 3328 3456 3584 3712 3840 3968 4096 9.9746949 10.0314707 10.0860103 10.1386865 10.1888623 10.2389178 10.2861217 10.3310832 10.4188155 10.5008227 10.5797636 10.6537093 10.7234819 10.7905204 10.8558274 10.9169641 10.9755471 11.0313155 11.0867588 11.1397614 11.1900650 11.2385736 11.2870085 11.3325767 11.4198410 11.5021737 11.5800870 11.6550679 11.7249838 11.7917189 11.8547999 11.9175576 11.9760081 12.0320870 12.0871429 12.1393587 12.1904356 12.2395965 12.2859574 12.3345439 5 5 6 5 5 6 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 33 33 31 32 34 35 32 34 33 35 34 32 33 34 34 35 33 34 34 33 32 32 30 33 32 32 35 35 35 34 33 33 31 35 32 35 33 34 33 32 0.028076 0.028077 0.025071 0.027076 0.029081 0.029082 0.027078 0.029083 0.027081 0.029087 0.028086 0.026085 0.027089 0.028093 0.028095 0.029099 0.027099 0.028102 0.028105 0.027107 0.026109 0.025112 0.023115 0.027119 0.025126 0.025134 0.028141 0.028149 0.028157 0.027167 0.026178 0.026188 0.024205 0.028205 0.025225 0.028226 0.026246 0.027254 0.026272 0.024299 3.4. Đánh giá về hàm AAF(k) Kết quả 1: Trong phạm vi k từ 1 đến 4096 ta có bất đẳng thức sau với xác suất tin cậy trên 0.998 log2(k)  AAF(k)  log2(k)+1. (3.4) Chứng minh: Như đã được đánh giá trong ví dụ 1 mục 2.4 thì |AAF(k)AAF(k,M)| < (3.1/ ) ( )M k (3.5) với 2(k) là phương sai của F(k) có xác suất tin cậy là 0.9990322 hay nói một cách khác là xác suất sai của bất đẳng thức (3.5) là không đến 0.001. Mặt khác theo bất đẳng thức (2.17) trong hệ quả trong mục 2.4.2 thì 2     22 s)1(ns)1(e)1(  (3.6) Ví dụ 2 mục 2.4.2 cho thấy xác suất sai của bất đẳng thức trên trong trường hợp M=107 và =0.0000006908 là 0.001. Cho nên xác định giá trị (k) theo công thức (3.3) ta có (k) 3.1/ ( )M k và vì thế ta thu được AAF(k,107)  (k)  AAF(k) AAF(k,107)+(k) (3.7) Với xác suất sai không đến 0.002 và do vậy xác suất tin cậy của (3.7) là trên 0.998. Từ số liệu thống kê về các giá trị AAF(k,107) và (k) tính được đưa ra trong bảng 1 ta có ngay được kết quả 1, tuy nhiên để dễ quan sát hơn chúng tôi đã thực hiện vẽ 4 đồ thị của các hàm AAF(k,107)(k), ký hiệu là AAF- , Nghiªn cøu khoa häc c«ng nghÖ T¹p chÝ Nghiªn cøu KH&CN qu©n sù, Sè 33, 10 - 2014 81 AAF(k,107)+(k), được ký hiệu là AAF + , log2(k) và log2(k)+1 trong hình vẽ 1. Rõ ràng bất đẳng thức trên là đúng và kết quả 1 đã được chứng minh. Hình 1. Đồ thị các hàm AAF(k,107)(k), AAF(k,107)+(k), log2(k) và log2(k)+1 trong khoảng [1, 4096]. 4. KẾT LUẬN Trên thực tế, phép cộng là phép tính cơ sở cho việc thực hiện các phép tính như phép nhân điểm, phép lũy thừa, phép nghịch đảo trong các thuật toán mật mã. Bài báo đã đưa ra được một công thức tính tương quan gần đúng giữa xung nhịp máy và phép cộng hai số nguyên, nói cách khác là số xung nhịp máy tiêu tốn trung bình cho phép cộng hai số nguyên. Kết quả này sẽ là tiền đề để đánh giá tính hiệu quả của một số phép nhân số lớn trong các thuật toán mật mã [4]. TÀI LIỆU THAM KHẢO [1]. T.T. Điệp, L.H.Tú, “Lý thuyết xác suất và thống kê toán học” NXBGD,Hà Nội 1999. [2]. N.T. Vân, “ Kỹ thuật số ”, Nhà xuất bản Khoa học & Kỹ thuật, Hà Nội 1999. [3]. Daniel Tabak, “ Advanced Microrocessors ”, McGraw-Hill Inc, 1995. [4]. Darrel Hankerson, Alfred Menezes, Scott Vanstone, “Guide to Elliptic Curve Crytography”, Springer-Verlag New York, Inc. 2004. [5]. J.Likeš, J. Laga, “Základní Statiscke Tabulky", Nakl. tech. literatury, Praha 1978. ABSTRACT A METHOD OF CALCULATING THE CORRELATION BETWEEN THE MACHINE CLOCK AND THE ADDITION OF TWO INTEGER WHEN IMPLEMENTED ON HARDWARE In the implementation of public-key cryptography systems, numerical calculations on the large integer calculation is always important and hardest. To assess the level of resource consumption as well as the speed of execution of this operation, in this paper we propose a method of calculating the correlation between the machine clock and the addition of two integers to real on hardware. Keywords: Addition, machine clock, Elliptic Curve Cryptography. Nhận bài ngày 15 tháng 6 năm 2014 Hoàn thiện ngày 10 tháng 9 năm 2014 Chấp nhận đăng ngày 25 tháng 9 năm 2014 Địa chỉ: * Ban Cơ yếu Chính phủ; ** Cục Cơ yếu – BTTM; DĐ 0983074784. F lo p s 14 12 10 8 6 4 2 0

Các file đính kèm theo tài liệu này:

  • pdf10_hoangvquan_75_81_7726_2149213.pdf
Tài liệu liên quan