最新发现 在大合数分解过程中遇到的一个现象

wsc810

设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) 大家想一想，能不能据此建立一个大合数分解的一个有效算法？

wsc810

有人会证明吗

gxqcn

反例如下： 取 d1=7，d2=17，p=31， 则 n=6 使 $(d1*d2)^n -= 1 (mod p)$ 成立， 但 $d1^n -= 4 (mod p),\quadd2^n -= 8 (mod p)$

wsc810

楼上请注意，这里要求n 是奇数且大于1

medie2005

n是奇数.

winxos

原帖由 wsc810 于 2009-4-28 14:46 发表 设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举一例说 ...

mathe

p=7,n=3的时候就可以有反例了. 当然等式成立的例子会很多, 你可以了解一下素论中一个很基本的定理:费马小定理

gxqcn

哦，对不起，没有注意到n必须为奇数。 （为方便大家阅读，我将楼主的主题帖重新排版了一遍） 另外想请教一下：d1 与 d2 是否可为合数，以及它们是否要求互素？

无心人

D^n=1 (mod p) 当D很大时候不好求吧 否则RSA早破解了

wsc810

反例是什么，math是否可以举出一例。当n是(p-1)/2时好理解。但若不是，如4181£17=1(mod 103),37£17=-1(mod 103),113£17=-1(mod 103)怎么去理解。 这是我用手机浏览时发的，不能打出幂次，就用£代替，希望大家理解。