オイラーの関数φ（ｎ）は１からｎ−１までの整数のうち，ｎと互いに素になるものの個数

　　φ（ｎ）＝＃（Ｚ／ｎＺ）

として定義されます．たとえば，ｎ＝７の場合，１，２，３，４，５，６なのでφ（７）＝６，ｎ＝１０の場合１，３，７，９がそうなのでφ（１０）＝４となります．

　１７６０年頃，オイラーは，数ｎが素因数ｐ，ｑ，ｒ，・・・をもつときに，それらの重複度にかかわらず，

　　φ（ｎ）＝ｎ（１−１／ｐ）（１−１／ｑ）（１−１／ｒ）・・・

であることを示しました．この原理は「エラトステネスのふるい」によっているのですが，たとえば，１０＝２・５，４４＝２^2・１１，１００＝２^2・５^2より，

　　φ（１０）＝１０（１−１／２）（１−１／５）＝４

　　φ（４４）＝４４（１−１／２）（１−１／１１）＝２０

　　φ（１００）＝１００（１−１／２）（１−１／５）＝４０

また，任意の素数ｐに対して，

　　φ（ｐ^n）＝ｐ^n（１−１／ｐ）

したがって，

　　φ（ｐ）＝ｐ（１−１／ｐ）＝ｐ−１

となります．

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

φ（１５）＝φ（３）φ（５）＝８＝１５（１-１/３）（１-１/５）＝８

φ（６３）＝φ（７）φ（９）＝３６＝６３（１-１/３）（１-１/７）＝３６

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

　φ（ｍ）は，ｍと互いに素であり，ｍより小さい整数ｒ，１≦ｒ＜ｍの個数として定義される．すなわち，φ（ｍ）は１からｍ−１までの整数のうち，ｍと公約数をもたない数はいくつあるかを数えた数を表す．

　ｍ＝９→１，２，４，５，７，８→φ（９）＝６

　ｍ＝１０→１，３，７，９→φ（１０）＝４

　φ（１）＝１，φ（２）＝１，φ（３）＝２，φ（４）＝２

　φ（５）＝４，φ（６）＝２，φ（７）＝６，φ（８）＝４

　φ（９）＝６，φ（１０）＝４，

　φ（ｐ）＝ｐ−１

　φ（ｐ^a）＝（ｐ−１）ｐ^(a-1)＝ｐ^a（１−１／ｐ）

　φ（ｍ）＝ｍΠ（１−１／ｐi）

　φ（１０）＝１０（１−１／２）（１−１／５）＝４

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

【１】公開鍵暗号システム

公開鍵暗号システムにおいて、関係者全部の暗号化した鍵は公表されている(公開鍵)。

ｓ氏に秘密の通信文を送りたい人は、Ｓ氏が公表した鍵を用いてそれを暗号化できる。

ｓ氏は逆鍵(解読鍵)を持っていて、その通信文を解読できる。

しかし、公表した鍵が逆鍵に対する有効な手がかりを含んでいないので、ほかの人は誰も解読できない。

もし、鍵が大きな数の積である指数ｋと法ｍから成り立っているなら、逆指数ｋ’は原理的には

ｋ^{φ(φ(m))-1}

から計算できるが、φ(m)を計算するためにはｍの因数を知る必要があるため、因数分解アルゴリズムを用いてもｍからは容易に出てこないため、実際にはこのことは不可能である。

一方、ｍの因数を知っている人はすぐに答えを求めることができるというわけである。

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

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

r=pq

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

rを公表するのである。

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