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.