tailieunhanh - Hệ Mật Mã Elgamal - Sinh Tham Số An Toàn phần 4

Có những thuật toán mật mã khóa bất đối xứng không có tính chất khóa công khai và bí mật như đề cập ở trên mà cả hai khóa (cho mã hóa và giải mã) đều cần phải giữ bí mật. | CHƯƠNG II. SINH số NGUyÊN phương pháp TĂNG DẨN ĐỘ DÀI bổ xung thêm công thức về mật độ. Ngoài ra nhiều tác giả đã chỉ ra sự không nhu nhau của các giá trị nA B x với cùng một giá trị A còn 1 B A chẳng hạn vào năm 1853 Tschebycheff chỉ ra n31 x n32 x còn n41 x n43 x với một số giá trị x nhỏ vào năm 1957 Leech đã tính đuợc với số x 26861 là số nguyên tố nhỏ nhất để n41 x n43 x và tuơng tự Bays Hudson 1978 tìm đuợc x 608981813029 là số nguyên tố nhỏ nhất để n31 x n32 x việc chỉ ra này Hudson Brauer đã phải bỏ ra vài năm để nghiên cứu xem Ribenboim trang 148-150 . THUẬT TOÁN POCKLINGTON Thuật toán kiểm tra tính nguyên tố Pocklington trên lớp LF Với cơ sở là các kết quả đã nêu trong mục 0 chúng ta có thể xây dựng đuợc thuật toán xác suất định huớng chấp nhận để kiểm tra tính nguyên tố của các số nguyên thuộc lớp LF nhu sau. r Giả sử F npa với mỗi i 1 r ta lấy số tự nhiên Mị gọi là các tham số i 1 của thuật toán. Các tham số này sẽ đuợc phân tích sau. Thuật toán . Thuật toán hiệu là Pock-testF. Đầu vào xeLF. Bước 1. Lấy i 1 Bước 2. p pi M Mi m 1 Bước 3. Lấy a random x . Bước 4. Kiểm tra đồng dư thức aN1 1 mod x . Nếu đúng sang bước 5. Ngược lại Pock-testF x 0 thuật toán dừng. 1 . Bước 5. Kiểm tra điều kiện aiỵh 1 mod x Nếu đúng sang bước 6. Ngược lại sang bước 7. ĐỀ TÀI SINH 6HAM số CHO HỆ MẬT ELGAMAL. 21 CHƯƠNG II. SINH số NGUyÊN phương pháp TĂNG DẨN ĐỘ DÀI Bước 6. Kiểm tra điều kiện m M. Nếu đúng m m 1 quay về bước 3. Ngược lại Pock-testF x 0 thuật toán dừng. 2 . Bước 7. Kiểm tra điều kiện gcd a x 1 p-1 x 1. Nếu đúng sang bước 8. Ngược lại Pock-testF x 0 thuật toán dừng. 3 . Bước 8. Kiểm tra điều kiện i r. Nếu đúng i i 1 quay về bước 2. Ngược lại sang bước 9. Bước 9. Kiểm tra điều kiện R F. Nếu đúng Pock-testF x 1 thuật toán dừng. Ngược lại sang bước 10. Bước 10. Kiểm tra điều kiện R mod F 2-4 R div F Q2. Nếu đúng Pock-testF x 0 thuật toán dừng. 4 . Ngược lại Pock-testF x 1 thuật toán dừng. Đánh giá xác suất sai lầm của