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

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

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

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

よろしくお願いします。

No.3 ベストアンサー 回答者： koinobori7 回答日時： 2009/03/20 06:54

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

この回答へのお礼

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

お礼日時：2009/03/21 22:43

No.2 回答者： Tacosan 回答日時： 2009/03/19 01:08

スマートなやりかた (笑)

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

この回答へのお礼

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

お礼日時：2009/03/21 22:41

No.1 回答者： ymmasayan 回答日時： 2009/03/19 00:26

これは(ｎ^11)/33の余りと(ｎ^21)/33の余りががどちらもｎと等しいといっているのですが

この部分の理解は出来ていますか。
あとは確かめてみるだけですね。
スマートにやるか力仕事でやるかは自由です。

この回答へのお礼

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

お礼日時：2009/03/25 23:58