「ねぇ。おじさん。このブログ、少しも、おもしろくないじゃないの！」「やぁ。ともちゃんか。じつは、わしもひそかにそう思っていたところじゃよ。どうしても文章が堅くなってしまうのう。これでは、わしの作っておるホームページと変わるところがないな。」
「でしょ。だから、ときどき、私が出てきて、ツッコミを入れてあげるわよ」
「いや。これは、これは。イタイ。いや、頼みましたよ」
ということで、ともちゃんが、現れて、助けてくれることになりました。
「で、早速なんだけど、この前、2の1024000乗を1067で割った余りが837と書いてあったよね」
「そうだったかな」
「そうよ！でも、どうしてDERIVEで、厳密な数値が出せなっていうのに、余りは、出てきたのよ？ それに、そもそも、出てきた、837が正しいって、どうして分かるの？」
「もっともな疑問だな。まず、余り、数学では、剰余というのじゃが、2の1024000乗を計算してから1067で割っている訳ではないのだ」
「え。余りって割ってみなければ、分からないのじゃないの」
「それは、大きな数の剰余を計算するには、まず、その数を2のべき乗の項の和に分解してから、計算するというのが定法なのじゃよ」
「へぇー。もう、ちょっと具体的に説明してよ」
「初等整数論の合同式のところに出てくるのだがな。
簡単な例で説明してみるかの。たとえば、100を13で割った場合の剰余を計算するとするな。このとき、100＝64＋32＋4であることが分かるな」
「確かにそうね。でも、13で割ったときの余りとは、どうやって結びつくのよ」
「まあ、まあ、あわてなさんな。64を13で割ると余りは、どうかな」
「余りは、12ね」
「そう。
それを64≡12（mod 13）と書くのじゃ。これを合同式という。
合同式の≡は、等号ではないが、等号と似たところもあるのじゃ。a≡b、c≡dであれば、a＋c≡b＋d、a×c≡b×dなどが成り立つのじゃよ」
「ふ～ん。」
「そこでじゃ。100＝64＋32＋4であるが、64≡12、32≡6、4≡4から、100≡12＋6＋4となり、更に12＋6＝18≡5なので、100≡5＋4＝9ということで、剰余は、9ということになるのだ。100を直接、割っておらんじゃろうが」
「なるほどね。でも、2の1024000乗なんて30万桁の数をどうやって2のべき乗の項の和に分解するの」
「う～ん。
鋭い質問であるな。
確かに一般の数については、面倒だの。素性の分からない、30万桁の数をいきなり書かれて、剰余を出せと言われても、ちょと困る」
「じゃ、どうするのよ」
「そのポイントは、今回の数が2の1024000乗という、いわば、単純な構造を持っているところにあるな。」
「というと？」
「まず、1024000＝2^19＋2^18＋2^17＋2^16＋2^15＋2^13なので、2≡2 mod 1067を元にして、まず、両辺を2乗すると2^2≡4、
更に二乗すると、2^（2×2）＝2^（2^2）≡16、2^（2^3））≡256、2^（2^4）≡65536≡449、2^（2^5）≡1005、2^（2^6）≡643、2^（2^7）≡520、2^（2^8）≡449、2^（2^9）≡1005、2^（2^10）≡643、2^（2^11）≡520、2^（2^12）≡449、2^（2^13）≡1005と進んでくる。
結局、2^（2^15）≡520、2^（2^16）≡449、2^（2^17）≡1005、2^（2^18）≡643、2^（2^19）≡520から、
1005×520≡837、1005×520×449≡229、1005×520×449×1005≡740、1005×520×449×1005×643≡1005、
すなわち、1005×520×449×449×1005×643×520≡837となるな。どうじゃな？」
「なーるほど。でも結構、面倒くさいわね」
「式でこのように書くと面倒のように見えるが、これは、単純なアルゴリズムで実現できるのじゃな」
「アルゴリズムって」
「算法ということだな。プログラムの中に組み込む手順のことだよ。もっとも、このあたりを解説していると大変だ。本日は、これまでということにしておこう」
「じゃ。また来るから、それまでにちゃんと勉強しといてね」
「おいおい、それは、ともちゃんの方だろうが・・」
