Class NumberTheory

java.lang.Object

org.episteme.core.mathematics.numbertheory.NumberTheory

public class NumberTheory
extends Object

Number theory algorithms and utilities.

Primality testing, GCD, modular arithmetic, and more.

Since:

1.0

Author:

Silvere Martin-Michiellot, Gemini AI (Google DeepMind)

Constructor Summary

Constructors

Constructor	Description
NumberTheory()

Method Summary

Modifier and Type	Method	Description
static Natural	eulerTotient(Natural n)	Euler's totient function φ(n): count of numbers ≤ n coprime to n.
static Integer[]	extendedGCD(Integer a, Integer b)	Extended Euclidean algorithm: finds x, y such that ax + by = gcd(a, b).
static Natural	gcd(Natural a, Natural b)	Euclidean algorithm for GCD.
static boolean	isAKS(BigInteger n)	AKS primality test (simplified implementation).
static boolean	isBailliePSW(BigInteger n)	Baillie-PSW primality test.
static boolean	isProbablePrime(Natural n, int certainty)	Probabilistic primality test using Miller-Rabin.
static Natural	lcm(Natural a, Natural b)	Least common multiple.
static boolean	millerRabin(BigInteger n, int k)	Miller-Rabin primality test.
static Natural	modInverse(Natural a, Natural m)	Modular inverse: finds x such that (a * x) ≡ 1 (mod m).
static Natural	modPow(Natural base, Natural exp, Natural m)	Modular exponentiation: (base^exp) mod m.

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

NumberTheory

public NumberTheory()

Method Details

millerRabin

public static boolean millerRabin(BigInteger n,
 int k)

Miller-Rabin primality test.

Probabilistic test with error probability ≤ 4^(-k).

Parameters:

n - number to test

k - number of rounds (higher = more accurate)

Returns:

true if probably prime

gcd

public static Natural gcd(Natural a,
 Natural b)

Euclidean algorithm for GCD.

lcm

public static Natural lcm(Natural a,
 Natural b)

Least common multiple.

extendedGCD

public static Integer[] extendedGCD(Integer a,
 Integer b)

Extended Euclidean algorithm: finds x, y such that ax + by = gcd(a, b).

modPow

public static Natural modPow(Natural base,
 Natural exp,
 Natural m)

Modular exponentiation: (base^exp) mod m.

modInverse

public static Natural modInverse(Natural a,
 Natural m)

Modular inverse: finds x such that (a * x) ≡ 1 (mod m).

eulerTotient

public static Natural eulerTotient(Natural n)

Euler's totient function φ(n): count of numbers ≤ n coprime to n.

isProbablePrime

public static boolean isProbablePrime(Natural n,
 int certainty)

Probabilistic primality test using Miller-Rabin.

Parameters:

n - number to test

certainty - number of rounds (higher = more certain)

Returns:

true if probably prime

isBailliePSW

public static boolean isBailliePSW(BigInteger n)

Baillie-PSW primality test.

Combines Miller-Rabin with base 2 and a Lucas probable prime test. No known pseudoprimes exist for this test.

Parameters:

n - number to test

Returns:

true if probably prime

isAKS

public static boolean isAKS(BigInteger n)

AKS primality test (simplified implementation).

Deterministic polynomial-time primality test. Due to complexity, uses simplified checks for small numbers and falls back to Miller-Rabin for larger numbers.

Parameters:

n - number to test

Returns:

true if definitely prime