質問: 5桁×5桁=123456789 ○○○○○×○○○○○=123456789 という問題があるのですが、○○○○○にはどの数字が入るのでしょうか? 気になっています。どなたか教えてください。
回答: > どうしたら答えが出せるんですか? 基本的には素因数分解しかないんじゃないかと思います. 123456789 が9(=3^2)で割れるのはすぐ見えます. 1+2+3+4+5+6+7+8+9=45 ですから,有名な判定法です. 123456789÷9 = 13717421 ですが,これの素因数分解はちょっと面倒です. √13717421 ≒ 3703.7 ですから,コンピューター使うなら 3703 以下の素数で次々割ってみればよいわけで, この程度でしたらあっという間にできるでしょう. 123456789 = 3×3×3607×3803 が素因数分解で,これから5桁×5桁にするには (3×3607)×(3×3803) = 10821×11409 にするしかないことがすぐわかります. 一般に,与えられた自然数が素数かどうか判定し,素数でないなら素因数分解する, というのは大きな数に対しては非常に困難な問題のようです. この困難さが公開鍵暗号の本質だと聞いています. 最近,何か新しいアルゴリズムの発展があったとどこかで見たか,聞いたかした 覚えがありますが,忘れちゃいました.