mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > gophne

Reply
 
Thread Tools
Old 2018-01-05, 22:17   #210
gophne
 
Feb 2017

3·5·11 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Batalov's claim is that if n+2 = 2^p - 1, your algorithm returns "prime" regardless of whether 2^p - 1 is prime or composite. If n+2 is composite. For example, set n = 2045 and check that the test is passed

2^n-1 mod (n+2) =? (n+1)/2
2^2045 - 1 mod 2047 =? 1023
1023 = 1023

but note that 2047 = 23*89.
Hi CRGreathouse

That is correct. the algorithm returns 750 false primes up to 10,000,000 according to SAGEMATH code I ran (Subject to confirmation by others)

The 1st false prime for the algorithm (and Fermat's Primality Test, base 2) occurs at 341.
2047 also returns a false positive as you point out.
gophne is offline   Reply With Quote
Old 2018-01-05, 22:26   #211
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

Quote:
Originally Posted by gophne View Post
Hi CRGreathouse

That is correct. the algorithm returns 750 false primes up to 10,000,000 according to SAGEMATH code I ran (Subject to confirmation by others)

The 1st false prime for the algorithm (and Fermat's Primality Test, base 2) occurs at 341.
2047 also returns a false positive as you point out.
And how many does Fermat's return ...
science_man_88 is offline   Reply With Quote
Old 2018-01-05, 23:17   #212
10metreh
 
10metreh's Avatar
 
Nov 2008

2×33×43 Posts
Default

Gophne, as actual proofs don't seem to have persuaded you, let's have a look at an example to see that the two tests are the same. I'm going to avoid modular arithmetic as much as possible because it seems to have caused a bit of confusion.

Suppose we are trying to test 561 for primality, so n = 559 in your test.

Fermat's test declares 561 prime. This is because 2^560 ≡ 1 (mod 561), i.e. 2^560 = 561m + 1 for some m.
Note that m is odd (it must be odd because the LHS is even, but you can also see this by calculating it directly if you wish), so m = 2k+1 for some k.
Therefore 2^560 = 561(2k+1) + 1 = 1122k + 562.
Divide both sides by 2: 2^559 = 561k + 281.
Subtract 1: 2^559 - 1 = 561k + 280
So "(2^559 - 1) mod 561 = 280" (quotation marks because this is bad notation), and 280 = (559+1)/2 so your test declares 561 prime.

Similarly, Fermat primality => gophne primality in general.

Going the other way:

Your test declares 561 prime. This is because (559+1)/2 = 280 and "(2^559 - 1) mod 561 = 280", i.e. 2^559 - 1 = 561k + 280 for some k.
Add 1: 2^559 = 561k + 281.
Multiply by 2: 2^560 = 1122k + 562 = 561(2k+1) + 1
So 2^560 = 561m + 1 for some m, i.e. 2^560 ≡ 1 (mod 561), and Fermat's test declares 561 prime.

Similarly, gophne primality => Fermat primality in general, so they are in fact the same test.

To turn these examples into a proper proof, just replace 559 with n, and remember that we are carrying out the primality tests on n+2 not n.
10metreh is offline   Reply With Quote
Old 2018-01-06, 02:16   #213
gophne
 
Feb 2017

3·5·11 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
And how many does Fermat's return ...
I have not run that myself, but I suspect the same based on the analysis 10metreh has done previously.
gophne is offline   Reply With Quote
Old 2018-01-06, 02:19   #214
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

Quote:
Originally Posted by gophne View Post
I have not run that myself, but I suspect the same based on the analysis 10metreh has done previously.
Okay so what is your sticking point? Is it that there's many ways to select that many from the set of natural numbers in that interval ?
science_man_88 is offline   Reply With Quote
Old 2018-01-06, 03:19   #215
gophne
 
Feb 2017

3·5·11 Posts
Default

Quote:
Originally Posted by 10metreh View Post
Gophne, as actual proofs don't seem to have persuaded you, let's have a look at an example to see that the two tests are the same. I'm going to avoid modular arithmetic as much as possible because it seems to have caused a bit of confusion.

Suppose we are trying to test 561 for primality, so n = 559 in your test.

Fermat's test declares 561 prime. This is because 2^560 ≡ 1 (mod 561), i.e. 2^560 = 561m + 1 for some m.
Note that m is odd (it must be odd because the LHS is even, but you can also see this by calculating it directly if you wish), so m = 2k+1 for some k.
Therefore 2^560 = 561(2k+1) + 1 = 1122k + 562.
Divide both sides by 2: 2^559 = 561k + 281.
Subtract 1: 2^559 - 1 = 561k + 280
So "(2^559 - 1) mod 561 = 280" (quotation marks because this is bad notation), and 280 = (559+1)/2 so your test declares 561 prime.

Similarly, Fermat primality => gophne primality in general.

Going the other way:

Your test declares 561 prime. This is because (559+1)/2 = 280 and "(2^559 - 1) mod 561 = 280", i.e. 2^559 - 1 = 561k + 280 for some k.
Add 1: 2^559 = 561k + 281.
Multiply by 2: 2^560 = 1122k + 562 = 561(2k+1) + 1
So 2^560 = 561m + 1 for some m, i.e. 2^560 ≡ 1 (mod 561), and Fermat's test declares 561 prime.

Similarly, gophne primality => Fermat primality in general, so they are in fact the same test.

To turn these examples into a proper proof, just replace 559 with n, and remember that we are carrying out the primality tests on n+2 not n.
Hi 10metreh

Now how was I expected to know/understand that! But it all make sense again, and I yet again must (for the last time, I promise) agree that the two algorithms are the same as you have explained again...(gnashing of teeth).

Just a few questions to you that I would like you to honestly answer please.

1) How many people out there would have been able to do the reduction that you have just done? I suspect very few, and very few ppl would be able to even understand what you have done right now, eccept of course math people that have studied these things assiduously.

2) How was Fermat's Little Theorem/Fermat's Primality Test "derived". I am asking out of interest, if you know.

