００６	平成１８年度前期	横浜市立大学	全学部	・・・	整数論	標準

　今年度の入試も峠を越した。「ハッ！」とするような問題もあまりなく、典型的な問題の出
題が多かったように感じる。その中で横浜市立大学の問題は、高校ではおそらく扱ってい
ない範疇の問題で新鮮であった。公開鍵暗号の理論で中心的な役割を果たすオイラー関
数の問題で、高校生でも思わず解いてみようと思わせるようなレベルの問題に仕上がって
いる。（→参考：公開鍵暗号の作り方）


横浜市立大学　全学部（２００６）

　Ｎ を自然数とし、φ（Ｎ） を Ｎ より小さくかつ Ｎ と互いに素な自然数の総数とする。すな
わち、φ（Ｎ）＝＃｛ ｎ｜ｎ は自然数、１≦ ｎ ＜Ｎ、ｇｃｄ（ Ｎ ， ｎ ）＝１｝でオイラー関数と呼
ばれている。ここに、ｇｃｄ（ ａ ， ｂ ）は、ａ と ｂ の最大公約数を、＃Ａは、集合 Ａ の要素の
総数を意味する。
　例えば、φ（６）＝＃｛１，５｝＝２、φ（１５）＝＃｛１，２，４，７，８，１１，１３，１４｝＝８　であ
る。このとき、以下の問いに答えよ。
（１） ｐ と ｑ を互いに異なる素数とし、Ｎ＝ｐｑ とおく。
　（�@） Ｎ より小さい自然数 ｎ で、ｇｃｄ（Ｎ，ｎ）≠１ となるものを全て求めよ。
　（�A） φ（Ｎ） を求めよ。
（２） ｐ と ｑ を互いに異なる素数とし、Ｎ＝ｐｑ とおく。今 Ｎ と φ（Ｎ） があらかじめ分かって
　　いるとき、 ｐ と ｑ を解としてもつ二次方程式を Ｎ や φ（Ｎ） 等を用いて表せ。
（３） Ｎ＝８４７７３０９３、および φ（Ｎ）＝８４７５４６６８ であるとき、Ｎ＝ｐｑ （ｐ＞ｑ） となる
　　素数 ｐ および ｑ を求めよ。（求めた ｐ および ｑ が素数であることを示さなくてよい。）
　　　ただし、必要に応じて以下の数表を使ってもよい。
　　　　３２０²＝１０２４００、３２２²＝１０３６８４、３２４²＝１０４９７６、３２６²＝１０６２７６、
　　　　３２８²＝１０７５８４、３３０²＝１０８９００

（解）（１）（�@）　Ｎ より小さい自然数 ｎ で、ｇｃｄ（Ｎ，ｎ）≠１ となるものは、ｐ または ｑ で割
　　　　　　　　　り切れる数なので、

　　　　　　　　　　ｐ、２ｐ、３ｐ、・・・、（ｑ−１）ｐ、ｑ、２ｑ、３ｑ、・・・、（ｐ−１）ｑ

　　　　　　　　　これらはすべて異なる自然数である。

　　　　　（�A）　φ（Ｎ）＝ｐｑ−１−（ｑ−１＋ｐ−１）＝ｐｑ−ｐ−ｑ＋１＝（ｐ−１)(ｑ−１）

　　（２）　ｐ＋ｑ＝ｐｑ−φ（Ｎ）＋１＝Ｎ−φ（Ｎ）＋１　、　ｐｑ＝Ｎ　より、

　　　　ｐ と ｑ を解としてもつ二次方程式は、　Ｘ²−（Ｎ−φ（Ｎ）＋１）Ｘ＋Ｎ＝０

　　（３）　条件より、　Ｘ²−１８４２６Ｘ＋８４７７３０９３＝０

　　　　判別式をＤとすると、
　　　　　　　　　　　　　　　　　Ｄ/４＝８４８７９３６９−８４７７３０９３＝１０６２７６＝３２６²
　　　　なので、
　　　　　　　　　　　Ｘ＝９２１３±３２６＝９５３９、８８８７　（終）

　問題文では、９５３９、８８８７が素数であることを示す必要はないとされているが、少し気
持ちが悪い。こちらのサイトで確認すると、確かに素数のようだ。

　この問題からも分かるように、Ｎ＝８４７７３０９３　から　９５３９×８８８７　と素因数分解す
ることは直ぐにはできないが、いったんφ（Ｎ）＝８４７５４６６８　が他人に知られてしまうと、
あっさり素因数分解されてしまう。多分このことをこの問題の出題者は意図したのだろう。

　このことから、Ｎに対して、φ（Ｎ）は暗号解読の秘密鍵として最重要機密事項と言える。