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

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)怎么去理解。
这是我用手机浏览时发的，不能打出幂次，就用£代替，希望大家理解。