Williams's p+1 algorithm

Posted on Edited on In Word count in article: 2.3k Reading time ≈ 2 mins.

在计算数论中，Williams的p+1算法是一种整数分解算法，是代数群因子分解算法家族中的一种。它是Hugh C. Williams在1982年发明的。
如果要分解的数N包含一个或多个素数因子p，且p+1是光滑的(即p+1只包含小的因子)，那么Williams’s p+1有效。
Williams’s p+1使用Lucas序列在二次域中执行求幂运算。

它类似于Pollard的p−1算法。

算法原理

选择一个大于2的整数A来计算Lucas序列:


其中所有的运算都是模N的

当M是的倍数时，奇素数p整除，


是jacobi symbol

我们要求，即D应该是一个模p的二次的非剩余，但是由于我们不知道p，所以在找到解之前可能需要一个以上的A值。()

如果，则该算法退化为Pollard的p−1算法的慢版本。

因此，对于不同的M值，我们计算 ，当结果不等于1或N时，我们便找到了N的一个非平凡因子。

使用的M值是连续的阶乘，而 是以 为特征的序列的第M个值

为了找到以B为特征的序列的第M个元素V，我们以类似于从左到右求幂的方式进行计算:

1
2
3
4
5
6
7
8
9
10
x := B
y := ( B ^ 2 - 2 ) MOD N
for each bit of M to the right of the most significant bit do
	if the bit is 1 then
		x := ( x * y - B ) MOD N
		y := ( y ^ 2 - 2 ) MOD N
	else
		y := ( x ^ y - B ) MOD N
		x := ( x ^ 2 - 2 ) MOD N
V := x

例子

令n = 112729，A = 5，求得的的连续值为:

1
2
3
4
5
6
7
V1 of seq(5) = V1! of seq(5) = 5
V2 of seq(V1) = V2! of seq(5) = 23
V3 of seq(V2) = V3! of seq(5) = 12098
V4 of seq(V3) = V4! of seq(5) = 87680
V5 of seq(V4) = V5! of seq(5) = 53242
V6 of seq(V5) = V6! of seq(5) = 27666
V7 of seq(V6) = V7! of seq(5) = 110229

此时，，所以139 是112729的一个非平凡素因子。
注意到 $p+1 = 140 = 2^2 5 7。而7!$ 是最小的是140的倍数的阶乘数，所以我们找到了一个合适的因子139。

例题 [V&N2020 公开赛]easy_RSA

就是因为这题，才会想到Williams’s p+1
审计代码发现n = qpr 中三个因子都是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
20
21
22
23
24
25
n=7941371739956577280160664419383740967516918938781306610817149744988379280561359039016508679365806108722198157199058807892703837558280678711420411242914059658055366348123106473335186505617418956630780649894945233345985279471106888635177256011468979083320605103256178446993230320443790240285158260236926519042413378204298514714890725325831769281505530787739922007367026883959544239568886349070557272869042275528961483412544495589811933856131557221673534170105409
A = [5, 7, 9, 11, 13]

def seq(t, base, n):
    x = 2
    y = base
    i = 0
    while True:
        x, y = y, (base * y - x) % n
        i += 1
        if i == t:
            return x
            break

fac = []
for v in A:
    for i in range(1, 5000):
        v = seq(i, v, n)
        p = gmpy2.gcd(v - 2, n)
        print(i,p)
        if p != 1:
            fac.append(p)
            break
    if len(fac) != 0:
        break

当程序在A = 5 , i = 2391时
就跑出了其中一个因子为

1
102634610559478918970860957918259981057327949366949344137104804864768237961662136189827166317524151288799657758536256924609797810164397005081733039415393

然后用n除以这个因子并对得数继续Williams’s p+1便可以分解出剩下的两个因子

wiki没有中文可真是头大(原理和例子其实就是英文wiki上Williams’s p+1的摘抄+翻译啦