我正在尝试用Python实现Pollard的P-1分解。请注意，Rho方法有一些答案，但这个p-1是不同的，我能在这里给你的关于p-1的最好的是wiki和Wolfram：
http://en.wikipedia.org/wiki/Pollard's_p_％E2％88％92_1_algorithm
http://mathworld.wolfram.com/Pollardp-1FactorizationMethod.html
这是n的因素，但始终没有找到p。 np和sp分别来自numpy和scipy。因此，sp.uint64的内置函数是无符号long 64 int（因为预期整数的大小），而np.prod（p）是列表p的累积乘积pi：
def pm1_attack(n,b):
p = [2,3,5,7,11,13,17]; i=19; a=2
while i<b:
if is_prime(i,10): p.append(i)
i+=2;
k = sp.uint64(np.prod(p)); q = power2(a,k,n)
g = euc_al_i((q-1),n)
print "product pi: ",k
print "q: ",q
print "g: ",g
#return a
print "pollard_pm1_attack(n,b): ",pollard_pm1_attack(n,2000)
输出找不到p：
Python 2.7 (r27:82525, Jul 4 2010, 09:01:59) [MSC v.1500 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>>
p = 1300199
q = 2063507
euler_totient = 2682966374188
common n = 2682969737893
public key e = 1588051820871
secret key d = 2410616084843
cleartext message = test
encoded message = 1489995542681
decoded message = test
check_rsa = Successful encryption and decrytion. Message is authenticated.
pollard_pm1_attack(n,b): product pi: 18446744073460481730
q: 2391570546599
g: 1
None
>>>
我正在学习Python，所以这可能是一个简单的错误。 power2（）函数通过平方使用取幂，对于非常大的整数，它基本上是一个超级充电的pow（）。 euc_al_i（）只是gcd。你可以使用你喜欢的任何gcd（），但是因为我正在学习我想自己制作这些。
我试图找出在这里发生了如此可怕的错误，即使从相对较小的n（小到20位长度）也找不到p。
我不知道np.prod和sp.uint64是做什么的，但我可以告诉你关于p-1算法，这是由John Pollard于1974年发明的。
Pollard的算法基于费马的小定理a ^ p == a（mod p），当a！= 0时，可以通过将a除以表达式来表示a ^（p-1）== 1（mod p）。因此，如果p - 1除以m，则p除以gcd（2 ^ m - 1，n）。 Pollard的p - 1算法将m计算为小于b的整数的最小公倍数，因此如果p - 1的所有因子都小于b，那么gcd（2 ^ lcm（1..b） - 1 ，n）是n的因子。通过将小于b的素数乘以小于b的多重性来计算最小公倍数：
function pminus1(n, b)
c := 2
for p in primes(b)
pp := p
while pp < b
c := powerMod(c, p, n)
pp := pp * p
g := gcd(c-1, n)
if 1 < g < n return g
error "factorization failed"
可选的第二阶段在b1和b2之间搜索“大素数”，其与第一阶段的最小公倍数组合以找到因子。第二阶段只需要每个素数的模乘，而不是模幂运算，使其非常快，第二阶段gcds可以分批计算。缓存很小但对功能的效率很重要。
function pminus1(n, b1, b2)
c := 2
for p in primes(b1)
pp := p
while pp < b
c := powerMod(c, p, n)
pp := pp * p
g := gcd(c-1, n)
if 1 < g < n return g
k := 0
for q in primes(b1, b2)
d := q - p
if d is not in cache
x := powerMod(c, d, n)
store d, x in cache
c := (c * x(d)) % n
p := q
k := k + 1
if k % 100 == 0
g := gcd(c-1, n)
if 1 < g < n return g
g := gcd(c-1, n)
if 1 < g < n return g
error "factorization failed"
Pollard的p - 1方法可能无法找到n的因子;它取决于n - 1的因子分解和你选择的界限。检查的方法是自己考虑因子n - 1，然后调用Pollard的方法，其中ab大于n - 1的最大因子。例如，如果你想要因子n = 87463 = 149 * 587，请注意n - 1 = 87462 = 2 * 3 * 3 * 43 * 113，所以调用b = 120的一阶段算法或b1 = 50和b2 = 120的两阶段算法，看看你是否找到了一个因子。
我在my blog讨论了Pollard的p - 1分解算法以及其他几种分解算法。我还给出了powerMod和gcd函数的实现，以防你在执行这些函数时遇到问题。我在http://ideone.com/wdyjxK上用Python编写了一个简单的单阶段算法实现。
这是在python中实现的两阶段版本。
from math import gcd, log
def pminus1(n, B1, B2):
log_B1 = log(B1)
M = 1
primes = prime_sieve()
for p in primes:
if p > B1:
break
M *= p**int(log_B1/log(p))
M = pow(2, M, n)
g = gcd(M-1, n)
if 1 < g < n:
return True
if g == n:
return False
# Start part 2.
cache = {0:M}
S = (M*M) % n
for d in range(2, int(log(B2)**2), 2):
cache[d] = cache[d-2] * S) % n
HQ = M
for k, q in enumerate(primes):
if q > B2:
break
d = q - p
HQ = (HQ * cache[d]) % n
M = (M * (HQ-1)) % n
p = q
if k % 200 == 0:
if 1 < gcd(M, n) < n:
return True
return 1 < gcd(M, n) < n