Dixon‘s 因子分解法——C语言实现

Dixon's 分解法（也称为随机平方分解法）是一种基于平方同余的通用整数分解算法。

这个实现原理和费马分解法相同

/*
Dixon's 分解法C语言版Dixon's 分解法原理和费马分解法相同gcc -o dixon dixon.cpp -lm
*/#include <stdio.h>
#include <stdlib.h>
#include <math.h>#include <stdio.h>// 迭代计算GCD
int gcd(int a, int b) {while (b != 0) {int temp = b;b = a % b;a = temp;}return a;
}int dixon_factor(long int n) {long int x, xx, y, d, q, rt;long int i, j;rt = sqrt(n);//printf("S = %Zd\n\n",rt);x = rt;for (;;x++) {d = gcd(x, n);//printf("X = %ld\n\n",x); //8400if (1<d && d<n) goto end;xx = (x*x)%n;//printf("XX = %ld\n\n",xx); //368449y = sqrt(xx);//printf("Y = %ld\n\n",y); //607q = (x-y)%n;d = gcd(q, n);if (1<d && d<n) goto end;}return 0;end:return d;
};int main() {int n, f;f = dixon_factor(70191551);printf("P = %ld\n\n",f);return 0;
};