 mersenneforum.org Primality test based on factorization of n^2+n+1
 Register FAQ Search Today's Posts Mark Forums Read 2018-02-04, 20:09 #1 carpetpool   "Sam" Nov 2016 22×83 Posts Primality test based on factorization of n^2+n+1 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.   2018-02-04, 21:35 #2 a1call   "Rashid Naimi" Oct 2015 Remote to Here/There 5×439 Posts 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. Last fiddled with by a1call on 2018-02-04 at 21:48   2018-02-04, 21:59 #3 a1call   "Rashid Naimi" Oct 2015 Remote to Here/There 42238 Posts 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.   2018-02-05, 00:20   #4
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3×7×461 Posts How about Williams, 1978 reference here?
Quote:
 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 n2+n+1 or n2-n+1 is rarely worth the effort.   2018-02-05, 05:19   #5
carpetpool

"Sam"
Nov 2016

22·83 Posts Quote:
 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.

Last fiddled with by carpetpool on 2018-02-05 at 05:22   2018-02-05, 05:20 #6 carpetpool   "Sam" Nov 2016 33210 Posts @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.   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Alberico Lepore Alberico Lepore 43 2018-01-17 15:55 Alberico Lepore Alberico Lepore 2 2018-01-01 21:31 Alberico Lepore Alberico Lepore 48 2017-12-30 09:43 Alberico Lepore Alberico Lepore 26 2017-12-17 18:44 Unabomber Math 1 2014-04-04 20:19

All times are UTC. The time now is 03:58.

Mon Jan 17 03:58:01 UTC 2022 up 177 days, 22:27, 0 users, load averages: 1.18, 1.04, 1.02