006 | 平成18年度前期 | 横浜市立大学 | 全学部 | ・・・ | 整数論 | 標準 |
今年度の入試も峠を越した。「ハッ!」とするような問題もあまりなく、典型的な問題の出
題が多かったように感じる。その中で横浜市立大学の問題は、高校ではおそらく扱ってい
ない範疇の問題で新鮮であった。公開鍵暗号の理論で中心的な役割を果たすオイラー関
数の問題で、高校生でも思わず解いてみようと思わせるようなレベルの問題に仕上がって
いる。(→参考:公開鍵暗号の作り方)
横浜市立大学 全学部(2006)
N を自然数とし、φ(N) を N より小さくかつ N と互いに素な自然数の総数とする。すな
わち、φ(N)=#{ n|n は自然数、1≦ n <N、gcd( N , n )=1}でオイラー関数と呼
ばれている。ここに、gcd( a , b )は、a と b の最大公約数を、#Aは、集合 A の要素の
総数を意味する。
例えば、φ(6)=#{1,5}=2、φ(15)=#{1,2,4,7,8,11,13,14}=8 であ
る。このとき、以下の問いに答えよ。
(1) p と q を互いに異なる素数とし、N=pq とおく。
(@) N より小さい自然数 n で、gcd(N,n)≠1 となるものを全て求めよ。
(A) φ(N) を求めよ。
(2) p と q を互いに異なる素数とし、N=pq とおく。今 N と φ(N)
があらかじめ分かって
いるとき、 p と q を解としてもつ二次方程式を N や φ(N) 等を用いて表せ。
(3) N=84773093、および φ(N)=84754668 であるとき、N=pq
(p>q) となる
素数 p および q を求めよ。(求めた p および q が素数であることを示さなくてよい。)
ただし、必要に応じて以下の数表を使ってもよい。
3202=102400、3222=103684、3242=104976、3262=106276、
3282=107584、3302=108900
(解)(1)(@) N より小さい自然数 n で、gcd(N,n)≠1 となるものは、p または q で割
り切れる数なので、
p、2p、3p、・・・、(q−1)p、q、2q、3q、・・・、(p−1)q
これらはすべて異なる自然数である。
(A) φ(N)=pq−1−(q−1+p−1)=pq−p−q+1=(p−1)(q−1)
(2) p+q=pq−φ(N)+1=N−φ(N)+1 、 pq=N より、
p と q を解としてもつ二次方程式は、 X2−(N−φ(N)+1)X+N=0
(3) 条件より、 X2−18426X+84773093=0
判別式をDとすると、
D/4=84879369−84773093=106276=3262
なので、
X=9213±326=9539、8887 (終)
問題文では、9539、8887が素数であることを示す必要はないとされているが、少し気
持ちが悪い。こちらのサイトで確認すると、確かに素数のようだ。
この問題からも分かるように、N=84773093 から 9539×8887 と素因数分解す
ることは直ぐにはできないが、いったんφ(N)=84754668 が他人に知られてしまうと、
あっさり素因数分解されてしまう。多分このことをこの問題の出題者は意図したのだろう。
このことから、Nに対して、φ(N)は暗号解読の秘密鍵として最重要機密事項と言える。