RSAのアルゴリズムについて教えてください

質問

RSAのアルゴリズムを
http://www.maitou.gr.jp/rsa/rsa10.php
で勉強中です。

このHPにある
『全ての数はなんと11 乗又は 21 乗すると自分自身に戻っているでしょう！
このように、２つの素数（ P, Q とします）をかけた数を法とする世界では、
全ての数が自分自身に戻るべき乗数が必ず存在します。そして、これが何乗
なのかは、最初の２つの素数( P , Q ) によって決まります』
という部分について、理屈が分かりません。。。

この部分の理屈について教えていただけませんか？
または、解説してあるHPや本を教えて頂けませんか？

よろしくお願いします。

回答No.3

koinobori7 · ベストアンサー

http://www002.upp.so-net.ne.jp/uyamakc4/RSAFFT/RSAFFT.htm
に書いてある説明で納得できますか？

お礼

ありがとうございます。
教えて頂いたホームページ読んでみます。

回答No.2

Tacosan

スマートなやりかた (笑)
重要な定理は, Fermat の定理と中国剰余定理 (Chinese Reminder Theorem, CRT) の 2つ. これらだけで OK.
CRT から「法33 の剰余系」は「法3 の剰余系」と「法11 の剰余系」の対で表すことができます. なので, そこの表の全ての数値に対し「3 でわった余りと 11 でわった余りの対」を書き込んでみてください. Fermat の定理を念頭におけば規則性が見えてくると思います.

お礼

ありがとうございます。
Fermat の定理と中国剰余定理ですね。
調べてみます。

回答No.1

ymmasayan

これは(ｎ^11)/33の余りと(ｎ^21)/33の余りががどちらもｎと等しいといっているのですが
この部分の理解は出来ていますか。
あとは確かめてみるだけですね。
スマートにやるか力仕事でやるかは自由です。

お礼

スマートなやり方で考えてみます。