Primality Proving with Cyclotomy, Band 1900

algorithm B₂ binary operations bit operations calculate character modulo combined complex multiplication complexity bounds compositeness tests conductor q coprime cost cyclic cyclotomic constellation cyclotomic polynomial defined divides element elliptic curves equal exists exponent extension of degree extension of Z/nZ field final trial division finite function Gal(L/Q Galois Gauss sums Gaussian elimination implies Jacobi sum test lcm(t Lemma log log log₂ Lucas-Lehmer test matrix maximal method minimal modulo needed to perform number of prime O(log OL/NOL optimization step ord(n mod ord(x pˆk parameters polynomial primality proof primality test prime divisor prime factors prime number prime power primes q probable primes problem prove the primality pseudoprimes quadratic replace residue classes result ring root of unity satisfies solution Su,m Suppose t₁ Theorem up,k upper bound values Z/mZ