3) Having now finally accepted that the two theorems are the same because of your explaination/reductions (and awmayer I think), would you agree that by using the algorithm in the form of the mersenne number modulo is a very interesting way to do it, since it establishes a direct relationship between mersenne numbers and ALL prime numbers -the hidden pattern of Prime numbers.....surely the holy grail everybody in prime exploration was looking for. Was the Fermat Little theorem/Primality test ever presented or investigated in this way? Can you give some references (or other contributors could as well if the have the info)?

4) Do you agree that the "mersenne number" way of expressing then the Fermat's Little theorem, base 2 could also help with factorization of mersenne numbers, something the standard form of the Fermat Primality Test does not do. This is because when you are testing the mersenne numbers modulo vs the odd numbers, the remainders of the modulo operation is cyclical, starting with 1 and terminating with (n+1)/2, when the odd number is prime or a false prime I suspect as well. When a particular odd number is a factor of a particular mersenne number, the the 0 remainder, falls at the centre of the modulo cycle that ends with (n+1)/2. This could be algorithmized into some sort of checker for mersenne number compositeness.

5) Lastly, as you have shown again so eloquently, that the "mersenne form" algorithm, is one and the same as the Fermat Primality Test, why did some expert ppl at first crack up the"algorithm" as "nonsense". Are they saying that Fermat's Primality Test is nonsense (or did they not know what you know?)

Thank you (and awmayer in the first place) for your definitive explanation.

Last fiddled with by gophne on 2018-01-06 at 03:28 Reason: adding line spaces between questions posed to 10metreh for clarity
gophne is offline   Reply With Quote
Old 2018-01-06, 03:23   #216
gophne
 
Feb 2017

3×5×11 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
Okay so what is your sticking point? Is it that there's many ways to select that many from the set of natural numbers in that interval ?
Nope it is clear, check 10metreh's post #212
gophne is offline   Reply With Quote
Old 2018-01-06, 03:45   #217
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

67×139 Posts
Default

Quote:
Originally Posted by gophne View Post
Nope it is clear, check 10metreh's post #212
Wow! This is almost as painful as watching Trump implode.
chalsall is online now   Reply With Quote
Old 2018-01-06, 04:19   #218
gophne
 
Feb 2017

16510 Posts
Default

Quote:
Originally Posted by chalsall View Post
Wow! This is almost as painful as watching Trump implode.
Hi chalsall

How is it similar?...are you comparing me to President Trump/ or are you feelling pain at President Trump's implosion, or both?

Very interesting, please elucidate a little bit more.
gophne is offline   Reply With Quote
Old 2018-01-06, 05:43   #219
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10111001000112 Posts
Default

I'm not 10metreh but I'll take a whack at it.

Quote:
Originally Posted by gophne View Post
1) How many people out there would have been able to do the reduction that you have just done? I suspect very few, and very few ppl would be able to even understand what you have done right now, eccept of course math people that have studied these things assiduously.
I would hope that (almost) everyone with a degree in mathematics could do it. US universities grant ~20,000 bachelor's degrees per year in mathematics and statistics, so maybe on the order of a million people in the US. Of course some people with such degrees couldn't do it, and some people without degrees could, but probably not as few as 100,000 or as many as 10 million in the US. Worldwide, maybe 10 times as many?

