我一直在試圖用過去一週半的時間,沒有運氣的情況下用Python生成大質數來進行RSA加密。費馬原理性測試在512比特的尺度下是不可行的,我無法將我的頭圍繞米勒 - 拉賓。 (我13歲)所有在線腳本似乎都可以在我使用的Python版本下工作。我應該怎麼做才能生成大量素數? (是的,概率素數都很好。)生成大的(512位+)素數python 3.6
0
A
回答
1
這裏是我的米勒 - 拉賓總理檢查:
def isPrime(n, k=5): # miller-rabin
from random import randint
if n < 2: return False
for p in [2,3,5,7,11,13,17,19,23,29]:
if n % p == 0: return n == p
s, d = 0, n-1
while d % 2 == 0:
s, d = s+1, d/2
for i in range(k):
x = pow(randint(2, n-1), d, n)
if x == 1 or x == n-1: continue
for r in range(1, s):
x = (x * x) % n
if x == 1: return False
if x == n-1: break
else: return False
return True
如果你想保證黃金(不是可能的素數),這不是很更難安排。有關Pocklington的方法,請參見my blog。
+0
你知道你函數的準確率嗎? –
+1
這取決於* k *的值。如果你想減少錯誤的機會,使用更大的* k *。但對於512位數字,* k *就足夠了。如果你擔心錯誤發生的可能性,請使用我的博客中描述的Pocklington方法,該方法可以保證產生質數。 – user448810
相關問題
- 1. 使用probablePrime生成素數。 probablePrime(512,randomSeed);
- 2. Python素數生成器
- 3. python素數生成器的問題
- 4. 如何在Java中乘以兩個大數字(比如512位)
- 5. Matplotlib for Python 3.6 64位窗口
- 6. SHA1碰撞小於512位
- 7. CoffeeScript的素數生成
- 8. Java中小於512位的RSA密鑰大小
- 9. renderInContext無法渲染寬度大於512像素的UIView
- 10. 如何在Appcelerator中生成base64編碼的SHA-512哈希?
- 11. 創建一個生成給定大小的素數的方法
- 12. Python 3.6 memcached
- 13. 凍結Python 3.6
- 14. Python 3.6 SSL:CERTIFICATE_VERIFY_FAILED
- 15. 在Python 3.6
- 16. cx_freeze in python 3.6
- 17. Python 3.6 - Sanic Motorengine
- 18. cx_Oracle for Python 3.6
- 19. 在Python 3.6
- 20. Python生成Python
- 21. python:如何生成一個位圖?
- 22. Python生成隨機128位字符串
- 23. 的Python - 生成
- 24. 生成6位數字
- 25. 向Python生成器添加元素
- 26. 使用LINQ生成素數
- 27. XSLT生成元素基數
- 28. 下一個素數生成
- 29. 併發素數生成器
- 30. SHA256:填充512位長度的消息
對於您感興趣的大小的數字,Fermat素性測試應該是完全可行的。只要確定您使用的是3-arg版本的pow, 'pow(2,p-1,p)== 1' –