mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2006-08-16, 02:30   #1
Dougy
 
Dougy's Avatar
 
Aug 2004
Melbourne, Australia

9816 Posts
Question Alternate means of primality testing

Sorry I haven't been around for a while - I've started a PhD in combinatorics and don't have much time to do things like this.

From my experience of primality proving, the tests that I have seen boil down to one of two things:
- Trial division.
- Proving that phi(n)=n-1, by proving that the multiplicative group Z_n has order n-1.

Do there exist primality tests that are essentially different? If so, could you please provide an example?

Note: I do not care about efficiency here.
Dougy is offline   Reply With Quote
Old 2006-08-16, 04:51   #2
bearnol
 
bearnol's Avatar
 
Sep 2005

127 Posts
Default

Well, I suppose there's always Wilson's Theorem - you did say you weren't concerned with efficiency!
J
bearnol is offline   Reply With Quote
Old 2006-08-16, 09:03   #3
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

101001100101102 Posts
Default

Quote:
Originally Posted by Dougy View Post
Sorry I haven't been around for a while - I've started a PhD in combinatorics and don't have much time to do things like this.

From my experience of primality proving, the tests that I have seen boil down to one of two things:
- Trial division.
- Proving that phi(n)=n-1, by proving that the multiplicative group Z_n has order n-1.

Do there exist primality tests that are essentially different? If so, could you please provide an example?

Note: I do not care about efficiency here.
Completely factor, using a method not equivalent to trial division, such as Ferma'ts method.

Ok, this is a cheeky answer, exploiting your overprecise specification. Here are a few more.

- Sieve of Eratosthenes.
- Find the positive values of a certain notorious polynomial in 26 variables.
- Miller-Rabin to enough small bases. Exactly how many depends on whether anyone has proved ERH yet.

Paul
xilman is offline   Reply With Quote
Old 2006-08-16, 10:27   #4
Dougy
 
Dougy's Avatar
 
Aug 2004
Melbourne, Australia

23·19 Posts
Default

Thanks for your responses.

Wilson's theorem is an interesting example. Does it fit into a category I listed? I'm not sure.

By multiplying 1, 2, ..., n-1 together you're in effect trying to find two divisors of n in the list and get a zero congruence (or when n is prime, a non-zero congruence (ignoring the special case n=4)). So it's basically GCD(n,(n-1)!)=n if and only if n is composite. Arguably, this could be considered trial division.

I'm consider factorisation and the sieve method to be classed as trial division.

Your notorious polynomial with 26 variables? http://mathworld.wolfram.com/PrimeDi...Equations.html

I do not know what to think of this! Upon inspection of its proof (Jones et al. 1976) it has more perplexing ideas:

Theorem 5: If p is a prime number, then there is a proof that p is prime consisting of only 87 additions and multiplications.

This looks like a good example of a theorem that doesn't fit into one of the two categories I listed.

I'd be interested if there are other theorems people can come up with.
Dougy is offline   Reply With Quote
Old 2006-08-16, 11:14   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Default

Quote:
Originally Posted by Dougy View Post

Theorem 5: If p is a prime number, then there is a proof that p is prime consisting of only 87 additions and multiplications.

This looks like a good example of a theorem that doesn't fit into one of the two categories I listed.
Please note that the numbers that are being added/multiplied are exponentially
large in (log p).
R.D. Silverman is offline   Reply With Quote
Old 2006-08-16, 11:46   #6
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2·5,323 Posts
Default

Quote:
Originally Posted by Dougy View Post
I'm consider factorisation and the sieve method to be classed as trial division.
Fair enough, though you are misusing a technical term "trial division" to describe processes which it normally does not.

A much better phrase, IMO, would be something like "exhibit a divisor other than 1 and p", which covers all factorization methods and the SoE.

Paul
xilman is offline   Reply With Quote
Old 2006-08-16, 11:50   #7
Fusion_power
 
Fusion_power's Avatar
 
Aug 2003
Snicker, AL

7·137 Posts
Default

Translating some of the above into useful language. There are several methods of proving a number prime but at a cost in time that is unacceptably large. I can show you a factoring method that is different from any of the above but using it to factor a 10 million digit number would take longer to run than the universe has been in existence.

Fusion
Fusion_power is offline   Reply With Quote
Old 2006-08-16, 11:51   #8
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

1064610 Posts
Default

Quote:
Originally Posted by Dougy View Post
Sorry I haven't been around for a while - I've started a PhD in combinatorics and don't have much time to do things like this.

From my experience of primality proving, the tests that I have seen boil down to one of two things:
- Trial division.
- Proving that phi(n)=n-1, by proving that the multiplicative group Z_n has order n-1.

Do there exist primality tests that are essentially different? If so, could you please provide an example?

Note: I do not care about efficiency here.
ECPP.

Paul
xilman is offline   Reply With Quote
Old 2006-08-16, 11:57   #9
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Quote:
Originally Posted by xilman View Post
ECPP.

Paul
Granted, it doesn't work in Z/ZN, and neither do P+1 primality proofs. But both fall into the class of "determine order of some finite group, and voila it's a prime," just like P-1 proofs.

What about APR-CL? I know little about it, but afaik it uses the theory of algebraic number fields rather than the structure of a finite group.

Alex

Last fiddled with by akruppa on 2009-05-30 at 09:31
akruppa is offline   Reply With Quote
Old 2006-08-16, 16:18   #10
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2×5,323 Posts
Default

Quote:
Originally Posted by akruppa View Post
Granted, it doesn't work in Z/ZN, and neither do P+1 primality proofs. But both fall into the class of "determine order of some finite group, and voila it's a prime," just like P-1 proofs.

What about APRT-CL? I know little about it, but afaik it uses the theory of algebraic number fields rather than the structure of a finite group.

Alex
I was answering the question he asked. As you say, P+1 also doesn't fall into his Z/ZN classification.

Perhaps he's learning how to phrase his question.

Paul
xilman is offline   Reply With Quote
Old 2006-08-17, 00:18   #11
Dougy
 
Dougy's Avatar
 
Aug 2004
Melbourne, Australia

23×19 Posts
Default

Yes, I agree that my two categories are rather loosely defined. Mostly where these theorems fit is a matter of opinion. I must admit my ignorance with elliptic curves, so I cannot make a valid comment on ECPP.

I think APRT-CL is a good example, it looks fundamentally different.
Dougy is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Primality testing non-Mersennes lukerichards Software 8 2018-01-24 22:30
Testing an expression for primality 1260 Software 17 2015-08-28 01:35
a new Deterministic primality testing wsc812 Computer Science & Computational Number Theory 36 2013-03-04 06:25
Automated primality testing with LLRnet mdettweiler Conjectures 'R Us 18 2008-03-04 00:06
a new primality testing method jasong Math 1 2007-11-06 21:46

All times are UTC. The time now is 04:09.

Mon Apr 19 04:09:55 UTC 2021 up 10 days, 22:50, 0 users, load averages: 2.11, 1.88, 1.70

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.