mersenneforum.org > Math Alternate means of primality testing
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2006-08-16, 02:30 #1 Dougy     Aug 2004 Melbourne, Australia 23×19 Posts 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.
 2006-08-16, 04:51 #2 bearnol     Sep 2005 127 Posts Well, I suppose there's always Wilson's Theorem - you did say you weren't concerned with efficiency! J
2006-08-16, 09:03   #3
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

10,639 Posts

Quote:
 Originally Posted by Dougy 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

 2006-08-16, 10:27 #4 Dougy     Aug 2004 Melbourne, Australia 100110002 Posts 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.
2006-08-16, 11:14   #5
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by Dougy 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).

2006-08-16, 11:46   #6
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

246178 Posts

Quote:
 Originally Posted by Dougy 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

 2006-08-16, 11:50 #7 Fusion_power     Aug 2003 Snicker, AL 7·137 Posts 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
2006-08-16, 11:51   #8
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

10,639 Posts

Quote:
 Originally Posted by Dougy 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

2006-08-16, 11:57   #9
akruppa

"Nancy"
Aug 2002
Alexandria

2,467 Posts

Quote:
 Originally Posted by xilman 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

2006-08-16, 16:18   #10
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

1063910 Posts

Quote:
 Originally Posted by akruppa 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

 2006-08-17, 00:18 #11 Dougy     Aug 2004 Melbourne, Australia 23·19 Posts 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post lukerichards Software 8 2018-01-24 22:30 1260 Software 17 2015-08-28 01:35 wsc812 Computer Science & Computational Number Theory 36 2013-03-04 06:25 mdettweiler Conjectures 'R Us 18 2008-03-04 00:06 jasong Math 1 2007-11-06 21:46

All times are UTC. The time now is 14:57.

Sun Apr 11 14:57:55 UTC 2021 up 3 days, 9:38, 1 user, load averages: 2.18, 1.86, 1.70