Primality test based on factorization of n^2+n+1

[carpetpool]

The primality tests for n if n^2-1 is factored 33.33% or higher are found here. What about the neoclassical tests for n? Suppose that n^3-1 is factored 33.33% or higher. Is there a way to prove n prime WITHOUT using ECPP? For example, is it possible to prove this prp (n) prime given the known factorization of n^3-1? I would supposed the neoclassical tests would be used, but I'm not sure. Any ideas? Thanks.

[a1call]

If you know all the prime factors of n^3-1, then you know all the factors of n-1.
This is because n-1 | n^3-1.
So you can use Lucas primality test to prove that n is prime.

If the partial know factors of n^3-1 are exclusive to n-1 factors then it would seem intuitively irrelevant to the primality of n, unless you can find an association between the (extra) factors of n^m-1 and n.
I doubt such association exits.

[a1call]

I could not find your reference to primality testing of n when n^2-1 is 1/3 factored.
https://primes.utm.edu/prove/index.html

Please provide a direct link.

[Batalov]

How about Williams, 1978 reference here?

Originally Posted by UTM pages

See [Williams78] for the theory and examples of these techniques). But the cost in terms of mathematical complication is very high. So in practice adding a few terms such as n²+n+1 or n²-n+1 is rarely worth the effort.

[carpetpool]

Originally Posted by [B

UTM Pages[/B]]The way Williams and others began in the 70's was to use the factors of other polynomials of n such as n2+1, n2+n+1 and n2-n+1 [Williams78].

Does the reference state when it is applicable though or exactly what theorems to follow? (Namely when a known factor of n^2+n+1 is roughly the size of n or greater). For constructing these n (which are prps or primes)

first choose a (proven) prime p = 1 (mod 3) and let a be a primitive root mod p.

compute m = a^((p-1)/3) mod p

If this m is (probably) prime, then most likely it can be proved using the fact that p is roughly the size of m (if not greater), and p divides m^3-1.

If this m is not prime, then choose some other prime q (can be small), and try and see if

m = a^((q-1)*((p-1)/3)) mod (q*p)

is (probably) prime. If so, then no need to continue further. If not try and find the smallest k such

m = a^((q-1)*q^(k-1)*((p-1)/3)) mod (q^k*p)

is (probably) prime.

For a quick demonstation of a another probable prime n (which may be proved prime based on the factorization of n^3-1 (and more specifically n^2+n+1).

First we have p = 13 and 6 a primitive root mod p (a = 19).

We find that 19^((p-1)/3) mod p isn't prime so we choose another prime q = 7.

Jumping ahead to step 2 (plus a little more work applied) we find that

m = a^(4*7^321) mod (7^322*13) is prp (already shown prime) and m^2+m+1 is 50% factored (33.33% for m^3-1). A proof based on factorization of m^2+m+1 would be easy to do for this m.

[carpetpool]

@a1call:

https://primes.utm.edu/prove/prove3_1.html

https://primes.utm.edu/prove/prove3_2.html

https://primes.utm.edu/prove/prove3_3.html

Hope you find these useful.