涉及知识点

光滑数：指能分解成小素数乘积的正整数

B-光滑数：若一个光滑数的最大小质数因子<=B,则称该光滑数为B-光滑数

费马小定理:

image

p-1光滑

image

由于p为质数，设a为整数且与p互质，则有

image

又因为p-1为因子互不相同的B-光滑数，所以

image

故p的倍数可以求出来，且我们有n=p*q。所以

image

Pollard’s p-1

由于我们只关注gcd的结果，不需要计算B！的值，我们只需要令B=1，2，3，…,计算出gcd结果即可

1
2
3
4
5
6
7
8
9
10
11
12
13
from gmpy2 import *
a = 2
n = 2
while True:
    a = powmod(a, n, N)
    res = gcd(a-1, N)
    if res != 1 and res != N:
        q = N // res
        d = invert(e, (res-1)*(q-1))
        m = powmod(c, d, N)
        print(m)
        break
    n += 1

p+1光滑

Williams’s p + 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def mlucas(v, a, n):
    """ Helper function for williams_pp1().  Multiplies along a Lucas sequence modulo n. """
    v1, v2 = v, (v**2 - 2) % n
    for bit in bin(a)[3:]: 
        v1, v2 = ((v1**2 - 2) % n, (v1*v2 - v) % n) if bit == "0" else ((v1*v2 - v) % n, (v2**2 - 2) % n)
    return v1

for v in count(1):
    for p in primegen():
        e = ilog(isqrt(n), p)
        if e == 0: 
            break
        for _ in xrange(e): 
            v = mlucas(v, p, n)
        g = gcd(v-2, n)
        if 1 < g < n: 
            return g # g|n
        if g == n: 
            break