Logarit rời rạc là bài toán khó (chưa biết một thuật toán hiệu quả nào), trong khi bài toán ngược luỹ thừa rời rạc lại không khó (có thể sử dụng thuật toán bình phương và nhân). | CHƯƠNG II. SINH số NGUyÊN phương pháp TĂNG DẨN ĐỘ DÀI nên rõ ràng ta chưa thể lập trình thực hiện nó. Theo quan điểm của chúng tôi việc sử dụng ý tưởng trong xây dựng thuật toán để tiến hành thiết lập một thuật toán có ý nghĩa thực hành sẽ thiết thực hơn nhiều. Chúng ta có thể lấy N 32 và cứ tiến hành sinh các số nguyên tố lớn theo phương pháp đã chỉ ra ở trên tất nhiên có thể sẽ gặp phải những ngoại lệ nào đó mà chúng ta có thể không thành công trong một vài lần thực hiện nhưng bù lại thuật toán sinh này lại là thuật toán nhanh và việc lập trình thực hiện chúng lại dễ dàng. Do sự có thể khác nhau giữa giá trị N0 32 so với giá trị sẽ tồn tại nêu trong phần chứng minh lý thuyết là N chúng ta sẽ gặp một số ngoại lệ khi tiến hành sinh các số nguyên tố có độ dài bit nằm trong khoảng từ N0 đến N ngoại lệ đáng kể nhất đó là sự không thoả mãn các tính chất được phát biểu trong định lý nhưng điều này không có nghĩa là tính đa thức về thời gian tính của thuật toán bị sai và như vậy thuật toán dù xuất phát từ N0 1 nào cũng vẫn là thuật toán thời gian đa thức bởi vì mọi ngoại lệ trong một khoảng hữu hạn N0 đến N sẽ được bù thêm bằng một hằng số cộng về thời gian tính. Cuối cùng trên quan điểm kinh tế sẽ thiết thực hơn nhiều nếu chúng ta có được số liệu về thời gian sinh trung bình của thuật toán trong một vài độ dài số cần sinh cụ thể nào đó để đối với thời gian sinh của một số thuật toán sinh khác mà cơ sở dựa vào của chúng là các thuật toán kiểm tra tất định tất nhiên có thể là không đa thức. TÀI LIỆU DẪN L. Đ. Tân Lều Đức Tân. Một số thuật toán kiểm tra nhanh tính nguyên tố của các số trên một số lớp số. Luận án phổ tiến sĩ Hà nội 1993. Ribenboim Paulo Ribenboim. The Little Book of Big Primes. SpringeVerlag 1991. ĐỀ TÀI SINH 6HAM số CHO HỆ MẬT ELGAMAL. 33 CHƯƠNG III. CHƯƠNG TRÌNH SINH số NGUyÊN TỐ MẠNH CHO HỆ MẬT ELGAMAL. CHƯƠNG III CHƯƠNG TRÌNH SINH số NGUYÊN Tố MẠNH CHO HỆ MẬT ELGAMAL Mỏ ĐẦU Trong chương II chúng ta đã biết đến một thuật toán nhanh mà bất cứ
