20180204, 20:09  #1 
"Sam"
Nov 2016
5·67 Posts 
Primality test based on factorization of n^2+n+1
The primality tests for n if n^21 is factored 33.33% or higher are found here. What about the neoclassical tests for n? Suppose that n^31 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^31? I would supposed the neoclassical tests would be used, but I'm not sure. Any ideas? Thanks.

20180204, 21:35  #2 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2·1,153 Posts 
If you know all the prime factors of n^31, then you know all the factors of n1.
This is because n1  n^31. So you can use Lucas primality test to prove that n is prime. If the partial know factors of n^31 are exclusive to n1 factors then it would seem intuitively irrelevant to the primality of n, unless you can find an association between the (extra) factors of n^m1 and n. I doubt such association exits. Last fiddled with by a1call on 20180204 at 21:48 
20180204, 21:59  #3 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2×1,153 Posts 
I could not find your reference to primality testing of n when n^21 is 1/3 factored.
https://primes.utm.edu/prove/index.html Please provide a direct link. 
20180205, 00:20  #4  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2·3^{3}·5·37 Posts 
How about Williams, 1978 reference here?
Quote:


20180205, 05:19  #5  
"Sam"
Nov 2016
5·67 Posts 
Quote:
first choose a (proven) prime p = 1 (mod 3) and let a be a primitive root mod p. compute m = a^((p1)/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^31. If this m is not prime, then choose some other prime q (can be small), and try and see if m = a^((q1)*((p1)/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^((q1)*q^(k1)*((p1)/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^31 (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^((p1)/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^31). A proof based on factorization of m^2+m+1 would be easy to do for this m. Last fiddled with by carpetpool on 20180205 at 05:22 

20180205, 05:20  #6 
"Sam"
Nov 2016
517_{8} 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  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
20th Test of primality and factorization of Lepore with Pythagorean triples  Alberico Lepore  Alberico Lepore  43  20180117 15:55 
18th Test of primality and factorization of Lepore in 5 * log_25 (N) (New Year's algorithm)  Alberico Lepore  Alberico Lepore  2  20180101 21:31 
14° Primality test and factorization of Lepore ( conjecture )  Alberico Lepore  Alberico Lepore  48  20171230 09:43 
Factorization and primality test O([log_9(N)]^3)  Alberico Lepore  Alberico Lepore  26  20171217 18:44 
On crt based factorization?  Unabomber  Math  1  20140404 20:19 