Chuyên Đề Xây dựng phần mềm phân tích các số dạng 2n - 1

Xây dựng phần mềm phân tích các số dạng 2n - 1


Lời nói đầu





Bài toán phân tích số nguyên ra thừa số nguyên tố đã được ra đời từ rất lâu và đã có rất nhiều nhà toán học trên thế giới nghiên cứu và giải quyết vấn đề về nó. Ngoài ý nghĩa lý thuyết của bản thân bài toán thì người ta còn phát hiện ra rất nhiều ý nghĩa thực tiễn đặc biệt là trong mật mã.





Thứ nhất nó là cơ sở cho sự ra đời của một hệ mật khoá công khai nổi tiếng ra đời trong năm 1978, đó là hệ mật RSA của Revert - Shamir - Adlemal. Hệ mật này mà độ mật của nó dựa vào tính khó của việc phân tích số N=pq (p, q nguyên tố ) ra thừa số.





Tiếp đến trong những việc thiết kế nên các bộ tạo dãy giả ngẫu nhiên một trong những nguyên liệu của nó là các đa thức nguyên thuỷ mà để tạo được các đa thức nguyên thuỷ bậc m thì điều đầu tiên phải giải quyết là phân tích hoàn toàn với 2m-1 ra thừa số nguyên tố.





Để giải quyết vấn đề được đặt ra trong đồ án này, chúng tôi đưa ra một số cơ sở lý thuyết.


Chương 1 sẽ trình bầy về các số Mersenne. Các số có dạng Mq=2qưưư-1 (với q là nguyên tố ) được gọi là các số Mersenne và đã được nghiên cứu công phu.


Chương 2 xem xét loại bài toán quen thuộc hơn đó là bài toán phân tích số nguyên ra thừa số. Sự đóng góp có tính khoa học của chúng tôi thề hiện bởi việc trình bày các thuật toán về phân tích số nguyên tố theo cách hiểu của mình.


Chương 3 là phần cơ bản của đề án, trong đó trình bày các tư tưởng của thuật toán phân tích ra thừa số nguyên tố của những số nguyên lớn. Tiếp theo trong chương này trình bày các cài đặt cụ thể cho những thuật toán liên quan đến việc phân tích ra thừa số nguyên tố, ví dụ như các phép : +, -, *, / và luỹ thừa các số lớn. Chúng tôi còn đặc biệt lưu ý tới việc cài đặt thuật toán Pollard thứ nhất một thuật toán rất hiêụ quả trong việc phân tích những hợp số lớn.


Một vấn đề không thể không nói trước là những vấn đề được hiểu thấu đáo sẽ được chúng tôi trình bày chi tiết ở mức độ thuật toán khả thi trong việc lập trình còn một số kết quá cần đến những chuẩn bị toán học cao siêu thì chỉ được dẫn các đánh giá tương ứng về thời gian tính đủ rút ra các thông số cần thiết để xây dựng các tiêu trí. Chúng tôi nghĩ rằng chỉ có thề trình bày bản báo cáo này theo cách như vậy mới đảm bảo tính cân đối trong cấu trúc bởi vì để làm cho tường minh dù chỉ một trong những vấn đề đã né tránh trên chúng ta cũng phải cần đến hàng tập tài liệu dầy, đấy là chưa kể đến việc chúng ta có đủ kiến thức cần thiết đến mức để có thể trình bày nó cho mọi người rõ hay không.