『今週の問題』第208回　解答

【コメント】

【問題２−２】について、参考としたサイトの表記の違いで、若干の混乱がありました。

「高校数学で遊ぶ公開鍵暗号ＲＳＡ」 では、暗号鍵Ｅと解読鍵Ｄとの関係は
Ｅ・Ｄ≡１　MOD((p-1)(q-1))となっていますが、
「サルにもわかるＲＳＡ暗号」では
Ｅ・Ｄ≡１　MOD(LCM(p-1,q-1))でした。

７５３は前者で、３５３は後者で求めたものです。
３５３の方が解としてはベターかと思います。

◆東京都の高校生　羅剛 さんからの解答

【問題１】

まず、今年は平成１７年だから　H＝１７

次にX＝２００５−Eとして、このXが２，３，５，７，１１，１３のうちの４つの数字により素因数分解でき、各数字が１回ずつでなければいけないので、Eにそれぞれを代入して検証する。

1. E＝２のとき、X＝２００３
   これは素数なので不可

2. E＝３のとき、X＝２００２
   分解可⇒X＝２×７×１１×１３、よって可

3. E＝５のとき、X＝２０００
   分解可⇒X＝２⁴×５³、よって不可

4. E＝７のとき、X＝１９９８
   分解可⇒X＝２×３³×３７、よって不可

5. E＝１１のとき、X＝１９９４
   分解可⇒X＝２×９９７、よって不可

6. E＝１３のとき、X＝１９９２
   分解可⇒X＝２³×３×８３、よって不可

◆京都府　so-un さんからの解答

【問題１】

Before make the answer.

F=17(knowledge)
A,B,C,D have same value.
… represents integral number.

The answer

If I use 5,I can't make 2005 by calculaion.
∵2005=5*41
　If,I use 5 for AtoD,E must be a multiple of 5.
  If,I use 5 for E,
     A*B*C*D must be a multiple of 5.
     It is unable,because of the precondition.
If E=13
  (2005-E=)1992=4*…
    ∴¬
If E=11,2
  1994(or+9)/3=664＋2/3(or+3)
   ∴¬
If E=7
  1998=9*…
   ∴¬
If E=3
  2002=2*7*11*13
  O.K.

So,the answer is (A,B,C,D)=(2,7,11,13),E=3,F=17 

◆神奈川県の中学校３年生　Ozza さんからの解答

【問題１】

今年は平成17年なのでF=17
すると、残りは2,3,5,7,11,13

もし、AからEに全て奇数が入ったとすると、A×B×C×D+Eは偶数となり不適。
よって、必ず2が含まれる。

（1）　E=2の場合
A×B×C×D=2003
しかし2003は素数なので、A,B,C,Dに1以上のどんな整数を入れても成立しないので、不適。

（2） それ以外
A=2として問題ないので、今後はそう仮定する。

ところで、Eには3,5,7,11,13しか入らないので、
B×C×Dの候補として、1001,1000,999,997,996

ところで、B,C,Dは全て奇数なのでB×C×Dも奇数。
よって候補としては1001,999,997となる。

(i) B×C×D=997の場合(E=11)
997は素数なのでA,B,C,Dに1以上のどんな整数を入れても成立しないので、不適。

(ii) B×C×D=999の場合(E=7)
999は9の倍数であり、3で少なくとも2回以上整除されるが、B,C,Dはすべて素数だから同じ素因数を2つ以上持つことはできない、よって不適。

(iii) B×C×D=1001の場合(E=3)
このとき1001に素因数分解を試みると、
1001=7×11×13

よって、B=7,C=11,D=13とすれば条件を満たす。

よって、A=2,B=7,C=11,D=13,E=3,F=17(A,B,C,Dは順序を問わないとする）が求める全ての答えである。

【問題２】

【問題２−１】

N=1217¹⁷について、それぞれ401,5で割った余りを見る。

（1）　401で割った余り

以下、≡はmod 401での等号とする。

1217¹⁷
≡14¹⁷
≡(14²)⁸×14
≡196⁸×14
≡(196²)⁴×14
≡((-80)⁴)×14
≡80⁴×14
≡((80²)²)×14
≡(-16)²×14
≡16²×14
≡256×14
≡376

（2）　5で割った余り

以下、≡はmod 5での等号とする。

1217¹⁷
≡2¹⁷
≡(2²)⁸×2
≡4⁸×2
≡(-1)⁸×2
≡1×2
≡2

上記(1)、(2)の両方を満たす解は中国剰余定理よりmod 2005において唯一つである。
それを以下で求める。

（1）より、N＝401k+376・・・(*)とかける。
ここに（2）を用いると以下のような方程式がたつ。
401k+376≡2 (mod 5)・・・(**)
これを解く。

5k≡0 (mod 5)は常に成り立つ。
よって、両辺80倍して、
400k≡0 (mod5)

(**)から両辺それぞれ引いて、
k+376≡2 (mod 5)
k+1≡2 (mod 5)
k≡1 (mod 5), 解が求まった。

ここで、(*)にk=1を代入して、
N≡401×1+376≡777 (mod 2005)

よって求める答えは、777である。

【問題２−２】

2005=5×401だから、
今、秘密鍵をdとおくと、
17d≡1 (mod 1600)・・・(***)の解を求めればよい。
この解を求める。

1600d≡0 (mod 1600)は常に成り立つ。
(***)を両辺94倍して、
1598d≡94,　

これを上の式から引いて、
2d≡-94 (mod 1600),

これを両辺8倍して、
16d≡-752 (mod 1600),

この式を(***)より引いて、
d≡753 (mod 1600),

解が求まった。

よって、753が秘密鍵である。

【感想】

やはり難しいですね。

◆東京都　まっちゃん さんからの解答

【問題１】

まず、F＝１７が分かります。

次にA〜DとEに２、３、５、７、１１、１３を入れるわけですが、これはつまりEに入れる素数とどれにも入らない素数を見つければよいということです。

ここで右辺を素因数分解してみると５×４０１となり５の倍数であることが分かります。
もしA〜Dに５が含まれているとEは５の倍数ではないので左辺は５の倍数ではありません。
またEが５の場合もA×B×C×Dが５の倍数でないので左辺は５の倍数ではありません。
よって５はどれにも入らないことが分かります。

あとは２、３、７、１１、１３からEに入る素数を探すだけなので５通り試してもすぐに見つかります。
少しだけ楽をするには２×３×７×１１×１３＝６００６から３と見当をつけてもいいかも知れません。

【問題２−１】

１２１７¹⁷
＝１２１７^1+2+4+8+2
＝１２１７¹×１２１７²×１２１７⁴×１２１７⁸×１２１７²

２００５を法として
１２１７¹≡１２１７
１２１７²≡１３９９
１２１７⁴≡３２１
１２１７⁸≡７８６より

１２１７¹⁷
≡１２１７×１３９９×３２１×７８６×１３９９
≡１２１７×３２１×３２１×７８６
≡１２１７×７８６×７８６
≡１２１７×２５６
≡７７７　となります。

【問題２−２】

２００５＝５×４０１よりp＝５、q＝４０１と分かる。
（p−１)(q−１）＝４×４００＝１６００から
秘密鍵βは１７β≡１（mod１６００）を満たす。

分かりやすくいうと
１７β＝１６００n＋１　　…（１）　（ただしnは自然数とする）　
となっている。

ここで右辺の１の位の数は１であり、βの１の位の数は３であることが分かるので
β＝１０m＋３　　　　　　…（２）　（ただしmは０以上の整数）
とおくことができて（１）に代入して整理すると
１７m＋５＝１６０n　　　…（３）

再び右辺の１の位に注目すると、０であることから、１７mの１の位は５であることが分かる。

つまりmの１の位が５であることが分かったので
m＝１０k＋５　　　　　　…（４）　（ただしkは０以上の整数）
とおくことができて（３）に代入して整理すると

１７k＋９＝１６n　　　　…（５）　　これを変形すると
１７(k−７)＝１６(nー８)　…（６）　　となる。

１７と１６(=2⁴)は互いに素なので
k−７＝１６i　　　　　　　…（７）　（ただしiは整数）　

kは０以上の整数であることから、iも０以上の整数であることが分かる。

（７）を（４）に代入して
m＝１６０i＋７５　　　　…（８）

さらに（８）を（２）に代入すると
β＝１６００i＋７５３　となる。

【感想】

RSA暗号の内容を初めて知りました。
簡単な数ですが実際に計算で出してみると嬉しいものですね。

◆滋賀県　松尾 さんからの解答

【問題１】

Fは 17 です。

あと6個の数ですが、全てをかけると 30030 です。
30030 ÷ 2005 = 14.978 ですので、2個の数をかけた時に15になるような組合せ、
すなわち 3 と 5 をかけ算から除きます。

答は 2 × 7 × 11 × 13 + 3 = 2005 です。

【問題２−１】

参考にしたページから
( A × B ) mod C ≡ (( A mod C ) × ( B mod C )) mod Cです。

また、

1217³ mod 2005 ≡ 338
1217² mod 2005 ≡ 1399

ですから、

1217 ¹⁷ mod 2005
≡ (( 1217 ³ ) ³× ( 1217 ³ ) ²× 1217²) mod 2005
≡ ( 338 ³× ( 338²× 1399 )) mod 2005
≡ ( 177 × 786 ) mod 2005
= 777

【問題２−２】

2005 = 5 × 401 だから、参考にしたページより
17 × D = n × (5 - 1) × (401 - 1) + 1 となるような D , n は
D = 753 , n = 8 となります。

答は 753 です。

念のため計算しますと、
( ３乗 ごとに計算したのは電卓の有効桁数に合わせたためです。)

777³ mod 2005 ≡1618
777⁹ mod 2005 ≡1618³ mod 2005 = 1942
777²⁷ mod 2005 ≡1942³ mod 2005 = 578
777⁸¹ mod 2005 ≡578³ mod 2005 = 1007
777²⁴³ mod 2005 ≡1007³ mod 2005 = 843
777⁷²⁹ mod 2005 ≡843³ mod 2005 = 1152

ですから、

777 ⁷⁵³ mod 2005
≡ ( 777 ⁷²⁹× (777 ⁹)²× (777 ³)²) mod 2005
≡ ( 1152 × 1942²× 1618² ) mod 2005
≡ ( 888 × 1618²) mod 2005
＝ 1217

◆千葉県　ベスの親分 さんからの解答

【問題１】

Ａ＝２，Ｂ＝７，Ｃ＝１１，Ｄ＝１３，Ｅ＝３、Ｆ＝１７

【問題２】

2005を法とし、公開鍵を17

【問題２−１】

1217ｘ1217⁸ｘ1217⁸≡777（mod2005）

1217²≡738（mod2005）

1217⁴のmodは738x738÷2005の余りで321

1217⁸のmodは321x321÷2005の余りで786

1217¹⁶のmodは786x786÷2005の余りで256

1217¹⁷のmodは1217ｘ256÷2005の余りで777

【問題２−２】

秘密鍵は、（秘密鍵をＡとする）
2つの素数をＰとＱにする

ＰｘＱ＝2005である。
下一桁が5であることから、どちらかの下一桁は５である。
下一桁が５の数字で素数は５のみ。
もう一つは2005÷5＝401

ＰとＱは5と401
17ｘＡ＝ｎ（Ｐ−１とＱ−１の最小公倍数）＋１
17ｘＡ＝ｎｘ400＋１
Ａ＝（ｎｘ400＋１）÷17　　Ａは正の整数
Ａ＝6001÷17　
Ａ＝353　　

秘密鍵は353、753、…と。　353＋nｘ400　（nは0,1,2,3,…）

　◆ 問題へもどる

　◆ 今週の問題へ

数学の部屋へもどる