如何模块化质因数分解 Python 脚本以将列表作为输入？
How do I modularize a prime factorization Python script to take in a list as input?
我有可用的 Python 代码（如下），它可以破解 RSA 密钥并乘以质因数分解。我如何将此代码放入一个模块中，该模块采用表示 n 的整数列表来创建范围为 0...2^n 的 n 位素数？我想传入一个整数列表和 return 个 n 值的 table 和 运行 次，如下所示：
n run time
15 0.2
16 1.1
17 1.4
18 10.6
19 30.2
20 46.6
代码：
import random
import math
import timeit
while True:
try:
n = input("Please enter a number n for creating an n-bit prime number for range 0...2^n: ")
n = int(n)
break
except ValueError:
print('\nPlease enter an integer value.')
def isPrime(m):
for i in range(2, m//2, 1):
if m % i == 0:
return False
return True
def nBitPrime(n):
r = random.random()
m = int(r * (2**n))
if m >= 2 and isPrime(m) == True:
return m
return nBitPrime(n)
def getPQ(n):
pq = nBitPrime(n) * nBitPrime(n)
return pq
pq = getPQ(n)
def factor(pq):
p = math.floor(math.sqrt(getPQ(n)))
if p % 2 == 0:
p += 1
while p < pq:
if pq % p == 0:
return p, int(pq/p)
p += 2
def wrapper(func,*args):
def wrapped():
return func(*args)
return wrapped
wrapped = wrapper(factor, n)
speed = (timeit.timeit(wrapped, number=1))*1000
print(round(speed, 4))
提前致谢。
这里有几个问题。首先，您的 factor 函数重新生成一个新的 pq 值，忽略您之前生成的值。这样就计算了两次获取pq的时间。此外，测量使用随机数生成器的进程的单次执行时间并不能使您很好地了解性能。您需要运行几次才能获得平均值。
我稍微清理了你的代码并更改了测量时间的方式以获得超过 100 次运行的平均值：
您的代码：
import random
import math
import timeit
def isPrime(m):
for i in range(2, m//2, 1):
if m % i == 0:
return False
return True
def nBitPrime(n):
r = random.random()
m = int(r * (2**n))
if m >= 2 and isPrime(m) == True:
return m
return nBitPrime(n)
def getPQ(n):
pq = nBitPrime(n) * nBitPrime(n)
return pq
def factor(pq):
p = math.floor(math.sqrt(pq))
if p % 2 == 0:
p += 1
while p < pq:
if pq % p == 0:
return p, int(pq/p)
p += 2
while True:
try:
n = input("Please enter a number n for creating an n-bit prime number for range 0...2^n: ")
n = int(n)
time = timeit.timeit(lambda:factor(getPQ(n)), number=100)
print(f"{time*10:.4f}")
except ValueError:
print('\nPlease enter an integer value.')
除了简单的代码优化之外，使用素数生成器和素数列表会大大加快速度。
以下是相同函数的示例实现，以更高效和 Pythonic 的方式，帮助您自己制作更好的函数：
素数生成（根据需要）
primes = [2,3]
primeSkip = {9:3}
# fill primes list up to the square root of N
def morePrimes(N):
lastPrime = primes[-1]
while lastPrime*lastPrime<N:
lastPrime += 2
if lastPrime not in primeSkip:
primeSkip[lastPrime*lastPrime] = lastPrime
primes.append(lastPrime)
continue
prime = primeSkip.pop(lastPrime)
multiple = lastPrime + 2*prime
while multiple in primeSkip: multiple += 2*prime
primeSkip[multiple] = prime
主要测试
# prime test uses the known prime list as a search mechanism
# and only checks divisions for primes when a larger number is given
from bisect import bisect_left
def isPrime(N):
if N<=primes[-1]:
return primes[bisect_left(primes,N)] == N
morePrimes(N)
for p in primes:
if N%p == 0: return False
if p*p>N: return True
return True
随机n位素数
# non-recursive implementation (faster than recursive)
# also uses randrange() to get the appropriate values without multiplication
# and floating point arithmetics
def nBitPrime(n):
p = random.randrange(2,2**n)
while not isPrime(p):
p = random.randrange(2,2**n)
return p
分解
# factorisation uses primes going backward from the square root of pq
# given that p and q are supposed to be large primes, this should converge
# faster to the two factors.
def factor(pq):
morePrimes(pq)
i = bisect_left(primes,int(pq**0.5)+1)
i = min(i,len(primes)-1)
while i>0:
p = primes[i]
if pq%p == 0: return p,pq//p
i -= 1
试运行
Your original code (cleaned up):
Please enter a number n for creating an n-bit prime number for range 0...2^n: 10
0.0531
Please enter a number n for creating an n-bit prime number for range 0...2^n: 15
1.2645
Please enter a number n for creating an n-bit prime number for range 0...2^n: 20
38.0535
...
# With the improved functions
Please enter a number n for creating an n-bit prime number for range 0...2^n: 10
0.0359
Please enter a number n for creating an n-bit prime number for range 0...2^n: 15
0.2044
Please enter a number n for creating an n-bit prime number for range 0...2^n: 20
3.76593
基于质数的函数有一些开销抵消了较小位大小的好处，但它们在高端
上提供了显着的改进
其他注意事项
您为 p 和 q 生成的值不符合通常用于 select 它们的标准。它们必须是彼此相距足够远的大素数。纯随机生成将产生易于因式分解的 pq 弱值（尽管低于 32 位，基于素数的因式分解将很快找到它们）
这个可能会好一点：
def getPQ(n):
p = random.randrange(2**(n-4),2**(n-2))
while not isPrime(p):
p = random.randrange(2**(n-4),2**(n-2))
q = random.randrange(p*2,2**n)
while not isPrime(q):
q = random.randrange(p*2,2**n)
return p*q
将因式分解时间与随机 pq 生成分开测量也是一个好主意。您的破解函数通常用于现有密钥，因此生成 pq 已经预先完成以生成密钥。这将突出显示 factor() 函数的实现与基于素数的函数之间的巨大性能差异。
while True:
try:
n = input("Please enter a number n for creating an n-bit prime number for range 0...2^n: ")
n = int(n)
pq = getPQ(n)
print("pq",pq) # exclude this from time measurement
time = timeit.timeit(lambda:factor(pq), number=100)
print(f"{time*10:.4f}")
except ValueError:
print('\nPlease enter an integer value.')
仅测试 factor() 函数性能：
# Your code:
Please enter a number n for creating an n-bit prime number for range 0...2^n: 20
pq 78161507029
4.5724
Please enter a number n for creating an n-bit prime number for range 0...2^n: 20
pq 414308573933
17.8163
Please enter a number n for creating an n-bit prime number for range 0...2^n: 20
pq 192833207923
14.7995
...
# Prime based:
Please enter a number n for creating an n-bit prime number for range 0...2^n: 20
pq 36909677657
1.9210
Please enter a number n for creating an n-bit prime number for range 0...2^n: 20
pq 62575471813
1.1313
Please enter a number n for creating an n-bit prime number for range 0...2^n: 20
pq 761609512621
1.5924
我有可用的 Python 代码（如下），它可以破解 RSA 密钥并乘以质因数分解。我如何将此代码放入一个模块中，该模块采用表示 n 的整数列表来创建范围为 0...2^n 的 n 位素数？我想传入一个整数列表和 return 个 n 值的 table 和 运行 次，如下所示：
n run time
15 0.2
16 1.1
17 1.4
18 10.6
19 30.2
20 46.6
代码：
import random
import math
import timeit
while True:
try:
n = input("Please enter a number n for creating an n-bit prime number for range 0...2^n: ")
n = int(n)
break
except ValueError:
print('\nPlease enter an integer value.')
def isPrime(m):
for i in range(2, m//2, 1):
if m % i == 0:
return False
return True
def nBitPrime(n):
r = random.random()
m = int(r * (2**n))
if m >= 2 and isPrime(m) == True:
return m
return nBitPrime(n)
def getPQ(n):
pq = nBitPrime(n) * nBitPrime(n)
return pq
pq = getPQ(n)
def factor(pq):
p = math.floor(math.sqrt(getPQ(n)))
if p % 2 == 0:
p += 1
while p < pq:
if pq % p == 0:
return p, int(pq/p)
p += 2
def wrapper(func,*args):
def wrapped():
return func(*args)
return wrapped
wrapped = wrapper(factor, n)
speed = (timeit.timeit(wrapped, number=1))*1000
print(round(speed, 4))
提前致谢。
这里有几个问题。首先，您的 factor 函数重新生成一个新的 pq 值，忽略您之前生成的值。这样就计算了两次获取pq的时间。此外，测量使用随机数生成器的进程的单次执行时间并不能使您很好地了解性能。您需要运行几次才能获得平均值。
我稍微清理了你的代码并更改了测量时间的方式以获得超过 100 次运行的平均值：
您的代码：
import random
import math
import timeit
def isPrime(m):
for i in range(2, m//2, 1):
if m % i == 0:
return False
return True
def nBitPrime(n):
r = random.random()
m = int(r * (2**n))
if m >= 2 and isPrime(m) == True:
return m
return nBitPrime(n)
def getPQ(n):
pq = nBitPrime(n) * nBitPrime(n)
return pq
def factor(pq):
p = math.floor(math.sqrt(pq))
if p % 2 == 0:
p += 1
while p < pq:
if pq % p == 0:
return p, int(pq/p)
p += 2
while True:
try:
n = input("Please enter a number n for creating an n-bit prime number for range 0...2^n: ")
n = int(n)
time = timeit.timeit(lambda:factor(getPQ(n)), number=100)
print(f"{time*10:.4f}")
except ValueError:
print('\nPlease enter an integer value.')
除了简单的代码优化之外，使用素数生成器和素数列表会大大加快速度。
以下是相同函数的示例实现，以更高效和 Pythonic 的方式，帮助您自己制作更好的函数：
素数生成（根据需要）
primes = [2,3]
primeSkip = {9:3}
# fill primes list up to the square root of N
def morePrimes(N):
lastPrime = primes[-1]
while lastPrime*lastPrime<N:
lastPrime += 2
if lastPrime not in primeSkip:
primeSkip[lastPrime*lastPrime] = lastPrime
primes.append(lastPrime)
continue
prime = primeSkip.pop(lastPrime)
multiple = lastPrime + 2*prime
while multiple in primeSkip: multiple += 2*prime
primeSkip[multiple] = prime
主要测试
# prime test uses the known prime list as a search mechanism
# and only checks divisions for primes when a larger number is given
from bisect import bisect_left
def isPrime(N):
if N<=primes[-1]:
return primes[bisect_left(primes,N)] == N
morePrimes(N)
for p in primes:
if N%p == 0: return False
if p*p>N: return True
return True
随机n位素数
# non-recursive implementation (faster than recursive)
# also uses randrange() to get the appropriate values without multiplication
# and floating point arithmetics
def nBitPrime(n):
p = random.randrange(2,2**n)
while not isPrime(p):
p = random.randrange(2,2**n)
return p
分解
# factorisation uses primes going backward from the square root of pq
# given that p and q are supposed to be large primes, this should converge
# faster to the two factors.
def factor(pq):
morePrimes(pq)
i = bisect_left(primes,int(pq**0.5)+1)
i = min(i,len(primes)-1)
while i>0:
p = primes[i]
if pq%p == 0: return p,pq//p
i -= 1
试运行
Your original code (cleaned up):
Please enter a number n for creating an n-bit prime number for range 0...2^n: 10
0.0531
Please enter a number n for creating an n-bit prime number for range 0...2^n: 15
1.2645
Please enter a number n for creating an n-bit prime number for range 0...2^n: 20
38.0535
...
# With the improved functions
Please enter a number n for creating an n-bit prime number for range 0...2^n: 10
0.0359
Please enter a number n for creating an n-bit prime number for range 0...2^n: 15
0.2044
Please enter a number n for creating an n-bit prime number for range 0...2^n: 20
3.76593
基于质数的函数有一些开销抵消了较小位大小的好处，但它们在高端
上提供了显着的改进其他注意事项
您为 p 和 q 生成的值不符合通常用于 select 它们的标准。它们必须是彼此相距足够远的大素数。纯随机生成将产生易于因式分解的 pq 弱值（尽管低于 32 位，基于素数的因式分解将很快找到它们）
这个可能会好一点：
def getPQ(n):
p = random.randrange(2**(n-4),2**(n-2))
while not isPrime(p):
p = random.randrange(2**(n-4),2**(n-2))
q = random.randrange(p*2,2**n)
while not isPrime(q):
q = random.randrange(p*2,2**n)
return p*q
将因式分解时间与随机 pq 生成分开测量也是一个好主意。您的破解函数通常用于现有密钥，因此生成 pq 已经预先完成以生成密钥。这将突出显示 factor() 函数的实现与基于素数的函数之间的巨大性能差异。
while True:
try:
n = input("Please enter a number n for creating an n-bit prime number for range 0...2^n: ")
n = int(n)
pq = getPQ(n)
print("pq",pq) # exclude this from time measurement
time = timeit.timeit(lambda:factor(pq), number=100)
print(f"{time*10:.4f}")
except ValueError:
print('\nPlease enter an integer value.')
仅测试 factor() 函数性能：
# Your code:
Please enter a number n for creating an n-bit prime number for range 0...2^n: 20
pq 78161507029
4.5724
Please enter a number n for creating an n-bit prime number for range 0...2^n: 20
pq 414308573933
17.8163
Please enter a number n for creating an n-bit prime number for range 0...2^n: 20
pq 192833207923
14.7995
...
# Prime based:
Please enter a number n for creating an n-bit prime number for range 0...2^n: 20
pq 36909677657
1.9210
Please enter a number n for creating an n-bit prime number for range 0...2^n: 20
pq 62575471813
1.1313
Please enter a number n for creating an n-bit prime number for range 0...2^n: 20
pq 761609512621
1.5924