こんにちは。R86plusAブログの時空です。今回は、素因数分解を行う強力なツールに関しての話です。
素因数分解？聞いたことないな。そろそろ現実を見なさい。ベッドから起きて歯を磨いて学校に行きなさい。はい。現実を見ます。現実的な話から始めましょう。
素因数分解は、暗号に使われるような解くのが困難な問題です。PvsNPという数学の難問とも関係がある問題で、現在のパソコンでは素因数分解の暗号であるRSA暗号は解けません。そこで、新しい方法論を用いて素因数分解を解いてみましょう。
まず、使うツールはmodです。modは剰余演算とも呼ばれ余りに関するツールです。
54=3mod17は54を１７で割った余りが３であることを示します。さらに、17×11＝１８７という問題はa=11としたとき、aが17個あることを表します。
ここで新しい考え方、あるいは新しい価値観を導入してみましょう。mod3は3で割ることを意味します。3の倍数を3で割れば余りは0です。つまり11aのうち3aは３で割ると余りは０です。17a=14a mod 3となります。
もし、mod5ならば5a=0mod5、17a=12a mod5となります。この２つの式を引いてみたらどうなるでしょうか。11×17=1mod3、11×17=2mod5です。(1mod3)-(2mod5)=2aです。つまり、14a-12a=2aです。さらに、恣意的に、(2mod5)-(7mod9)=4aとなります。
ここで、両式(1mod3)-(2mod5)=2aから(2mod5)-(7mod9)=4aを引きます。
すると、(1mod3)+(7mod9) = -2a+(4mod5)となります。
ここで、1mod3は11×17-11×3=154=1mod3、7mod9は11×17-11×9=88=7mod9を意味するので、 左辺は154+88=242となります。4mod5は2mod5+2mod5なので、11×17が2回掛けられています。
つまり、(11×17-11×5)x2=264=4mod5です。トータルで見て、154+88=(-2)x11+242となります。
ここで(1mod3)と(7mod9)を足します。11×17が2個あることになるので、(11x17x2)mod(3+9)=2mod12=154+88=242です。この方法で計算できるのは11×17=187ということが分かっているからです。
次に、(1mod3)+(7mod9)=(2mod12)= -2a+(4mod5)です。
これは、(2mod12)-(4mod5)=242-264=-2aとなります。(2mod12)-(11×17-4-5a)=-2aです。
22-183mod12=7mod12=-7aとなり、(-7×7)a=(7×7)mod12。a=(-1)mod12=11mod12。
a=１１、ｂ=１７, a x b =187
コメント