请教gxqcn一个问题

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

猜想其对x分解质因数的算法 1. 用一定范围内的小素数试除，比如说用65536以内的素数试除。 2. 用伪素数试除，如 n=210K+i(i除以2,3,5,7的余数都不等于0，n

无心人 · 发表于 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

账号		自动登录	找回密码
密码			欢迎注册

[求助] 请教gxqcn一个问题