最新发现 在大合数分解过程中遇到的一个现象
:) 设D是待要分解的一个大合数，D=d1*d2设有D^n=1(mod p) ,n为成立的最小指数，
当n是奇数时(大于1)，则有 d1^n=1,d2^n=1 或者有 d1^n=-1,d2^n=-1;（为什么？谁会证明）
下面对较小的D举一例说明4181=37*113
4181^3=2^3=1 (mod 7), 37^3=2^3=1 (mod 7), 113^3=1^3=1 (mod 7)
4181^11=18^11=1 (mod 23), 37^11=14^11= -1 (mod 23), 113^11=21^11=-1 (mod 23)
4181^41=31^41=1 (mod 83), 37^41=1 (mod 83), 113^41=30^41=1 (mod 83)
大家想一想，能不能据此建立一个大合数分解的一个有效算法？
忘了说明在这里要求 选取的以模p的素数小于待要分解的合数D
有人会证明吗结论是错的
反例如下：取 d1=7，d2=17，p=31，
则 n=6 使 $(d1*d2)^n -= 1 (mod p)$ 成立，
但 $d1^n -= 4 (mod p),\quadd2^n -= 8 (mod p)$
楼上请注意，这里要求n 是奇数
楼上请注意，这里要求n 是奇数且大于1 n是奇数. 原帖由 wsc810 于 2009-4-28 14:46 发表 http://bbs.emath.ac.cn/images/common/back.gif:) 设D是待要分解的一个大合数，D=d1*d2 设有
D^n=1(mod p) ,n为成立的最小指数 ，当n是奇数时(大于1)，则有 d1^n=1,d2^n=1
或者有 d1^n=-1,d2^n=-1;（为什么？谁会证明）
下面对较小的D举一例说 ...
:) p=7,n=3的时候就可以有反例了.
当然等式成立的例子会很多,
你可以了解一下素论中一个很基本的定理:费马小定理 哦，对不起，没有注意到n必须为奇数。
（为方便大家阅读，我将楼主的主题帖重新排版了一遍）
另外想请教一下：d1 与 d2 是否可为合数，以及它们是否要求互素？ D^n=1(mod p)
当D很大时候不好求吧
否则RSA早破解了 本帖最后由 wsc810 于 2009-9-1 15:16 编辑
反例是什么，math是否可以举出一例。当n是(p-1)/2时好理解。但若不是，如4181£17=1(mod 103),37£17=-1(mod 103),113£17=-1(mod 103)怎么去理解。
这是我用手机浏览时发的，不能打出幂次，就用£代替，希望大家理解。
页:
[1]
2