素因数分解

素因数分解とは、負でない整数を素数の積の形に表現すること。

概要

• 0⁰ = 1
• 1⁰ = 1

なので、素因数分解の結果が「ただ一通り」にならない（素因数分解の一意性が成立しない）ようなことのないよう、素数には含めない。言ってみれば「素数の定義」と「素因数分解の一意性」は相対（そうつい）の関係にある。
12 を 素因数は 2 が二個にと 3 が一個なのだが、これを　12 = 2²・3¹の形、すなわち「素数の小さいものから順に並べ、冪数の係数が 0 であるものを除く」という形に整理したものが素因数分解である。
したがって、ある 2 以上の整数について、その結果

• (p = p ¹) ≡ (p は素数)
• n が平方数である場合、冪数の係数はすべて 2 である。

などが謂える。

人間生活との関わり・利用

素因数分解の効率的な計算法は、現在のところ、見つかっていない。とくに多数桁の素数×多数桁の素数を二つに分解するのには非常に手間がかかるため、暗号理論などに利用されている。