このアプリケーションは整数について以下の値を計算します。
- 素因数分解およびオイラーのφ関数
- 原始根(ある場合)
- 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)
などに使われます。
原始根
素数および素数の冪なる数(4,8,9,16,25 など)には原始根と呼ばれる値がφ(N-1)個存在します。原始根はその1からN-2までの冪を法Nで考えると1からN-1までの数全てが現れます。例えば7の原始根は3です。実際
3^0 = 1
3^1 = 3
3^2 = 2 (mod 7)
3^3 = 6 (mod 7)
3^4 = 4 (mod 7)
3^5 = 5 (mod 7)
です。有限体Fpの乗法群は巡回群であるなどとも言われます。
This application calculates the following values for integers
- Prime factorization and Euler's φ function Primitive roots (if any)
- Number for which x^2 + y^2 = p (sum of squares) for primes of type 4n+1
- Number for which x^2 + 3y^2 = p for primes of type 3n+1
- Number for which x^2 + 2y^2 = p for primes of type 8n+1 and 8n+3
- Number for which x^2 - 2y^2 = p for primes of type 8m+1 and 8n+7
We use Fermat's method, Bollard-Law method, and elliptic function method for prime factorization, and Miller-Rabin method and SQUFOF method for prime number determination.