Tạo số nguyên tố ngẫu nhiên Python
|
tạo số nguyên tố
Python triển khai kiểm tra tính nguyên tố của Fermat để tạo các số nguyên tố có độ dài bit bất kỳ Show
Sử dụnggenerate_big_prime(n) # Generates a random prime number of length n bits Cảnh báoCác số nguyên tố được tạo bởi thuật toán này không an toàn cho việc sử dụng mật mã Tất cả các mật mã được mô tả trong cuốn sách này cho đến nay đã tồn tại hàng trăm năm. Những mật mã này hoạt động tốt khi tin tặc phải dựa vào bút chì và giấy, nhưng giờ đây chúng dễ bị tổn thương hơn khi máy tính có thể thao tác dữ liệu nhanh hơn hàng nghìn tỷ lần so với con người. Một vấn đề khác với các mật mã cổ điển này là chúng sử dụng cùng một khóa để mã hóa và giải mã. Việc sử dụng một phím sẽ gây ra sự cố khi bạn đang cố gửi một tin nhắn được mã hóa. ví dụ: làm thế nào bạn có thể gửi khóa một cách an toàn để giải mã nó? Trong , bạn sẽ tìm hiểu cách mật mã khóa công khai cải thiện mật mã cũ bằng cách sử dụng các số nguyên tố rất lớn để tạo hai khóa. khóa công khai để mã hóa và khóa riêng để giải mã. Để tạo các số nguyên tố cho các khóa của mật mã khóa công khai, bạn sẽ cần tìm hiểu về một số thuộc tính của số nguyên tố (và độ khó của việc phân tích các số lớn) giúp tạo ra mật mã. Trong chương này, bạn sẽ khai thác các tính năng này của số nguyên tố để tạo số nguyên tố. mô-đun py, có thể tạo khóa bằng cách nhanh chóng xác định xem một số có phải là số nguyên tố hay không Một số nguyên tố là gì?Số nguyên tố là số nguyên lớn hơn 1 và chỉ có hai ước. 1 và chính nó. Nhắc lại rằng các thừa số của một số là những số có thể được nhân lên bằng số ban đầu. Ví dụ, các số 3 và 7 là thừa số của 21. Số 12 có thừa số 2 và 6 cũng như 3 và 4 Mọi số đều có ước là 1 và chính nó vì 1 nhân với số nào cũng bằng số đó. Ví dụ: 1 và 21 là thừa số của 21 và các số 1 và 12 là thừa số của 12. Nếu không tồn tại ước số nào khác của một số thì số đó là số nguyên tố. Ví dụ: 2 là số nguyên tố vì nó chỉ có 1 và 2 là ước của nó Đây là danh sách ngắn các số nguyên tố (lưu ý rằng 1 không được coi là số nguyên tố). 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, Có vô số số nguyên tố, nghĩa là không tồn tại số nguyên tố lớn nhất. Chúng tiếp tục ngày càng lớn hơn, giống như những con số thông thường. Mật mã khóa công khai sử dụng các số nguyên tố lớn để làm cho khóa quá lớn đối với lực lượng vũ phu Các số nguyên tố có thể khó tìm và các số nguyên tố lớn, chẳng hạn như các số được sử dụng cho khóa công khai, thậm chí còn khó tìm hơn. Để tạo các số nguyên tố lớn làm khóa công khai, chúng ta sẽ tìm một số lớn ngẫu nhiên rồi kiểm tra xem số đó có phải là số nguyên tố hay không bằng cách sử dụng phép kiểm tra tính nguyên tố. Nếu số là số nguyên tố theo kiểm tra tính nguyên tố, chúng tôi sẽ sử dụng nó; Hãy xem xét một số số rất lớn để minh họa mức độ lớn của các số nguyên tố được sử dụng trong mật mã khóa công khai Một googol là 10 lũy thừa 100 và được viết là 1 theo sau là 100 số không 10.000.000.000.000.000.000.000.000.000.000.000.000.000.000, Một tỷ tỷ tỷ googol có nhiều hơn 27 số 0 so với một googol 10.000.000.000.000.000.000.000.000.000.000.000.000.000.000, Nhưng đây là những con số nhỏ so với các số nguyên tố mà mật mã khóa công khai sử dụng. Ví dụ: một số nguyên tố điển hình được sử dụng trong chương trình khóa công khai có hàng trăm chữ số và có thể trông giống như thế này 112.829.754.900.439.506.175.719.191.782.841.802.172.556.768, Con số này lớn đến mức tôi cá là bạn thậm chí còn không nhận ra lỗi đánh máy trong đó Một vài tính năng thú vị khác của số nguyên tố cũng hữu ích để biết. Vì tất cả các số chẵn đều là bội của 2 nên 2 là số nguyên tố chẵn duy nhất có thể. Ngoài ra, phép nhân hai số nguyên tố sẽ dẫn đến một số chỉ có ước là 1, chính nó và hai số nguyên tố đã được nhân. (Ví dụ, nhân các số nguyên tố 3 và 7 cho kết quả là 21, chỉ có các ước là 1, 21, 3 và 7. ) Các số nguyên không phải là số nguyên tố được gọi là hợp số vì chúng bao gồm ít nhất hai thừa số ngoài 1 và số. Mọi hợp số đều có một thừa số nguyên tố, là một thừa số chỉ bao gồm các số nguyên tố. Ví dụ: hợp số 1386 gồm các số nguyên tố 2, 3, 7, 11 vì 2 × 3 × 3 × 7 × 11 = 1386. Thừa số nguyên tố của mỗi hợp số là duy nhất cho hợp số đó Chúng tôi sẽ sử dụng thông tin này về những gì tạo nên một số nguyên tố để viết một mô-đun có thể xác định xem một số nhỏ có phải là số nguyên tố hay không và tạo ra các số nguyên tố. Mô-đun, primeNum. py, sẽ xác định các chức năng sau isPrimeTrialDiv() sử dụng thuật toán chia thử để trả về True nếu số được truyền cho nó là số nguyên tố hoặc Sai nếu số được truyền cho nó không phải là số nguyên tố primeSieve() sử dụng sàng của thuật toán Eratosthenes để tạo ra các số nguyên tố rabinMiller() sử dụng thuật toán Rabin-Miller để kiểm tra xem số truyền cho nó có phải là số nguyên tố hay không. Thuật toán này, không giống như thuật toán chia thử, có thể hoạt động nhanh chóng trên các số rất lớn. Chức năng này không được gọi trực tiếp mà là bởi isPrime() isPrime() được gọi khi người dùng phải xác định xem một số nguyên lớn có phải là số nguyên tố hay không generateLargePrime() trả về một số nguyên tố lớn dài hàng trăm chữ số. Chức năng này sẽ được sử dụng trong makePublicPrivateKeys. chương trình py trong Mã nguồn cho mô-đun số nguyên tốGiống như mật mã. py, được giới thiệu trong , primeNum. chương trình py được các chương trình khác nhập dưới dạng mô-đun và không làm bất cứ điều gì khi tự chạy. Số nguyên tố. mô-đun py nhập mô-đun ngẫu nhiên và toán học của Python để sử dụng khi tạo số nguyên tố Mở cửa sổ chỉnh sửa tệp mới bằng cách chọn Tệp▸Tệp mới. Nhập mã sau vào trình chỉnh sửa tệp và sau đó lưu nó dưới dạng primeNum. py số nguyên tố. py 1. # sàng số nguyên tố Chạy mẫu mô-đun số nguyên tốĐể xem đầu ra mẫu của primeNum. py, hãy nhập thông tin sau vào trình bao tương tác >>> nhập số nguyên tố Nhập số nguyên tố. mô-đun py cho phép chúng tôi tạo một số nguyên tố rất lớn bằng cách sử dụng hàm generateLargePrime(). Nó cũng cho phép chúng ta chuyển bất kỳ số nào, dù lớn hay nhỏ, cho hàm isPrime() để xác định xem đó có phải là số nguyên tố hay không Thuật toán phân chia dùng thử hoạt động như thế nàoĐể biết một số đã cho có phải là số nguyên tố hay không ta sử dụng thuật toán chia thử. Thuật toán tiếp tục chia một số cho các số nguyên (bắt đầu bằng 2, 3, v.v.) để xem liệu có số nào trong số đó chia đều số có 0 là số dư không. Ví dụ: để kiểm tra xem 49 có phải là số nguyên tố hay không, chúng ta có thể thử chia nó cho các số nguyên bắt đầu bằng 2 49 ÷ 2 = 24 dư 1 49 ÷ 3 = 16 dư 1 49 ÷ 4 = 12 dư 1 49 ÷ 5 = 9 dư 4 49 ÷ 6 = 8 dư 1 49 ÷ 7 = 7 dư 0 Vì 7 chia hết cho 49 dư 0 nên ta biết 7 là thừa số của 49. Điều này có nghĩa là 49 không thể là số nguyên tố vì nó có ít nhất một ước khác 1 và chính nó Chúng ta có thể xúc tiến quá trình này bằng cách chỉ chia cho số nguyên tố, không chia cho hợp số. Như đã đề cập trước đó, hợp số không gì khác hơn là hợp số của các số nguyên tố. Điều này có nghĩa là nếu 2 không thể chia hết cho 49, thì một hợp số chẳng hạn như 6, có các thừa số bao gồm 2, cũng sẽ không thể chia hết cho 49. Nói cách khác, bất kỳ số nào chia hết cho 6 cũng có thể chia hết cho 2, vì 2 là thừa số của 6. minh họa khái niệm này Hình 22-1. Số nào chia hết cho 6 thì cũng chia hết cho 2 Một ví dụ khác, hãy kiểm tra xem 13 có phải là số nguyên tố không 13 ÷ 2 = 6 dư 1 13 ÷ 3 = 4 dư 1 Chúng tôi chỉ phải kiểm tra các số nguyên lên đến (và bao gồm) căn bậc hai của số mà chúng tôi đang kiểm tra tính nguyên tố. Căn bậc hai của một số là số mà khi nhân với chính nó thì được số ban đầu. Ví dụ, căn bậc hai của 25 là 5 vì 5 × 5 = 25. Vì một số không thể có hai thừa số lớn hơn căn bậc hai của nó, nên chúng ta có thể giới hạn phép thử của thuật toán chia thử đối với các số nguyên nhỏ hơn căn bậc hai của số đó. Căn bậc hai của 13 là khoảng 3. 6 nên ta chỉ cần chia 2 và 3 là biết 13 là số nguyên tố Một ví dụ khác, số 16 có căn bậc hai là 4. Nhân hai số lớn hơn 4 sẽ luôn dẫn đến một số lớn hơn 16 và bất kỳ thừa số nào của 16 lớn hơn 4 sẽ luôn được ghép với các thừa số nhỏ hơn 4, chẳng hạn như 8 × 2. Do đó, bạn sẽ tìm thấy tất cả các thừa số lớn hơn căn bậc hai bằng cách tìm bất kỳ thừa số nào nhỏ hơn căn bậc hai Để tìm căn bậc hai của một số trong Python, bạn có thể sử dụng phép toán. hàm sqrt(). Nhập nội dung sau vào trình bao tương tác để xem một số ví dụ về cách chức năng này hoạt động >>> nhập toán Chú ý rằng toán học. sqrt() luôn trả về giá trị dấu phẩy động Triển khai Thử nghiệm Thuật toán Phân chia Thử nghiệmHàm isPrimeTrialDiv() trên dòng 7 trong primeNum. py lấy một số làm tham số num và sử dụng phép thử thuật toán chia thử để kiểm tra xem số đó có phải là số nguyên tố không. Hàm trả về Sai nếu num là hợp số và True nếu num là số nguyên tố 7. def isPrimeTrialDiv(num) Dòng 13 kiểm tra xem số có nhỏ hơn 2 không, nếu đúng thì hàm trả về Sai, vì số nhỏ hơn 2 không thể là số nguyên tố Dòng 17 bắt đầu vòng lặp for thực hiện thuật toán chia thử. Nó cũng lấy căn bậc hai của num bằng toán học. sqrt() và sử dụng giá trị dấu phẩy động được trả về để đặt giới hạn trên của phạm vi số nguyên mà chúng tôi sẽ kiểm tra 16. # Xem num có chia hết cho bất kỳ số nào đến căn bậc hai của num không Dòng 18 kiểm tra xem phần còn lại có phải là 0 hay không bằng toán tử mod (%). Nếu phần còn lại là 0, num chia hết cho i và do đó không phải là số nguyên tố và vòng lặp trả về Sai. Nếu vòng lặp for ở dòng 17 không bao giờ trả về Sai, thì hàm trả về True ở dòng 20 để cho biết num có thể là số nguyên tố Thuật toán chia thử trong hàm isPrimeTrialDiv() rất hữu ích, nhưng đó không phải là cách duy nhất để kiểm tra tính nguyên tố. Bạn cũng có thể tìm các số nguyên tố bằng sàng của Eratosthenes Sàng của EratosthenesSàng Eratosthenes (phát âm là “era-taws-thuh-knees”) là một thuật toán tìm tất cả các số nguyên tố trong một dãy số. Để xem thuật toán này hoạt động như thế nào, hãy tưởng tượng một nhóm hộp. Mỗi hộp chứa một số nguyên từ 1 đến 50, tất cả được đánh dấu là số nguyên tố, như minh họa trong Để thực hiện sàng Eratosthenes, chúng tôi loại bỏ các số không phải là số nguyên tố khỏi phạm vi của chúng tôi cho đến khi chỉ còn lại các số nguyên tố. Vì 1 không bao giờ là số nguyên tố nên hãy bắt đầu bằng cách đánh dấu số 1 là “không phải số nguyên tố. ” Sau đó, hãy đánh dấu tất cả các bội số của hai (trừ 2) là “không phải là số nguyên tố. ” Điều này có nghĩa là chúng ta sẽ đánh dấu các số nguyên 4 (2 × 2), 6 (2 × 3), 8 (2 × 4), 10, 12, v.v. cho đến 50 là “không phải số nguyên tố”, như minh họa trong Hình 22-2. Thiết lập sàng Eratosthenes cho các số từ 1 đến 50 Hình 22-3. Loại bỏ số 1 và tất cả các số chẵn Sau đó, chúng tôi lặp lại quy trình bằng cách sử dụng bội số của ba. chúng tôi loại trừ 3 và đánh dấu 6, 9, 12, 15, 18, 21, v.v. là “không phải số nguyên tố. ” Chúng tôi lặp lại quy trình này cho các bội số của 4 trừ 4, các bội số của 5 trừ 5, v.v. cho đến khi chúng tôi vượt qua các bội số của 8. Chúng tôi dừng lại ở 8 vì nó lớn hơn 7. 071, là căn bậc hai của 50. Tất cả các bội số của 9, 10, 11, v.v. sẽ được đánh dấu sẵn, bởi vì bất kỳ số nào là thừa số lớn hơn căn bậc hai sẽ được ghép với một thừa số nhỏ hơn căn bậc hai mà chúng ta đã đánh dấu Sàng hoàn thành sẽ trông như thế nào, với các số nguyên tố được hiển thị trong hộp màu trắng Hình 22-4. Các số nguyên tố được tìm thấy bằng sàng của Eratosthenes Sử dụng sàng của Eratosthenes, chúng tôi thấy rằng các số nguyên tố nhỏ hơn 50 là 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43 và 47. Thuật toán sàng này dùng tốt nhất khi muốn tìm nhanh tất cả các số nguyên tố trong một dãy số nào đó. Nó nhanh hơn nhiều so với việc sử dụng thuật toán chia thử trước đó để kiểm tra từng số riêng lẻ Tạo số nguyên tố bằng sàng EratosthenesHàm primeSieve() trên dòng 23 của primeNum. mô-đun py sử dụng sàng của thuật toán Eratosthenes để trả về danh sách tất cả các số nguyên tố trong khoảng từ 1 đến sàngSize 23. def primeSieve(SizeSize) Dòng 27 tạo danh sách các giá trị Boolean True đại diện cho độ dài của sàngSize. Các chỉ số 0 và 1 được đánh dấu là Sai vì 0 và 1 không phải là số nguyên tố Vòng lặp for trên dòng 32 đi qua từng số nguyên từ 2 đến căn bậc hai của sàngSize 31. # Tạo sàng Con trỏ biến bắt đầu ở bội số đầu tiên của i sau i, là i * 2 trên dòng 33. Sau đó, vòng lặp while đặt chỉ mục con trỏ trong danh sách sàng thành Sai và dòng 36 thay đổi con trỏ để trỏ tới bội số tiếp theo của i Sau khi vòng lặp for trên dòng 32 kết thúc, danh sách sàng bây giờ sẽ chứa True cho mỗi chỉ mục là số nguyên tố. Chúng tôi tạo một danh sách mới, danh sách này bắt đầu dưới dạng một danh sách trống ở dạng số nguyên tố, lặp qua toàn bộ danh sách sàng và nối các số khi sàng[i] là True hoặc khi tôi là số nguyên tố 38. # Tổng hợp danh sách các số nguyên tố Dòng 44 trả về danh sách các số nguyên tố 44. trả về số nguyên tố Hàm primeSieve() có thể tìm tất cả các số nguyên tố trong một phạm vi nhỏ và hàm isPrimeTrialDiv() có thể nhanh chóng xác định xem một số nhỏ có phải là số nguyên tố hay không. Nhưng còn một số nguyên lớn dài hàng trăm chữ số thì sao? Nếu chúng ta chuyển một số nguyên lớn cho isPrimeTrialDiv(), sẽ mất vài giây để xác định xem đó có phải là số nguyên tố hay không. Và nếu số đó dài hàng trăm chữ số, giống như các số nguyên tố mà chúng ta sẽ sử dụng cho chương trình mật mã khóa công khai trong Trong phần tiếp theo, bạn sẽ tìm hiểu cách xác định xem một số rất lớn có phải là số nguyên tố hay không bằng phép kiểm tra tính nguyên tố Rabin-Miller Thuật toán nguyên tố Rabin-MillerLợi ích chính của thuật toán Rabin-Miller là nó là một bài kiểm tra tính nguyên tố tương đối đơn giản và chỉ mất vài giây để chạy trên máy tính bình thường. Mặc dù mã Python của thuật toán chỉ dài vài dòng, nhưng phần giải thích bằng chứng toán học về lý do tại sao nó hoạt động sẽ quá dài đối với cuốn sách này. Thuật toán Rabin-Miller không phải là phép thử chắc chắn cho tính nguyên tố. Thay vào đó, nó tìm các số rất có khả năng là số nguyên tố nhưng không đảm bảo là số nguyên tố. Nhưng khả năng xảy ra dương tính giả là đủ nhỏ để phương pháp này đủ tốt cho mục đích của cuốn sách này. Để tìm hiểu thêm về cách thức hoạt động của thuật toán Rabin-Miller, bạn có thể đọc về nó tại https. // vi. wikipedia. org/wiki/Miller-Rabin_primality_test Hàm rabinMiller() thực hiện thuật toán này để tìm các số nguyên tố 46. def rabinMiller(num) Đừng lo lắng về cách mã này hoạt động. Khái niệm quan trọng cần ghi nhớ là nếu hàm rabinMiller() trả về True, thì đối số num rất có thể là số nguyên tố. Nếu rabinMiller() trả về Sai, num chắc chắn là hợp số Tìm Số Nguyên Tố LớnChúng ta sẽ tạo một hàm khác có tên là isPrime() sẽ gọi rabinMiller(). Thuật toán Rabin-Miller không phải lúc nào cũng là cách hiệu quả nhất để kiểm tra xem một số có phải là số nguyên tố hay không; . Hãy lưu trữ danh sách tất cả các số nguyên tố nhỏ hơn 100 trong biến hằng số LOW_PRIMES. Chúng ta có thể sử dụng hàm primeSieve() để tính danh sách này 72. # Hầu hết thời gian chúng ta có thể nhanh chóng xác định xem num có phải là số nguyên tố hay không Chúng tôi sẽ sử dụng danh sách này giống như chúng tôi đã làm trong isPrimeTrialDiv() và chiết khấu bất kỳ số nào nhỏ hơn 2 (dòng 81 và 82) 78. def isPrime(num) Khi num không nhỏ hơn 2, chúng ta cũng có thể sử dụng danh sách LOW_PRIMES làm lối tắt để kiểm tra num. Việc kiểm tra xem num có chia hết cho tất cả các số nguyên tố nhỏ hơn 100 hay không sẽ không cho chúng ta biết chắc chắn số đó có phải là số nguyên tố hay không, nhưng nó có thể giúp chúng ta tìm các hợp số. Khoảng 90 phần trăm số nguyên lớn được chuyển đến isPrime() có thể được phát hiện dưới dạng hợp số bằng cách chia cho các số nguyên tố nhỏ hơn 100. Lý do là nếu một số có thể chia hết cho một số nguyên tố, chẳng hạn như 3, bạn không cần phải kiểm tra xem số đó có thể chia hết cho các hợp số 6, 9, 12, 15 hay bất kỳ bội số nào khác của . Chia số cho các số nguyên tố nhỏ hơn sẽ nhanh hơn nhiều so với việc thực hiện thuật toán Rabin-Miller chậm hơn trên số đó, do đó, phím tắt này giúp chương trình thực hiện nhanh hơn khoảng 90 phần trăm thời gian isPrime() được gọi Dòng 85 lặp qua từng số nguyên tố trong danh sách LOW_PRIMES 83. # Xem có số nguyên tố thấp nào chia hết cho num không Nếu số nguyên trong num giống số nguyên tố thì hiển nhiên num phải là số nguyên tố và dòng 86 trả về True. Số nguyên trong num được sửa đổi theo từng số nguyên tố bằng cách sử dụng toán tử mod trên dòng 87 và nếu kết quả ước tính bằng 0, chúng ta biết rằng số nguyên tố chia hết cho num nên num không phải là số nguyên tố. Trong trường hợp đó, dòng 88 trả về Sai Đó là ba phép kiểm tra nhanh mà chúng ta sẽ thực hiện để xác định xem một số có phải là số nguyên tố hay không. Nếu quá trình thực thi tiếp tục qua dòng 87, hàm rabinMiller() sẽ kiểm tra tính nguyên thủy của num Dòng 90 gọi hàm rabinMiller() để xác định xem số đó có phải là số nguyên tố hay không; 89. # Nếu vẫn thất bại, hãy gọi rabin Miller() để xác định xem số đó có phải là số nguyên tố không Bây giờ bạn đã biết cách xác định xem một số có phải là số nguyên tố hay không, chúng ta sẽ sử dụng các phép kiểm tra tính nguyên tố này để tạo số nguyên tố. Chúng sẽ được sử dụng bởi chương trình khóa công khai trong Tạo số nguyên tố lớnSử dụng vòng lặp vô hạn, hàm generateLargePrime() ở dòng 93 trả về một số nguyên tố. Nó thực hiện điều này bằng cách tạo một số ngẫu nhiên lớn, lưu trữ nó trong num, sau đó chuyển num tới isPrime(). Hàm isPrime() sau đó kiểm tra xem num có phải là số nguyên tố hay không 93. def generateLargePrime(keysize=1024) Nếu num là số nguyên tố, dòng 98 trả về num. Nếu không, vòng lặp vô hạn quay lại dòng 96 để thử một số ngẫu nhiên mới. Vòng lặp này tiếp tục cho đến khi nó tìm thấy một số mà hàm isPrime() xác định là số nguyên tố Tham số keysize của hàm generateLargePrime() có giá trị mặc định là 1024. Kích thước khóa càng lớn, càng có nhiều khóa khả thi và mật mã càng khó bị brute-force. Kích thước khóa công khai thường được tính theo số gọi là bit, bạn sẽ tìm hiểu thêm về điều này trong và. Hiện tại, chỉ cần biết rằng một con số 1024 bit là rất lớn. đó là khoảng 300 chữ số Bản tóm tắtSố nguyên tố có những tính chất hấp dẫn trong toán học. Như bạn sẽ tìm hiểu trong , chúng cũng là xương sống của mật mã được sử dụng trong phần mềm mã hóa chuyên nghiệp. Định nghĩa của một số nguyên tố là đủ đơn giản. là số chỉ có 1 và chính nó là thừa số. Nhưng việc xác định số nào là số nguyên tố cần một số mã thông minh Trong chương này, chúng ta đã viết hàm isPrimeTrialDiv() để xác định xem một số có phải là số nguyên tố hay không bằng cách thay đổi một số thành tất cả các số nằm trong khoảng từ 2 đến căn bậc hai của số đó. Đây là thuật toán chia thử. Một số nguyên tố không bao giờ được có số dư bằng 0 khi được sửa đổi bởi bất kỳ số nào ngoài các thừa số của nó, 1 và chính nó. Vì vậy, chúng tôi biết rằng một số có số dư 0 không phải là số nguyên tố Bạn đã biết rằng sàng của Eratosthenes có thể nhanh chóng tìm thấy tất cả các số nguyên tố trong một dãy số, mặc dù nó sử dụng quá nhiều bộ nhớ để tìm các số nguyên tố lớn Vì sàng của Eratosthenes và thuật toán chia thử trong số nguyên tố. py không đủ nhanh để tìm các số nguyên tố lớn, chúng tôi cần một thuật toán khác cho mật mã khóa công khai, thuật toán này sử dụng các số nguyên tố cực lớn dài hàng trăm chữ số. Như một giải pháp thay thế, bạn đã học cách sử dụng thuật toán Rabin-Miller, sử dụng suy luận toán học phức tạp để xác định xem một số rất lớn có phải là số nguyên tố hay không Trong , bạn sẽ sử dụng primeNum. mô-đun py để viết chương trình mật mã khóa công khai. Cuối cùng, bạn sẽ tạo ra một mật mã dễ sử dụng hơn so với mật mã dùng một lần nhưng không thể bị tấn công bởi các kỹ thuật hacker đơn giản được giới thiệu trong cuốn sách này Hàm tạo số nguyên tố ngẫu nhiên trong Python là gì?randint(p,q) với ngẫu nhiên. randint(p,q). 1 - điều này làm cho mã hiệu quả gấp đôi, nhưng loại bỏ khả năng kết quả sẽ là 2.
Có cách nào để tạo số nguyên tố không?Trong lý thuyết số tính toán, nhiều thuật toán giúp tạo ra các số nguyên tố một cách hiệu quả . Chúng được sử dụng trong các ứng dụng khác nhau, ví dụ như băm, mật mã khóa công khai và tìm kiếm các thừa số nguyên tố với số lượng lớn.
Làm thế nào để RSA tạo ra các số nguyên tố?RSA dựa vào sự dễ dàng tương đối trong việc tìm các số nguyên tố lớn và độ khó so sánh của việc phân tích các số nguyên để bảo mật . Để sử dụng hệ thống này, trước tiên chúng ta tìm hai số nguyên tố lớn p và q và lập tích của chúng n = pq. Tiếp theo, chúng ta chọn một số nguyên ngẫu nhiên e nguyên tố cùng nhau với (p-1)( q-1) (đây là phi(n)). |
