二つの大きな数をかけるのは易しいが、大きな数を因数分解は難しい。そこで、

r=pq

(s,φ(r))=1である指数sを選ぶ

rを公表するのである。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

[参]小島寛之「素数ほどステキな数はない」技術評論社

にしたがって解説すると

p=3,q=11

N=pq=33を公開鍵とする。

Nと組になる公開鍵をr=3とするが、その場合、秘密鍵はs=7となる。

「え」＝14=aを暗号化する

14^r=5 (modN)

「5」を復号するためにｓを用いる。

5^s=14 (modN)

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

オイラーの定理をN=33に適用する。

33と互いに素で、33以下の数は20個ある。φ(33)=φ(3)φ(11)＝2・10＝20

a~20=1 (mod33)が成り立つ。

rs=1　　(modφ(33))となるｓを選ぶ。

a^r=b (modN)で暗号化

b^s=(a^r）^s=a^rs=a (modN)より、aに復号。

φ(33)=(p-1)(q-1)を知るためには、p,qを知る必要があるが、ということはNを素因数分解しなければならない。

しかし、素因数分解のための効率的なアルゴリズムは、現在のところ見つかっていないのである。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

φ(33)=20

φ(20)=20(1-1/2)(1-1/5)=8

s=φ(φ(33))-1=7

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