Lôgarit rời rạc có ứng dụng trong hệ mật mã khóa công khai Hệ mật mã Elgamal. Lôgarit rời rạc là sự tiếp nối của phép tính lôgarit trên trường số thực vào các nhóm hữu hạn. | CHƯƠNG II. SINH số NGUyÊN phương pháp TĂNG DẨN ĐỘ DÀI Giả sử y là giá trị đầu tiên được chọn trong thuật toán với đầu vào là n thì rõ ràng độ dài của y là k-n-m do số được thử đầu tiên là x yF 1 có độ dài n như vậy số nguyên tố tìm được trong thuật toán giả sử là p y F 1 thì theo công thức 2-9 định lý ta có y y A y m lnm 6 . Rõ ràng y m lnm 6 m lnm 6 1 nên độ dài của p là y y l n log m lnm 6 1 2-20 . Trong công thức 2-20 với m đủ lớn ta sẽ có log m lnm 6 1 m và công thức 2-17 đã được chứng THUẬT TOÁN SINH CÁC số NGUyÊN Tố N BIT TỪ THUẬT TOÁN SINH CÁC số NGUyÊN Tố N BIT Mở đầu Trong mục này chúng tôi giải quyết vấn đề sau Biết thuật toán sinh toàn bộ các số nguyên tố độ dài không đến n. Hãy xây dựng thuật toán sinh các số nguyên tố độ dài không dưới n sao cho cổ thể sinh toàn bộ các số nguyên tố độ dài n. ý tưởng chủ đạo để giải quyết vấn đề trên của chúng tôi là từ khả năng có thể sinh được toàn bộ các số nguyên tố độ dài không đến n của thuật toán đã có chúng tôi sinh ngẫu nhiên các số F thoả mãn hai điều kiện sau F1 . n length F 3. F2 . Biết được phân tích của F ra thừa số nguyên tố. Tiếp đến sử dụng thuật toán sinh Pocklington để sinh các số nguyên tố độ dài không dưới n trong lớp LF. Việc giải quyết vấn đề được thể hiện qua sơ đồ ở trang sau Thuật toán Sơ đồ thuật toán . ĐỀ TÀI SINH 6HAM số CHO HỆ MẬT ELGAMAL. 27 CHƯƠNG II. SINH số NGUyÊN phương pháp TĂNG DẨN ĐỘ DÀI ĐỀ TÀI SINH 6HAM số CHO HỆ MẬT ELGAMAL. 28 CHƯƠNG II. SINH số NGUyÊN phương pháp TĂNG DẨN ĐỘ DÀI Phân tích khả năng sinh các số nguyên tố dộ dài n của thuật toán Chúng ta biết rằng nếu p là một số nguyên tố có độ dài n bit không giảm tổng quát ta giả sử n 2 do đó nó là số lẻ nên có dạng p 2x 1 trong đó x là số có độ dài n do đó mọi ước nguyên tố của x đều có độ dài không quá n-1 bit. Nói một cách khác là x sẽ là bội của F nào đó có thể đuợc tạo từ thuật toán và do đó p sẽ thuộc lớp LF hay p có thể được sinh từ thuật toán. Tóm lại chúng ta .
