Primality and Factorization, The ns Prime Test

The ns Prime Test

Perhaps the term "pseudoprime test" is a misnomer, because it actually proves n is composite, not prime. What if we want to prove, beyond doubt, that n is prime? A probabilistic approach won't do.

In some cases the pseudoprime test can be extended to prove n is prime. Assume for some x, xn-1 = 1, and for every prime q dividing n-1, x(n-1)/q ≠ 1. The order of the element x, in the group of units mod n, is a factor of n-1, but not a factor of (n-1)/q for any q. Hence the order of x is n-1, and n is prime.

A complete factorization of n-1 is not always necessary to prove primality. Suppose for some x, and some factorable s > sqrt(n), s divides n-1, and xs = 1. Also, for every q dividing s, xs/q-1 is coprime to n. (Relatively prime is easily computed using the gcd algorithm.)

If n is prime there is always such an x, namely any primitive element raised to the (n-1)/s. Now let's assume x and s exist.

Let r be a prime dividing n. Since xs = 1, the order of x mod r is a factor of s. If it were any smaller, say s/q, then xs/q-1 and n would share a common factor of r. This is not the case, hence |x| = s, and r = 1 mod s. Every prime factor is larger than sqrt(n), and n is prime.

To use this test,we only need factor n-1 halfway, up to the square root of n.

It is not necessary to find one global x; x(q) will suffice. Let r be a prime dividing n. For every q into s, there is x(q) exhibiting a primitive qth root of 1 mod r. Hence r = 1 mod q. If qk divides s then xs/qk becomes a primitive root of order qk, and r = 1 mod qk. This holds for all q dividing s. By the chinese remainder theorem, r = 1 mod s.

Finding a Generator

Along with proving n prime, the above procedure provides an efficient (albeit probabilistic) algorithm for finding a generator mod n. (You will want to select one global x, rather than x(q).) If you choose x randomly, what are the odds of finding a generator?

Since φ(n-1) of the elements in Zn* are primitive, Your selection will succeed with probability φ(n-1)/(n-1). The expected number of trials needed to obtain success is therefore (n-1)/φ(n-1).

At worst, n-1 = 2×3×5×7×11…, and φ(n-1) = 1×2×4×6×10… There are no more than t = log(n) of these factors. The ratios are even worse if we treat all odd numbers as prime, bumping 11/10 up to 9/8 etc. Compute the product of these odd/even ratios, and let t approach infinity.

Pull 2/1 out; we'll put it back later.

The product is the geometric mean of the ratios, raised to the t. For any set of positive numbers, the arithmetic mean exceeds the geometric mean, so replace each ratio with the arithmetic mean.

To find the average of the first t odd/even ratios, pull out 1 from each term, and you are left with half of 1 + 1/2 + 1/3 + 1/4 + … the harmonic series is bounded by 1+log(t). Divide this by 2t, add 1, and raise this to the t power.

exp(t × log(1 + (1+log(t))/2t))

If r approaches 0 then log(1+r) approaches r, so write it this way.

exp(t × (1+log(t))/2t)

exp((1+log(t))/2)

sqrt(E×t)

1.7 × sqrt(t) { approximate }

3.3 × sqrt(t) { put 2 back in }

The number of trials needed to find a generator x is, at worst, 3 times the square root of the number of bits in n. If n-1 is factored, or factored halfway, x can be used to prove n is prime, as described above.

Probabilistic and Recursive

Ok, this test is probabilistic, but there's a difference. Once you have found your x, you can publish x, s, and the factorization of s, and others can quickly confirm your results. Yes indeed, n is prime. Of course the test assumes s has been factored into primes, and if these primes are large, you may have to reinvoke the test on each q dividing s. A proper implementation is recursive, until the prime is small enough to verify by trial division.

Cube Root

Perhaps n-1 can only be factored a third of the way, up to s, where s is larger than the cube root of n. The ns prime test can still be applied. Assume the conditions of the test are met. Now each prime factor of n is 1 mod s. If n is not prime it is the product of two primes between n1/3 and n2/3.

Let the two primes be sx+1 and sy+1, and note that sxsy+sx+sy = n-1, or sxy+x+y = (n-1)/s. This means the sum x+y is known mod s.

Since sxsy is below n, xy is bounded below s. The largest integer value of x+y, on this hyperbola, sets x = 1 and y = s-1. Substitute and evaluate sxsy+sx+sy+1, giving s3 + 1, which is larger than n. Therefore x+y is below s, and x+y is known unambiguously.

Substitute for y, and solve the resulting equation in x, using the quadratic formula. The result is an integer iff n is composite.

If the situation is desperate and s is, say, 1/8 of the cube root of n, trial divide the 8 values below n1/3 that are 1 mod s. Finding no factors, n is once again built from primes between n1/3 and n2/3. Write xsxy+sx+sy = n-1 as before, and x+y is fixed mod s. This time x+y is bounded below 64s, hence there are 64 possible values for x+y. This leads to 64 quadratic equations, which is manageable.

If s > n1/3/100, there are 100 trial divisions, and 10,000 quadratic equations to solve.

Applications to Irreducibility

These tests can be used to prove a polynomial w(x), of degree d, over Zp is irreducible. In this case we don't have to "find" a generator. If w is irreducible than x is the generator for the resulting finite field. It's order is pd-1, and if we can prove the order of x is pd-1, we're done.

Let u = pd-1. If xu = 1 and xu/q ≠ 1 for every prime q dividing u, then the order of x is u, and w is irreducible. (This was discussed on the previous page.)

If u can only be factored partway, apply the ns test. This requires xs/q-1 to be relatively prime to w. Fortunately there is an efficient gcd algorithm for polynomials, based on synthetic division. So - suppose r(x) is an irreducible factor of w(x). The order of x is now v, as dictated by the degree of r. Since xu = 1, v divides into u. For each q in s, x leads to a qth root of 1, whence q is a factor of v. The same holds for each qk in s. Therefore s is a factor of v. If s is larger than pd/2, then the degree of r is more than half the degree of w. This holds for each r(x), hence w is irreducible.