wsc810 发表于 2012-11-5 09:05:55

利用模p的原根求解大数的因子

设p=2q+1 ,p和q 均为素数，且p>Sqrt ,N为待要分解的大合数N=d1*d2，若ind N=q ,即
N^q=1 (mod p) 成立的最小指数是q ,则有 ind d1=ind d2=p-1,上面的意思即是说若 N是p的平方剩余，则它的两个因子d1,d2是模p的非平方剩余。利用这个论断，对不同的模数p,看那些因子是共有的，则在多个非平方剩余的有序表中查找，可筛选的数就会不断减少。不知这个方法对付大数怎么样，对不大的数N，能否有效分解。

无心人 发表于 2012-11-5 19:18:47

现在的主流算法都是利用因子基
来获取
x^2 - y^2 = R^2 (mod P)的形式
以进行分解

郭先抢 发表于 2012-11-20 19:35:48

我感觉你对数论中的分解因数和素数判定很感兴趣呀,傻孩子,别在这方面浪费太多的时间,人的精力是很悠闲的丫

mathe 发表于 2012-11-22 05:21:15

题目的结论是错误的，平方剩余的乘积还是平方剩余
页: [1]
查看完整版本: 利用模p的原根求解大数的因子