p、qが小さい素数の場合に、公開鍵と秘密鍵を求めてみましょう。

（2）N=33（p＝3、q＝11）の場合
　N＝p×q＝3×11と因数分解できる場合を考えます。(p－1) (q－1)＝2×10＝20です。N＝33を法とする場合、剰余値には0~32までの33個の数しか現れません。表2にべき乗の法を33とした値を示します。2と10の最小公倍数（LCM）は10ですから、
・ 　n・LCM＋1＝11、21、31、41、51、61、・・・（ｎ＝1.2.3.・・・）
となります。21＝3×7、51＝3×17、91＝7×13、111＝3×37ですが、鍵の候補は、20以下の自然数なので、
・ （公開鍵、秘密鍵）＝（3、7）、（3、17）、（7、13）
となります。公開鍵と秘密鍵を入れ替えても構いません。例えば、平文値が17の場合、公開鍵3を用いて17を法33の下で3乗して暗号値29を得ます。復号時には、秘密鍵7を用いて、29を法33の下で7乗すると元の値17に戻ります。3乗して7乗するので、平文値ｍが21乗され、元の値ｍに戻ります。

表2　べき乗の法を33とした値

（3）N=35（p＝5、q＝7）の場合
N＝p×q＝5×7と因数分解できる場合を考えます。(p－1) (q－1)＝4×6＝24です。N＝35を法とする場合、剰余値には0~34までの35個の数しか現れません。表3にべき乗の法を35とした値を示します。4と6の最小公倍数（LCM）は12ですから、表3の暗号値は周期12で変化していることが分かります。
・ 　n・LCM＋1＝13、25、37、49、61、73、85、97・・・（ｎ＝1.2.3.・・・）
となります。鍵の候補は、24未満の自然数なので
・ （公開鍵、秘密鍵）＝（5、5）、（7、7）、（5、17）（11、11）（7、19）
となります。公開鍵と秘密鍵を入れ替えても構いません。

表3　べき乗の法を35とした値

（4）N=85 （p＝5、q＝17）の場合
N＝p×q＝5×17と因数分解できる場合を考えます。(p－1) (q－1)＝4×16＝64です。N＝85を法とする場合、剰余値には0~84までの85個の数しか現れません。表4にべき乗の法を85とした値を示します。4と16の最小公倍数（LCM）は16ですから、表4の暗号値は周期16で変化していることが分かります。
・ 　n・LCM＋1＝17、33、49、65、81、97、113、129・・・

となります。鍵の候補は、64未満の自然数なので
・ （公開鍵、秘密鍵）＝（3、11）、（7、7）、（5、13）、（3、43）、（5、29）、（7、23）、（3,59）
となります。公開鍵と秘密鍵を入れ替えても構いません。実際の暗号にはもっと大きな数が用いられます。

表4　べき乗の法を85とした値

（5）N＝20190707（p＝4567、q＝4421）の場合
2019年の七夕の日にちなみ20190707という比較的大きい数字を考えましょう。
・ N=20190707＝4567×4421
と素因数分解できます。つまりN＝20190707、p＝4567、q＝4421です。
・ （ｐ－1）（q－1）＝4566×4420＝20181720

　　（＝2 * 2 * 2 * 3 * 5 * 13 * 17 * 761）
を法（mod）とする剰余計算を行います。剰余計算とは、法で割った余りを与える計算です。
法(p－1)(q－1)と互いに素な自然数C（公開鍵）に対して、
・ C×D≡1　mod (p－1)(q－1)　かつ　0≦D≦(p－1)(q－1)
を満たす数D（秘密鍵）が存在します。例えばC＝707（＝101×7）に対して、
・ 707×D≡1　mod 20181720　かつ　0≦D≦20181720
なる自然数Dは997525043です。なぜなら
・ 707×997525043＝705250205401
・ 20181720×34945＝705250205400
より
・ 707×997525043＝20181720×34945＋1
が成り立っているからです。受信者は、（N、C）＝（20190707、707）を公開し、D＝997525043は秘密鍵として非公開にします。送信者は、送りたいメッセ－ジを数字ｍ（0≦ｍ≦N）に変換し、公開鍵Cを用いて
・ K＝ｍ^C mod N
なる暗号文Kを送信します。暗号文Kは公開鍵から復号することはできません。受信者は、秘密鍵Dを用いて暗号文Kを復号し
・ ｍ＝K^D mod N
元のメッセ－ジｍを得ることができます。代入すると
・ （ｍ^C mod N）^D mod N＝ｍ^CD mod N＝ｍ　・・・（3）
となります。最後の等式（3）は、次に示すオイラ－の定理より、
・ CD≡1 mod (p－1)(q－1) かつ　0≦D≦(p－1)(q－1)
を満たす秘密鍵Dであれば、成り立ちます。Nを因数分解し、pとqを得られれば、(p－1)(q－1)を法として、公開鍵Cに対する秘密鍵Dを求めることができます。

（6）オイラ－の定理とは
オイラ－の定理とは、正整数ｍ、Nに対して、ｍ、Nが互いに素であるとき、
・ ｍ^φ(N)≡1 mod N　・・・（4）
が成り立つというものです。ここでオイラー関数φ(N) は「Nより小さい正の整数のうち、Nと互いに素な数の個数」を表す関数です。素数Pの場合φ(P)＝P－1となります。
・ φ(N)＝φ(pq)＝(p－1)(q－1)
となります。（2）式をｖ乗して、両辺にｍをかけると
・ ｍ^（φ(N)v+1）≡ｍ mod N　・・・（5）
（3）と（5）を比較すると
・ CD＝φ(N)v+1
を満たす整数Dとｖが存在しれば、復号できることが分かります。一次不定方程式の整数解の定理により、Cとφ(N)が互いに素であれば、整数Dとｖが存在します。もしDが負なら、
・ C（D＋ｋφ(N)）－φ(N)（v＋ｋC）＝1
と変形し、十分大きい数ｋを用いて、Dを正数D＋ｋφ(N)に置き換えることができます。