Người ta thường chọn nhóm G trong mật mã logarit rời rạc là nhóm cyclic (Zp)×; chẳng hạn như mật mã ElGamal, Trao đổi khoá Diffie-Hellman, và Chữ ký số Elgamal. | CHƯƠNG III. CHƯƠNG TRÌNH SINH số NGUyÊN TỐ MẠNH CHO HỆ MẬT ELGAMAL. cải tiến của chúng tôi theo hai nghĩa một là để thực hiện lập trình được thuật toán sẵn có và hai là cải thiện được đôi chút về thời gian tính. Phép nhân số lớn Chúng ta đều biết cơ sở để xây dựng phép toán nhân trên các số lớn là công thức nhân sau. Công thức . m n _ Cho X x0 x1q . xmqm và Y yo y1q . ynqn ta cổ XY z z k 3-11 .ũ k 0 i j k Theo công thức nhân 3-11 trên thì để thực hiện một phép nhân hai số lớn có độ dài q phân là n chúng ta cần tối thiểu n2 phép toán nhân hai số trong phạm vi q. Trong Rieshel tác giả có trình bày trong phần phụ lục một thuật toán nhân có thời gian tính chỉ là O n1 5 cụ thể như sau. Đầu tiên chúng ta xét trường hợp tích của hai số có độ dài 2 trong hệ Q phân nào đó. Giả sử X x0 x1Q và Y y0 y1Q dễ dàng kiểm tra được đẳng thức sau. Công thức . XY xoyo xoyo xo-xi yi-yo xiyiJQ xiyiQ2 Xoyo 1 Q xo-Xi yi-yo Q Xiyi Q Q2 3-12 . Như vậy để thực hiện tính toán theo công thức 3-12 chúng ta chỉ cần tính 3 phép nhân các số trong phạm vi Q. Bây giờ nếu chúng ta xét Q q2 thì bằng cách truy hồi theo công thức 3-12 k bước thì tổng số phép nhân hai số trong phạm vi q phục vụ thuật toán này chỉ là n 3k. Rõ ràng 2k-1 n 2k với n là độ dài q phân của các thừa số nhân cho nên nếu theo công thức 3-11 ta phải cần đến n2 22 k-1 4k-1 phép nhân. Tóm lại thời gian tính toán của phép nhân ĐỀ TÀI SINH sô THAM số CHO HỆ MẬT ELGAMAL. 46 CHƯƠNG III. CHƯƠNG TRÌNH SINH số NGUyÊN TỐ MẠNH CHO HỆ MẬT ELGAMAL. hai số lớn độ dài khai triển q phân là n theo cách trên sẽ chỉ là O nLog3 O n1 5 . Trong một số chương trình nguồn tính toán trên các số lớn như N. V. Khán V. V. Xứng Kapp . mà chứng tôi có trong tay thì chưa có chương trình này thực hiện phép nhân theo công thức 3-11 . Để thực hiện thuật toán theo công thức 3-12 vừa trình bày cần đến kỹ thuật lập trình cao vì bản chất của thuật toán là đệ quy nên rất khó thực hiện. Chứng tôi tránh việc phải thực hiện đệ quy bằng chia thuật toán nhân ra .
