About Number Theory Utils

for(uint64_t i = 0; i < 100; ++i){
	int64_t p = nut_u64_rand(2, 1ull << 30);
	while(!nut_u64_is_prime_dmr(p)){
		++p;
	}
	//Want to solve n**2 - n + 1 == 0 mod p
	//<=> 4*n**2 - 4*n + 4 == 0 mod p
	//<=> (2*n - 1)**2 == -3 mod p
	//<=> n == 2**-1*(1 +- sqrt(-3)) mod p
	switch(nut_i64_jacobi(p - 3, p)){
		case -1:
			printf("n**2 - n + 1 has no roots mod %"PRId64"\n", p);
			break;
		case 0://-3 is a multiple of p, ie p == 3 so we only have 1 solution
			printf("n**2 - n + 1 has a root at %"PRId64" mod %"PRId64"\n", (p + 1)/2, p);
			break;
		default: {
			//WARNING: here we know p - 3 is a quadratic residue, but nut_i64_sqrt_mod does not check this and thus if a nonresidue is given and
			//Tonelli-Shanks is selected as the optimal algorithm for this p, this would be an infinite loop
			int64_t r = nut_i64_sqrt_mod(p - 3, p);
			printf("n**2 - n + 1 has roots at %"PRId64" and %"PRId64" mod %"PRId64"\n", mod((p + 1)/2*(1 + r), p), mod((p + 1)/2*(1 - r), p), p);
		}
	}
}

A collection of functions for working modular arithmetic, polynomials over finite fields, and related things.

Implements factorization of 64 bit numbers using trial division, Pollard's Rho algorithm with Brent or Floyd cycle finding, and Lenstra's Elliptic Curve algorithm with Wierstrass or Montgomery curves. Planned support for arbitrary precision integers and Kraitcheck style methods (ie quadratic sieve and number field sieve), although Flint and its extension library Arb may be more suited for your needs.

For polynomials, implements finding roots of a polynomial over a prime field using the Cantor-Zassenhaus algorithm.

Also includes general purpose modular arithmetic routines, including powers, Miller-Rabin prime checking, random numbers, random quadratic nonresidues, Jacobi symbols, modular square root including Tonelli-Shanks and Cippola, extended gcd, Chinese remainder theorem, and Euclidean remainder.

For polynomials, also includes arithmetic (addition, subtraction, scalar multiplication, coefficientwise multiplication, multiplication, quotient and remainder, Horner evaluation, gcd, and powers), printing/normalization, and distinct degree factorization. Currently there is a simple driver function that will find all roots of a polynomial over a prime field, but if a full factorization is desired the squarefree step must still be done manually. Like the factorization part of the library, polynomials use 64 bit integers, so computations involving numbers larger than about 2³⁰ potentially can fail due to overflow.