Quote:
Originally Posted by gophne View Post
3) Having now finally accepted that the two theorems are the same because of your explaination/reductions (and awmayer I think), would you agree that by using the algorithm in the form of the mersenne number modulo is a very interesting way to do it, since it establishes a direct relationship between mersenne numbers and ALL prime numbers -the hidden pattern of Prime numbers.....surely the holy grail everybody in prime exploration was looking for.
I would not, because you could use any base, not just base 2. Instead of getting A001567 = 341, 561, 645, 1105, ... as exceptions, you'd get A005935 = 91, 121, 286, 671, 703, 949, .... (base 3), A005936 = 4, 124, 217, 561, 781, 1541, 1729, ... etc. as exceptions. (We refer to them as pseudoprimes, actually.)

Quote:
Originally Posted by gophne View Post
4) Do you agree that the "mersenne number" way of expressing then the Fermat's Little theorem, base 2 could also help with factorization of mersenne numbers
I don't see an advantage to either form. Regardless, it's an interesting question as to whether Fermat tests (or more likely, Miller tests) could be used to factor numbers. In general I don't see an efficient way to do this, but if you can get some composite to pass many (say, 2 to 20) Fermat/Miller tests, you could probably find a factorization of the number. (It works especially well on Carmichael numbers, where I think you can get polynomial expected time factorizations.)

This is worth studying!

Quote:
Originally Posted by gophne View Post
5) Lastly, as you have shown again so eloquently, that the "mersenne form" algorithm, is one and the same as the Fermat Primality Test, why did some expert ppl at first crack up the"algorithm" as "nonsense". Are they saying that Fermat's Primality Test is nonsense (or did they not know what you know?)
Reviewing the first few pages of this thread, it seems like no one was calling your algorithm nonsense. Rather, they thought that your claims were unlikely, to wit:

Quote:
Originally Posted by gophne View Post
The algorithm is very clear.
ALL primes are covered- tested to M34 -2^1,257,787-1, Seriously!
ALL composites are identified!
Time O(log n) -Very very fast. Serious.
ALL primes are defined -NO false primes expected as per algorithm logic.
The algorith is a logical formulation, so can be verified quickly.
If authenticated, will compare to simplicity of Euclid's Proof for Infinite number of Primes.
If true, will be a new frontier in PNT
Let's score these. I think your algorithm is pretty clear. You first defined it, I think, here:
Quote:
Originally Posted by gophne View Post
2^n-1 mod (n+2)= 1/2*(2^n-1)+1
where the only wrinkle is that you hadn't yet mentioned that it was a test for n+2 rather than n. All primes are covered. You hadn't tested it up to 2^1257787 - 1, though, which you did have the courage to admit in post #36. Not all composites are identified. It doesn't run in O(log n), it's Omega(log^2 n). The algorithm can't be verified at all (let alone quickly) because it doesn't perform as advertised. I'll give you your claim on simplicity -- it's an elegant method. Your final claim is vacuously true... it didn't authenticate, so there's no requirement that it be a new frontier.

All in all, I think the skepticism was warranted. No doubt the skepticism could have been expressed more kindly though; sometimes we're not as welcoming as we'd like to be.

Last fiddled with by CRGreathouse on 2018-01-06 at 05:44
CRGreathouse is offline   Reply With Quote
Old 2018-01-06, 10:18   #220
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

3×479 Posts
Default

Quote:
Originally Posted by gophne View Post
2) How was Fermat's Little Theorem/Fermat's Primality Test "derived". I am asking out of interest, if you know.
See http://www.mersenneforum.org/showthread.php?t=21737
and http://www.mersenneforum.org/showthread.php?t=21756
Nick is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
gpuOwL: an OpenCL program for Mersenne primality testing preda GpuOwl 2475 2020-09-24 12:23
GQQ: a "deterministic" "primality" test in O(ln n)^2 Chair Zhuang Miscellaneous Math 21 2018-03-26 22:33
Aouessare-El Haddouchi-Essaaidi "test": "if Mp has no factor, it is prime!" wildrabbitt Miscellaneous Math 11 2015-03-06 08:17
"New primality proving test from Alex Petrov" ewmayer Math 11 2007-04-23 19:07
P-1 B1/B2 selection with "Test=" vs "Pfactor=" James Heinrich Software 2 2005-03-19 21:58

All times are UTC. The time now is 15:33.

Thu Sep 24 15:33:28 UTC 2020 up 14 days, 12:44, 1 user, load averages: 1.60, 1.60, 1.57

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.