请教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提供的例子
就是瞬间分解掉

factorize.c (6.59 KB, 下载次数: 5)

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一个问题