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

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

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

设p=2q+1 , p和q 均为素数，且p>Sqrt[N] ,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

题目的结论是错误的，平方剩余的乘积还是平方剩余

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

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

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。