Prime Number

素数とは、1と自分自身でのみ割り切れる1より大きい自然数である。数論の構成要素であり、すべての整数は素数の積として一意に分解される。

目的

整数の構成要素として、数論と暗号（RSA）の基礎を成す。

メカニズム

1より大きい自然数で、約数が1と自分自身のみのものである。算術の基本定理により、すべての整数は素数の積に一意に分解される。素数判定には試し割り、Miller-Rabin（確率的）、AKS（決定的だが遅い）などがある。素数は無限に存在する（ユークリッドの証明）。

ユースケース

RSA鍵ペアの生成
Diffie-Hellmanのパラメータ
素数サイズのハッシュテーブル
数論におけるリサーチ

例

入力

The first 10 primes

Output

2,3,5,7,11,13,17,19,23,29

2 is the only even prime

よくあるエラー

Using small primes for RSA moduli: Use large primes (≥1024 bits)

関連用語

Modular Arithmetic

合同算術（モジュラ演算）は整数演算の剰余を取り、結果を[0, n)の範囲に保つ。数論と暗号理論の基礎である。

BigInteger は任意精度の整数型であり、固定ワードサイズに制限されず、ネイティブ整数の範囲を超える計算（暗号や組合せ論など）に使われる。

最大公約数（GCD）は、2 つ以上の整数を割り切る最大の正の整数であり、ユークリッドの互除法で効率的に計算できる。

関連ツール

ランダムバイトジェネレーター

Generate cryptographically secure random bytes or integers。無料、プライベート、100%クライアントサイド。

フェルマー素因数分解

Fermat Factorization — 純クライアントサイドツール。プライバシーファースト、サーバー往復なし。

References