素因数分解

素因数分解とは、ある正の整数を素数の積の形で表す方法のことである。ただし、1に対する素因数分解は 1と定義する。

素因数分解には次のような性質がある。

現在多く用いられているRSA暗号に代表される公開鍵暗号の安全性は素因数分解と深い関わりがあるため素因数分解のアルゴリズムが活発に研究されている。

Table of contents

1 例
 2 素因数分解の方法
 3 関連項目

60を素因数分解する。

60 = 2 × 2 × 3 × 5 = 2² × 3 × 5

60 の約数は次のように表せる。

2⁰3⁰5⁰、2⁰3⁰5¹、2⁰3¹5⁰、2⁰3¹5¹、2¹3⁰5⁰、2¹3⁰5¹、2¹3¹5⁰、2¹3¹5¹、2²3⁰5⁰、2²3⁰5¹、2²3¹5⁰、2²3¹5¹

正の整数nを素因数分解するための最も単純な方法は、 2から順にまでの素数で割っていく方法である。しかし、nが大きくなるとこの方法では困難である。

大きなnに対しては以下のような方法がある。