「ねぇ。おじさん。このブログ、少しも、おもしろくないじゃないの!」
「やぁ。ともちゃんか。じつは、わしもひそかにそう思っていたところじゃよ。どうしても文章が堅くなってしまうのう。これでは、わしの作っておるホームページと変わるところがないな。」
「でしょ。だから、ときどき、私が出てきて、ツッコミを入れてあげるわよ」
「いや。これは、これは。イタイ。いや、頼みましたよ」
ということで、ともちゃんが、現れて、助けてくれることになりました。
「で、早速なんだけど、この前、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となるな。どうじゃな?」
「なーるほど。でも結構、面倒くさいわね」
「式でこのように書くと面倒のように見えるが、これは、単純なアルゴリズムで実現できるのじゃな」
「アルゴリズムって」
「算法ということだな。プログラムの中に組み込む手順のことだよ。もっとも、このあたりを解説していると大変だ。本日は、これまでということにしておこう」
「じゃ。また来るから、それまでにちゃんと勉強しといてね」
「おいおい、それは、ともちゃんの方だろうが・・」