mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2018-02-04, 20:09   #1
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

11×29 Posts
Post 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.
carpetpool is offline   Reply With Quote
Old 2018-02-04, 21:35   #2
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2×7×139 Posts
Default

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
a1call is offline   Reply With Quote
Old 2018-02-04, 21:59   #3
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2·7·139 Posts
Default

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.
a1call is offline   Reply With Quote
Old 2018-02-05, 00:20   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

9,161 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2018-02-05, 05:19   #5
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

11·29 Posts
Default

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
carpetpool is offline   Reply With Quote
Old 2018-02-05, 05:20   #6
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

13F16 Posts
Post

@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.
carpetpool is offline   Reply With Quote
Reply

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 2018-01-17 15:55
18th Test of primality and factorization of Lepore in 5 * log_25 (N) (New Year's algorithm) Alberico Lepore Alberico Lepore 2 2018-01-01 21:31
14° Primality test and factorization of Lepore ( conjecture ) Alberico Lepore Alberico Lepore 48 2017-12-30 09:43
Factorization and primality test O([log_9(N)]^3) Alberico Lepore Alberico Lepore 26 2017-12-17 18:44
On crt based factorization? Unabomber Math 1 2014-04-04 20:19

All times are UTC. The time now is 11:12.

Mon Nov 30 11:12:05 UTC 2020 up 81 days, 8:23, 3 users, load averages: 2.22, 1.89, 1.68

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.