关于我更新的整数分解算法factorization_nr_138132535-的技术咨询

我最近更新了自己的一款旧整数分解算法——factorization_nr_138132535-，想和大家聊聊这个算法的思路、优化版本，听听各位的专业看法~

基础数学逻辑 #

算法的核心基于以下数学推导：

• 设待分解的目标整数为N
• 定义M = b*N（b为迭代参数）
• 计算X = (a^(M²) - a) mod (a*M²)
• 求最大公约数p = gcd(X, M)
• 最终得到N的候选因子P = gcd(N, p)

UPDATE 1：初始可运行实现（C+GMP） #

我用C语言结合GMP大数库完成了第一版可运行的算法，设置max_a=100，代码如下：

Input N (number to factor)
P=1
a=2
b=1
while( P==1 || P==N ){
    M=b*N
    while(a < max_a){
        X= (a^(M^2)-a) mod (a*M^2)
        p= gcd(X,M)
        P=gcd(N,p)
        a=a+2
    }
    a=2
    b++
}
Output P (factor of N)

UPDATE 2：版本2_2（大幅提速） #

后续我优化出了2_2版本，运行速度有明显提升，算法代码如下：

Input N (number to factor)

P=1

a=2

b=1

while( P==1 || P==N ){

    M=b*N
    
    while(a < max_a){

        X= (a^(M^2-1)-1) mod (N)

        P=gcd(X,N)

        a++
    }
    a=2
    b++
}

Output P (factor of N)

UPDATE 3：版本2_3（进一步优化速度） #

紧接着我又迭代出了2_3版本，速度表现更出色：

Input N (number to factor)

P=1

a=2

b=1
c=1
while( P==1 || P==N ){
    M=b*N
    while(c < max_c){     
        R=M^c
        while(a < max_a){
            X= (a^(R-1)-1) mod (N)
            P=gcd(X,N)
            a++
        }
        a=2
        c++ 
    }
    c=1
    b++
}

Output P (factor of N)

UPDATE 4：性能测试结论 #

经过实际测试，版本2_2在处理大整数分解时的速度表现优于其他所有版本。

备注：内容来源于stack exchange，提问作者Alberico Lepore