基于大素数分解的公钥加密的2个公式不明白

epegasus

p,q是2个大素数
n=pq
m=(p-1)(q-1)
1<= e <=m
以下2个不结论不懂：
1.当(m, e)=1,有d使得de=km，k为某正整数
2.x^(km)mod(n)=1

[ 本帖最后由 epegasus 于 2008-9-28 08:56 编辑 ]

egmkang

建议你上TopLanguage上面去问问,那里学习数学的牛人比较多.


[ 本帖最后由 egmkang 于 2008-9-28 12:05 编辑 ]

cugb_cat

这个。。。得去看数论了。。

win_hate

原帖由 epegasus 于 2008-9-28 08:46 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&p,q是2个大素数
n=pq
m=(p-1)(q-1)
1<= e <=m
以下2个不结论不懂：
1.当(m, e)=1,有d使得de=km，k为某正整数
2.x^(km)mod(n)=1

m=phi(n)=(p-1)(q-1)，phi 是欧拉函数

若 x 与 n 互素，则总有 x^m=1 (mod n)， 对任意 k ，当然也有 x^(km)=1 (mod n)

第一个结论与 (m, e)=1 没有什么关系，估计你抄错了。

cugb_cat

原帖由 win_hate 于 2008-9-28 12:15 发表


m=phi(n)=(p-1)(q-1)，phi 是欧拉函数

若 x 与 n 互素，则总有 x^m=1 (mod n)， 对任意 k ，当然也有 x^(km)=1 (mod n)

第一个结论与 (m, e)=1 没有什么关系，估计你抄错了。

还是老大牛叉，膜拜中。。

epegasus

那x^m=1 (mod n)这个结论又是怎么得出来的呢

win_hate

原帖由 epegasus 于 2008-9-28 12:53 发表
那x^m=1 (mod n)这个结论又是怎么得出来的呢

这个是欧拉定理。要找本书学一下，否则不容易弄清楚。下面是一个简短证明:

设 A={a(1), a(2), ..., a(m)} 是 0~(n-1) 中与 n 互素的数集. (x, n)=1

则 xA = {x a(1), x a(2), ... x a(m) } 在模 n 的意义下是 A 的一个置换。

所以 a(1)...a(n)=x^m a(1)...a(n) (mod n)

但 a(1)...a(n) 与 m 互素，所以 x^m=1 (mod n).

epegasus

原帖由 win_hate 于 2008-9-28 13:07 发表


这个是欧拉定理。要找本书学一下，否则不容易弄清楚。下面是一个简短证明:

设 A={a(1), a(2), ..., a(m)} 是 0~(n-1) 中与 n 互素的数集. (x, n)=1

则 xA = {x a(1), x a(2), ... x a(m) } 在模 n 的 ...

妙，关于第3步：
xa(i)!=xa(j) mod(n)
因为如果相等则有a(i)=a(j) mod(n)    ?

还有就是欧拉很牛，早就知道了，听说他写的书和文章后人收集的全集就有长长的一个书架，但是好象他的书都是德文的，没有翻译成中文的。否则一定看看。。

[ 本帖最后由 epegasus 于 2008-9-28 14:13 编辑 ]