20180105, 22:17  #210  
Feb 2017
165_{10} Posts 
Quote:
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. 

20180105, 22:26  #211  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:


20180105, 23:17  #212 
Nov 2008
2·3^{3}·43 Posts 
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. 
20180106, 02:16  #213 
Feb 2017
3·5·11 Posts 

20180106, 02:19  #214 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 

20180106, 03:19  #215  
Feb 2017
3·5·11 Posts 
Quote:
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 20180106 at 03:28 Reason: adding line spaces between questions posed to 10metreh for clarity 

20180106, 03:23  #216 
Feb 2017
3×5×11 Posts 

20180106, 03:45  #217 
If I May
"Chris Halsall"
Sep 2002
Barbados
249F_{16} Posts 

20180106, 04:19  #218 
Feb 2017
245_{8} Posts 

20180106, 05:43  #219  
Aug 2006
5,939 Posts 
I'm not 10metreh but I'll take a whack at it.
Quote:
Quote:
Quote:
This is worth studying! Quote:
Quote:
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 20180106 at 05:44 

20180106, 10:18  #220  
Dec 2012
The Netherlands
3^{2}·13^{2} Posts 
Quote:
and http://www.mersenneforum.org/showthread.php?t=21756 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
gpuOwL: an OpenCL program for Mersenne primality testing  preda  GpuOwl  2609  20201201 23:42 
GQQ: a "deterministic" "primality" test in O(ln n)^2  Chair Zhuang  Miscellaneous Math  21  20180326 22:33 
AouessareEl HaddouchiEssaaidi "test": "if Mp has no factor, it is prime!"  wildrabbitt  Miscellaneous Math  11  20150306 08:17 
"New primality proving test from Alex Petrov"  ewmayer  Math  11  20070423 19:07 
P1 B1/B2 selection with "Test=" vs "Pfactor="  James Heinrich  Software  2  20050319 21:58 