- ch−ơng i. - vai trò của số nguyên tố dạng p=2q+1 trong mật mã.. - Kỹ thuật để tìm cặp s,t nêu trong kết quả 1.4 đ−ợc thực hiện nh− sau.. - Chọn B là một số nguyên nào đó gọi là ng−ỡng của cơ sở phân tích, giả sử m là số các số nguyên tố không quá B, sau đó tiến hành các b−ớc sau:. - k m+1 t m+1 , dễ dàng kiểm tra. - Chú ý rằng, b−ớc 1 đ−ợc thực hiện theo cách Lấy-Kiểm tra cho đến khi tìm đ−ợc đầy đủ số cặp theo yêu cầu, còn việc làm của b−ớc 2 chính là giải một hệ ph−ơng trình đại số tuyến tính hệ số trên GF(q) mà hệ này luôn có nghiệm. - Tóm lại ta luôn tìm đ−ợc cặp s,t theo mong muốn, tuy nhiên để có thể đ−a ra một dẫn giải t−ờng minh về thời gian tính của thuật toán này là một. - Chúng ta bằng lòng với kết quả đã đ−ợc công bố về thời gian tính của ph−ơng pháp sàng bậc q nh− sau (xem [Stinson]).. - Kết quả 1.5. - Thời gian tính tiệm cận của thuật toán sàng bậc q để tìm đ−ợc logarit trên tr−ờng GF(p) là. - ở trên q là −ớc nguyên tố lớn nhất của p-1, còn O(1) là một vô cùng bé khi. - 1.2.4 Thuật toán sàng tr−ờng số. - Giống nh− ý t−ởng của thuật thoán sàng bậc q, ph−ơng pháp sàng tr−ờng số cũng thực hiện theo kiểu tìm cặp s,t sao cho ε s a t =w q (mod p), sự khác biệt cơ bản là thay vì việc tìm các cặp s,t trên trực tiếp trên GF(p) của sàng bậc q thì sàng tr−ờng số lại đi tìm chúng trong tr−ờng mở rộng K nào đó.. - Tính hiệu quả của thuật toán sàng tr−ờng số là ở chỗ có thể khéo léo lựa chọn. - đ−ợc tr−ờng K thích hợp để việc tìm cặp s,t đ−ợc dễ dàng hơn. - Để có thể trình bày cặn kẽ các b−ớc thực hiện của ph−ơng pháp này chúng ta cần phải có một loạt kiến thức bổ trợ về đại số cao cấp (xem chi tiết trong [P. - đích của đề tài này không phải là lặp lại một việc làm nh− vậy mà ở đây chúng tôi chỉ muốn dẫn ra kết quả cuối cùng về thời gian tính của thuật toán. - Kết quả 1.6. - Thời gian tính tiệm cận của thuật toán sàng tr−ờng số để tìm. - đ−ợc logarit trên tr−ờng GF(p) là. - ở trên q là −ớc nguyên tố lớn nhất của p-1, C ≈ 1.9229 còn O(1) là một vô. - Để các hệ mật mà độ mật dựa trên cơ sở tính khó giải của bài toán logarit trên tr−ờng GF(p) có độ an toàn cao thì:. - 1.Độ dài nhị phân của số nguyên tố p phải lớn. - p-1 phải có −ớc nguyên tố lớn, tốt nhất là các số nguyên tố mạnh.. - Với các kết luận trên rõ ràng việc sinh các số nguyên tố mạnh để sử dụng trong Ngành là một điều tất yếu và vô cùng cần thiết trong giai đoạn này.. - Hoà] Phạm Thị Minh Hoà, Nghiên cứu ph−ơng pháp sàng tr−ờng số, tính logarit rời rạc trên tr−ờng hữu hạn. - sinh số nguyên tố.bằng ph−ơng pháp tăng dần độ dài. - sinh số nguyên tố lớn bằng ph−ơng pháp tăng dần độ dài. - Một thuật toán sinh các số nguyên tố thông th−ờng đ−ợc coi là một hệ quả của một thuật toán kiểm tra tính nguyên tố nào đó theo ph−ơng thức. - "Chọn ngẫu nhiên số tự nhiên x độ dài n, sau đó lấy và kiểm tra các số trong dãy x+k (với k=0,1,2. - cho đến khi đ−ợc số nguyên tố". - Nh− vậy tự nhiên mà nói thì thuật toán sinh bao giờ cũng "lâu". - hơn thuật toán kiểm tra mà nó dựa vào. - Cho đến bây giờ, ch−a tồn tại một thuật toán kiểm tra tất định tính nguyên tố trong thời gian đa thức do vậy mọi thuật toán sinh theo cách cổ truyền trên không thể thực hiện đ−ợc trong thời gian đa thức. - Đối với thuật toán xác suất thì với ph−ơng pháp kiểm tra tính xác suất của Rabin-Miller hay của Salovay-Strassen chúng ta có ngay đ−ợc một thuật toán sinh với thời gian tính cỡ O(n 6 ) và trong tr−ờng hợp giả thuyết Riemann mở rộng là đúng đắn thì nó cũng là một thuật toán tất định.. - Trong ch−ơng này chúng tôi đ−a ra một ph−ơng thức mới để xây dựng thuật toán sinh và với ph−ơng thức này chúng tôi thu đ−ợc một kết quả khá. - thú vị đó là thuật toán xác suất đ−ợc thực hiện trong thời gian O(n 8. - Điểm khác biệt cơ bản giữa thuật toán mà chung tôi đ−a ra với thuật toán xác suất của Rabin-Miller hay của Salovay-Strassen là ngay cả trong tr−ờng hợp giả. - thuyết Riemann mở rộng ch−a đ−ợc chứng minh thì các số thu đ−ợc tại đầu ra của thuật toán này luôn là nguyên tố trong khi đó của thuật toán sau là ch−a chắc. - Kết quả thu đ−ợc của chúng tôi chỉ là một đóng góp khiêm tốn trong lĩnh vực lý thuyết số và thuật toán bởi vì nó mới chỉ là một ví dụ chứng tỏ sự. - "Không phải là hệ quả của thuật toán sinh đối với thuật toán kiểm tra". - đã là nh− vậy thì tính đa thức của thuật toán sinh cũng ch−a chắc đã đóng góp. - đ−ợc gì cho khả năng tạo đ−ợc thuật toán kiểm tra mà theo chúng tôi thì sự. - thiết kế đ−ợc thuật toán kiểm tra nhanh mới là đóng góp lớn. - Một đặc điểm trong việc xây dựng thuật toán sinh của chúng tôi là các công cụ đ−ợc sử dụng rất đơn giản thậm chí là rất "cũ kỹ". - Đơn giản nh−ng hiệu quả có lẽ là đóng góp cao nhất của chúng tôi trong công bố thuật toán ở ch−ơng này.. - Kết quả đạt đ−ợc chính trong ch−ơng của chúng tôi có thể nêu nh− sau:. - Từ những phân tích về sai lầm loại 1 của thuật toán kiểm tra tính nguyên tố các số trong lớp L F chúng ta có đ−ợc thời gian thực hiện của thuật toán Pock_test F dùng để kiểm tra tính nguyên tố của một số tự nhiên độ dài n là T Pock-test (n)≤C α n 4 lnn với C α là một hằng số tính đ−ợc theo xác suất sai lầm loại 1 của thuật toán là α.. - Từ định lý 2.6 về sự tồn tại số nguyên tố trong đoạn [yF+1;(y+∆)F+1] với ∆≤lnF(lnlnF+6) chúng ta có đ−ợc định lý 2.7 về thời gian tối đa của thuật toán sinh POCK-GEN F ký hiệu là T POCK-GEN (n)≤C 0 n 6 . - Bằng việc chứng minh đ−ợc thời gian sinh một số nguyên tố độ dài n bằng thuật toán sinh các số nguyên tố độ dài <n (định lý 2.11) chúng ta có đ−ợc kết luận quan trọng nhất của ch−ơng đó là thời gian tính của thuật toán sinh số của chúng ta xây dựng là O(n 7. - 2.1 Một số kết quả trong lý thuyết số. - Một số kết quả trong lý thuyết số đ−ợc trích dẫn d−ới đây (xem [Ribenboim], [L. - sẽ đ−ợc sử dụng để xây dựng thuật toán sinh số nguyên tố và quan trọng hơn cả là chứng minh tính đa thức của thuật toán sinh này.. - Định lý Pocklington. - −ớc nguyên tố q của F tồn tại giá trị a sao cho:. - Thì mọi −ớc nguyên tố p của x đều có dạng p=tF+1.. - Định lý về thặng d− bậc q. - Cho p là số nguyên tố lẻ sao cho q là −ớc của p-1.. - Một vài điều kiện đủ về tính nguyên tố.. - Một điều kiện đủ về tính nguyên tố. - định lý Pocklington. - Nếu R ≤ F thì x là số nguyên tố.. - Nếu F<R ≤ F 2 và B 2 -4A là số không chính ph−ơng thì x là số nguyên tố.. - Định lý Dirichlet. - Số các số nguyên tố có dạng Ak+B với gcd(A,B)=1 không v−ợt quá x ký hiệu là π A,B (x) là vô cùng lớn t−ơng đ−ơng với ϕ 1. - tức là π A,B (x. - ở đây ϕ (A) là số các số không quá A và nguyên tố với A.. - Định lý đầu tiên do Dirichlet đ−a ra và chứng minh vào năm 1837 mới dừng ở kết luận là có vô số số nguyên tố dạng Ak+B, sau này Valée Poussin
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt