NEW GAME!を観ました。プログラミング始めます。（18）

遅れを取り戻すべく連続更新！（このペースは続きません）
f:id:kirintt:20171024230608p:plain

※基本的に、愛知大学の有澤先生がプログラミングの講義で使用しているテキスト「Pythonによるプログラミング入門」に沿って進めています。
※Python 2.7.13を使用しています。

今回のテーマは「ちょっと変わった掛け算」です。

ちょっと変わった掛け算

　公開鍵暗号にも応用されている数学の問題を扱おう。紙面の都合上もちろん全てを解説できない。ほんの入り口である。整数 x と y および正整数 m を与え x と y を掛けて m で割った余りの計算を行う。
（引用元：Pythonによるプログラミング入門, p. 44）

この１文目読んだ瞬間に「あ、この節無理だわ」と思ったのは内緒。
さて、テキストでは具体例として x = 1 , · · · , 12、y = 1 , · · · , 12、m = 13 の場合の表（下図）が示されている。

図 4.1: mod 13 による掛け算表
（引用元：同上, p. 44）

いくつか例を挙げておく。

例１）x = 2, y = 3
(x * y) % m = (2 * 3) % 13 = 6
→ 2行3列の交点：6

例２）x = 7, y = 11
(x * y) % m = (7 * 11) % 13 = 12
→ 7行11列の交点：12

例３）x = 10, y = 4
(x * y) % m = (10 * 4) % 13 = 1
→ 10行4列の交点：1

パッと見、よくわからん数字の羅列だなぁ…と感じたが、テキストによるとこの行列はどの行・どの列を見ても1～12の数字が必ず１つずつ現れているらしい。本当か？ …本当だった。ちなみに、こういう現象については整数論の入門書に載っているとのこと。

図 4.1 で示された表は次のプログラムによって作成される。

譜 4.7 剰余による掛け算表

m=13
for x in range(1,m):
    for y in range(1,m):
        print "%4d"%(x*y%m),
    print

（引用元：同上, p. 44）

ところがこの性質が見られるのは、m が素数の時だけらしい。
試しに、m = 10 として譜 4.7 を動かしてみた。

   1    2    3    4    5    6    7    8    9
   2    4    6    8    0    2    4    6    8
   3    6    9    2    5    8    1    4    7
   4    8    2    6    0    4    8    2    6
   5    0    5    0    5    0    5    0    5
   6    2    8    4    0    6    2    8    4
   7    4    1    8    5    2    9    6    3
   8    6    4    2    0    8    6    4    2
   9    8    7    6    5    4    3    2    1