be_thodia_iuanh91
New Member
Download miễn phí Đề tài Bài toán phân tích số nguyên ra thừa số nguyên tố
Mục lục
Lời nói đầu 1
Chương I : Đặt vấn đề và ý nghĩa bài toán phân tích số nguyên 3
Chương II : Số Mersenne và việc phân tích 5
2.1. Số Mersenne 5
2.2. Phép thử nguyên tố cho các số Mersenne 6
Chương III : Một số thuật toán và phương pháp phân tích số nguyên 10
3.1. Thuật toán sàng Eratosthenes10
3.2. Thuật toán sàng đồng dư 10
3.3. Thuật toán sàng bậc hai 11
3.4. Thuật toán Dixon và sàng bậc hai 14
3.5. Phương pháp p-1: Thuật toán Pollard thứ nhất 16
3.6. Phương pháp p : Thuật toán Pollard thứ hai 19
3.7. Phương pháp p ? 1 : Thuật toán Williams 20
3.8. Phương pháp p của Pollard 22
3.9. Mô tả đại số phương pháp p Pollard 26
3.10. Chương trình mô tả phương pháp p Pollard 27
Chương VI : Xây dựng phần mềm phân tích các số dạng 2n - 1 30
4.1. Sơ đồ xuất phát 30
4.2. Phân tích hệ thống 3
4.3. Cài đặt chương trình 41
4.4. Sơ đồ khối của các module thuộc chương trình 43
Phụ lục 1 : Kết quả phân tích các số dạng 2n – 1 ( n? 200 ) .45
Kết luận .53
Phụ lục 2 : Chương trình nguồn 54
Tài liệu dẫn và tham khảo . 71
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à đã cuốn hút nhiều bộ óc vĩ đại nhất trên thế giới để 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 và Shamir. 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ố.
Bản đồ án không đi sâu vào các phân tích của những ý nghĩa nêu trên mà đã đặt nhiệm vụ chính là giải quyết bài toán, phân tích các số 2m-1 ra thừa số nguyên tố (với m200) như là một việc làm trung gian của một ứng dụng thực tiễn cụ thể.
Để giải quyết vấn đề được đặt ra trong đồ án này, chúng tui đư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 tui thề hiện bởi việc trình bày khá tường minh cho thuật toán của Williams theo cách hiểu của mình (chúng tui chỉ có trong tay các đoạn vắn tắt về ý tưởng của thuật toán) đồng thời thuật toán dựa vào phân tích của Nl trong mục 2.3 phần nào bổ xung tốt cho phần “khó giải được" của các thuật toán đã nêu trong 2.2.
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 tui 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 tui 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 tui 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.
CHƯƠNG I. SỐ MERSENNE VÀ VIỆC PHÂN TÍCH
1.1 Số Mersenne
Nếu một số có dạng 2m-1 là một số nguyên tố thì m=q là một số nguyên tố. Không khó khăn lắm, có thể chứng minh được rằng nếu 2m-1 là luỹ thừa của một số Prime Power thì nó phải là một số nguyên tố và do vậy m cũng là một số nguyên tố.
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.
Ở vào thời đại của Mersenne, người ta đã biết rằng một vài số Mersenne là số chính phương và một vài số khác là hợp số. Ví dụ, M2=3, M3=7, M5=31, M7=127 là nguyên tố, trong khi M11=23*89.
Vào năm 1640 , Mersenne đã cho rằng Mq là số nguyên tố đối với q=13,17,19,31,67,127,257; ông đã nhầm đối với 67 và 257 và đã không đưa 61,89 và 107(những số nhỏ hơn 257) vào danh sách trên. Những số này cũng sinh ra các số nguyên tố Mersenne. Phát hiện của ông thực sự đáng kinh ngạc về mặt độ lớn của các số.
Một bài toán khá hiển nhiên là: Xét xem một số Mersenne có là số nguyên tố không, và nếu không thì xác định các thừa số của nó ( hay còn gọi là bài toán phân tích ra thừa số). Một kết quả cổ điển do Euler đưa ra năm 1750 và sau đó được Lagrange(1775) và Luces(1875) chứng minh là:
Bài toán: Nếu q là một số nguyên tố đồng dư modulo 4(q3(mod 4)) thì Mq chia hết cho 2q+1 khi và chỉ khi 2q+1 là nguyên tố; trong trường hợp này, nếu q>3 thì Mq là hợp số.
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
Mục lục
Lời nói đầu 1
Chương I : Đặt vấn đề và ý nghĩa bài toán phân tích số nguyên 3
Chương II : Số Mersenne và việc phân tích 5
2.1. Số Mersenne 5
2.2. Phép thử nguyên tố cho các số Mersenne 6
Chương III : Một số thuật toán và phương pháp phân tích số nguyên 10
3.1. Thuật toán sàng Eratosthenes10
3.2. Thuật toán sàng đồng dư 10
3.3. Thuật toán sàng bậc hai 11
3.4. Thuật toán Dixon và sàng bậc hai 14
3.5. Phương pháp p-1: Thuật toán Pollard thứ nhất 16
3.6. Phương pháp p : Thuật toán Pollard thứ hai 19
3.7. Phương pháp p ? 1 : Thuật toán Williams 20
3.8. Phương pháp p của Pollard 22
3.9. Mô tả đại số phương pháp p Pollard 26
3.10. Chương trình mô tả phương pháp p Pollard 27
Chương VI : Xây dựng phần mềm phân tích các số dạng 2n - 1 30
4.1. Sơ đồ xuất phát 30
4.2. Phân tích hệ thống 3
4.3. Cài đặt chương trình 41
4.4. Sơ đồ khối của các module thuộc chương trình 43
Phụ lục 1 : Kết quả phân tích các số dạng 2n – 1 ( n? 200 ) .45
Kết luận .53
Phụ lục 2 : Chương trình nguồn 54
Tài liệu dẫn và tham khảo . 71
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à đã cuốn hút nhiều bộ óc vĩ đại nhất trên thế giới để 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 và Shamir. 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ố.
Bản đồ án không đi sâu vào các phân tích của những ý nghĩa nêu trên mà đã đặt nhiệm vụ chính là giải quyết bài toán, phân tích các số 2m-1 ra thừa số nguyên tố (với m200) như là một việc làm trung gian của một ứng dụng thực tiễn cụ thể.
Để giải quyết vấn đề được đặt ra trong đồ án này, chúng tui đư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 tui thề hiện bởi việc trình bày khá tường minh cho thuật toán của Williams theo cách hiểu của mình (chúng tui chỉ có trong tay các đoạn vắn tắt về ý tưởng của thuật toán) đồng thời thuật toán dựa vào phân tích của Nl trong mục 2.3 phần nào bổ xung tốt cho phần “khó giải được" của các thuật toán đã nêu trong 2.2.
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 tui 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 tui 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 tui 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.
CHƯƠNG I. SỐ MERSENNE VÀ VIỆC PHÂN TÍCH
1.1 Số Mersenne
Nếu một số có dạng 2m-1 là một số nguyên tố thì m=q là một số nguyên tố. Không khó khăn lắm, có thể chứng minh được rằng nếu 2m-1 là luỹ thừa của một số Prime Power thì nó phải là một số nguyên tố và do vậy m cũng là một số nguyên tố.
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.
Ở vào thời đại của Mersenne, người ta đã biết rằng một vài số Mersenne là số chính phương và một vài số khác là hợp số. Ví dụ, M2=3, M3=7, M5=31, M7=127 là nguyên tố, trong khi M11=23*89.
Vào năm 1640 , Mersenne đã cho rằng Mq là số nguyên tố đối với q=13,17,19,31,67,127,257; ông đã nhầm đối với 67 và 257 và đã không đưa 61,89 và 107(những số nhỏ hơn 257) vào danh sách trên. Những số này cũng sinh ra các số nguyên tố Mersenne. Phát hiện của ông thực sự đáng kinh ngạc về mặt độ lớn của các số.
Một bài toán khá hiển nhiên là: Xét xem một số Mersenne có là số nguyên tố không, và nếu không thì xác định các thừa số của nó ( hay còn gọi là bài toán phân tích ra thừa số). Một kết quả cổ điển do Euler đưa ra năm 1750 và sau đó được Lagrange(1775) và Luces(1875) chứng minh là:
Bài toán: Nếu q là một số nguyên tố đồng dư modulo 4(q3(mod 4)) thì Mq chia hết cho 2q+1 khi và chỉ khi 2q+1 là nguyên tố; trong trường hợp này, nếu q>3 thì Mq là hợp số.
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links