このアプリケーションは整数について以下の値を計算します。

• 素因数分解およびオイラーのφ関数
• 原始根(ある場合)
• 4n+1型の素数のときはx^2 + y^2 = p （平方和）となる数
• 3n+1型の素数のときは x^2+3y^2 = p となる数
• 8n+1型、8n+3型の素数のときは x^2 + 2y^2 = p となる数
• 8n+1型、8n+7型の素数のときは x^2 - 2y^2 = p となる数

素因数分解にはフェルマー法、ボラード・ロー法、楕円関数法を、素数判定にはミラー・ラビン法、SQUFOF法を使用しています。

解説

オイラーのφ関数

オイラーのφ関数とは与えられた数（Nとする）と互いに素な数の個数です。Nが素数ならばφ(N)=N-1となります。フェルマーの小定理

a^φ(N)=1 (mod N)

などに使われます。