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