Contents
素数判定・合成数判定の方法
ある整数が素数であるか合成数であるかは、多くの人は、試し割り算法や倍数の特徴を使って、求めようとすると思います。試し割り算法というのは、単純に2,3,5,7,11と順々に割っていく方法で、倍数の特徴は、例えば、２の倍数は、１の位が偶数または０であることや、各位の数を足して３の倍数なら３で割り切れるなどのこと。
しかし、この方法では、３桁くらいまでならいいのですが、４桁くらいになると苦しくなり、中には、倍数の特徴が使えない数や、試し割り算法が効率的でないこともあります。
フェルマーの因数分解法
- 調べたい数 = nとする
- √n ≦ x となる最小の整数をxを考える
- x^2-n=完全平方数となれば、因数分解可能なので合成数
- １回目で定まらなければ、xを１つずつ増やし x+1で3と同じ操作を繰り返す（この操作は自明な因数分解か、n=n・1の形で、必ず止まる）
フェルマーの因数分解法の例
それでは、6499が素数であるか、合成数であるかを判定してみたいと思います。まず、n = 6499とします。80<√6499<81なので、x=81とします。81^2-6499=62となるので、x=82として、再び計算すると、82^2-6499=225=15^2となります。よって、これは完全平方数なので、6499=(82+15)(82-15)=97×67と表せて合成数であることがわかります。ちなみに、97も67もどちらも素数です。今回は、２回繰り返して完全平方数が導けましたが、もっと時間がかかる場合もあります。ですが、この計算は、自明な因数分解で必ず止まりますのでご安心ください。また、繰り返しが有効な特徴から、フェルマーの因数分解法はコンピューターの計算などに使うと効力を存分に発揮してくれます。
自明な因数分解
フェルマーの因数分解法は、自明な因数分解で必ず止まるといいましたが、それはどんな時でしょう。わかりやすいようにn=7として考えてみます。７は明らかに素数として知られていますが、これにフェルマーの因数分解法を適用してみます。
すると、7=(4+3)(4-3) となり、これは、7=7×1を表します。これが自明な因数分解です。自明な因数分解では、x=(n+1)/2, y=(n-1)/2 となります。以下に計算結果をのせておきます。
