<p>我不知道<em>np.prod</em>和<em>sp.uint64</em>是做什么的,但是我可以告诉你<em>p</em>-1算法,它是由John Pollard在1974年发明的。</p>
<p>Pollard的算法是基于Fermat的小定理<em>a</em>^<em>p</em>==<em>a</em>(mod<em>p</em>),当<em>a</em>时!=0可以用表达式除以<em>a</em>^(<em>p</em>-1)==1(mod<em>p</em>)。因此,如果<em>p</em>-1除<em>m</em>,则<em>p</em>除gcd(2^<em>m</em>-1,<em>n</em>)。Pollard's<em>p</em>-1算法将<em>m</em>计算为小于a界<em>b</em>的整数的最小公倍数,因此如果<em>p</em>-1的所有因子小于<em>b</em>,则gcd(2^lcm(1..<em>b</em>)-1,<em>n</em>)是<em>n</em>的因子。最小公倍数是用小于<em>b</em>的素数乘以小于<em>b</em>的素数来计算的:</p>
<pre><code>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"
</code></pre>
<p>可选的第二阶段搜索<em>b1</em>和<em>b2</em>之间的“大素数”,该素数与第一阶段的最小公倍数结合以找到因子。第二阶段只需要对每个素数进行模乘,而不是模幂运算,因此运算速度相当快,第二阶段的gcd可以成批计算。缓存很小,但对函数的效率很重要。</p>
<pre><code>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"
</code></pre>
<p>Pollard的<em>p</em>-1方法可能无法找到<em>n</em>的因子;这取决于<em>n</em>-1的因子分解和您选择的界限。检查的方法是自己设置factor<em>n</em>-1,然后使用大于最大factor<em>n</em>-1的a<em>b</em>调用Pollard的方法。例如,如果您想要factor<em>n</em>=87463=149*587,请注意<em>n</em>-1=87462=2*3*3*43*113,所以调用<em>b</em>=120的一级算法或<em>b1</em>=50和<em>b2</em>=120的两级算法,看看是否找到了一个因子。</p>
<p>我在<a href="http://programmingpraxis.com" rel="noreferrer">my blog</a>讨论了Pollard的<em>p</em>-1因子分解算法,以及其他一些因子分解算法。我还提供了powerMod和gcd函数的实现,以防在实现这些函数时遇到问题。我用Python在<a href="http://ideone.com/wdyjxK" rel="noreferrer"/><a href="http://ideone.com/wdyjxK" rel="noreferrer">http://ideone.com/wdyjxK</a>编写了一个单阶段算法的简单实现。</p>