我正在寻找一种实现或清晰的算法,用于在python,伪代码或其他任何可读的内容中获得N的素数因子分解.有一些要求/事实:

• N介于1到20位之间
• 没有预先计算的查找表,但是memoization很好.
• 不需要在数学上证明(例如,如果需要,可以依赖于Goldbach猜想)
• 不需要精确,如果需要,可以是概率/确定性的

我需要一个快速素数因子分解算法,不仅适用于自身,还适用于许多其他算法,如计算Euler phi(n).

我已经尝试了维基百科的其他算法,但要么我无法理解它们(ECM),要么我无法从算法(Pollard-Brent)创建工作实现.

我对Pollard-Brent算法非常感兴趣,因此对它的任何更多信息/实现都会非常好.

谢谢!

编辑

搞砸了一下后,我创建了一个非常快速的素数/分解模块.它结合了优化的试验分割算法,Pollard-Brent算法,米勒 - 拉宾素性测试和我在互联网上发现的最快的素数.gcd是常规Euclid的GCD实现(二进制Euclid的GCD 比常规GCD 慢得多).

赏金

哦,快乐,可以获得赏金!但我怎么能赢呢？

• 在我的模块中找到最优化或错误.
• 提供替代/更好的算法/实现.

最完整/最具建设性的答案得到了赏金.

最后模块本身:

import random

def primesbelow(N):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    #""" Input N>=6, Returns a list of primes, 2 <= p < N """
    correction = N % 6 > 1
    N = {0:N, 1:N-1, 2:N+4, 3:N+3, 4:N+2, 5:N+1}[N%6]
    sieve = [True] * (N // 3)
    sieve[0] = False
    for i in range(int(N …