论坛 › 难题征解 › 请教gxqcn一个问题

liangbch 发表于 2008-10-27 17:19:33

猜想其对x分解质因数的算法
1. 用一定范围内的小素数试除，比如说用65536以内的素数试除。
2. 用伪素数试除，如 n=210K+i(i除以2,3,5,7的余数都不等于0，n<sqrt(x)) 的形式的数试除，因为每210个数中，至多有48个质数，所有这个方法分解x，之多需要 sqrt(x)*48/210= sqrt(x)*0.22次除法,

无心人 发表于 2008-10-27 19:47:28

据说是用2048内的素数除比较好

无心人 发表于 2008-10-27 20:14:34

上传一个GMP-4.2.4里的例子
使用的是简单的算法
分解liangbch提供的例子
就是瞬间分解掉

gxqcn 发表于 2008-10-27 20:24:05

谢谢无心人提供的资料，等有空时分析下它的算法（好像用到了rho）。

无心人 发表于 2008-10-27 20:35:13

是的
三个算法
试除
2kp
rho
中间的不知道啥意思

gxqcn 发表于 2008-10-27 20:49:09

大致浏览了一下代码，2kp 也是试除法，
只是它试除的是一个以 2p+1 为首项、2p为公差的等差数列（项数为入参limit-1）。

无心人 发表于 2008-10-27 21:18:30

哦

无心人 发表于 2008-10-27 21:35:49

http://www.shamus.ie/index.php?page=Downloads

这里能下载到miracl 5.3.3的代码
其中有source目录
下面是源代码
factor.c也是分解算法
这个全
RHO, P+1, P-1, 椭圆曲线、二次筛均实现了
1700多行代码

可惜我这里的gcc无法测试编译
VC是支持的

无心人 发表于 2008-10-27 21:43:42

RHO不错（GMP那个）
34位的一个数也得到了结果

bash-3.2# ./factor
1234567890123456789012345678901234567
1234567890123456789012345678901234567 = 43 1283 2363743 27740913371 341270582221531
111111111111111111111111111111111111189012345
111111111111111111111111111111111111189012345 = 3 5 22441 541571 10000250261371 60947761086054896783
bash-3.2# ./factor
10000250261371
10000250261371 = 10000250261371
60947761086054896788
60947761086054896788 = 2 2 7 22854281 95242801691

medie2005 发表于 2008-10-27 21:54:34

设N=p*q   p,q(p>q)均为素数,且p-q=O(N^(1/2)).
设p-q=a_1*2^(v_1)+a_2*2^(v_2)+...+a_k*2^(v_k),其中:k<O(loglog(N)),v_i<O(log(N)), a_iin{-1,0,+1}.
令V_0=p,U_0=p-q.
于是,V_0,U_0满足:V_0^2-V_0*U_0-N=0.
将U_0看成常数,那么,V_0是方程V^2-U_0*V-N=0的一个正整数根.
我们穷举U_0,判断U_0^2+4N是否是平方数,若是,则解方程就得到一个素因子.

查看完整版本: 请教gxqcn一个问题