mersenneforum.org "New" primality test/check
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2017-12-29, 00:21   #67
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23×1,201 Posts

Quote:
 Originally Posted by gophne Hi jnml Using the algorithm (sagemath), I get positive result for M3, M5 & M17. I could not test beyound M29 (dividend) due to unknown run time). e.g. M3 (2^7-1) #1......a=2^7-1..................Divisor under test~127....n-2 <-- what the hell is this? #2......b=(2^7-1)-2.............n~125 #3......c=1/2*(b+1).............Target Congruant~63 #4......d=2^b-1...................Dividend~42,535,295,865,117,307,932,921,825,928,971,026,431 #5.......e=d mod a..............Congruant~63 #6.......c==e.......................True~127(divisor) is Prime
So after all your talk about n this, n that, your own scribbling show that you suddenly call n-2 "n". Then of course, your "n+2" is n.

Congratulations! You proved that all primes are 2-PRP.
What is even more impressive is that all composite Mersenne numbers are 2-PRPs (even if you don't know it), so your test will just call them all prime. No false negatives!

2017-12-29, 01:18   #68
gophne

Feb 2017

3·5·11 Posts

Quote:
 Originally Posted by Batalov So after all your talk about n this, n that, your own scribbling show that you suddenly call n-2 "n". Then of course, your "n+2" is n. Congratulations! You proved that all primes are 2-PRP. What is even more impressive is that all composite Mersenne numbers are 2-PRPs (even if you don't know it), so your test will just call them all prime. No false negatives!
Hi batalov

That is how I coded the algorithm (in SAGE)....if you like I could(should?) have coded the algorithm as follows as well -I did the above to put the "number" being tested as step #1.

#1.......a=(2^7-1)-2.........Modulo Dividend???~125 (should be the dividend "seed" value to get "d", the real Modulo dividend as per the algorithm.
#2.......b=2^7-1...............Modulo Divisor~(a+2=127)....NUMBER UNDER TEST
#3.......c=(a+1)/2............Modulo Target Congruant~63
#4.......d=2^a-1..............Modulo Divident~ As above
#5.......e=d mod a..........Algorithm Congruant=63
#6.......c==e....................True~127(Divisor) is Prime

To simplify further you could simply call the Divident seed 25 in step #1. That would make the divisor in step #2, 27~(n+2). or (a+2) if you like. I only used mersenne notation because jnml was working with Mn notation, which would be more practical if very large numbers are to be considered.

I am trying my best to be clear, but bear with me that I am trying to translate my code into words. I will try to type some actual code of a working page as I code the algorithm in SAGEMATH. But everybody would code differently depending on their expertise in SAGEMATH. My coding skills in SAGE are moderate.

2017-12-29, 02:18   #69
ewmayer
2ω=0

Sep 2002
República de California

101101100110012 Posts

Quote:
 Originally Posted by Batalov Congratulations! You proved that all primes are 2-PRP. What is even more impressive is that all composite Mersenne numbers are 2-PRPs (even if you don't know it), so your test will just call them all prime. No false negatives!
No true negatives, either - but hey, who needs all that negativity, it's harshing the holiday spirit, and stuff.

2017-12-29, 02:23   #70
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

258816 Posts

Quote:
 Originally Posted by old TV cartoon That's why we called him Neutron! He is always so positive!
.

Last fiddled with by ewmayer on 2017-12-29 at 04:40 Reason: Ha, ha, nice to see another TIE fan in the house - "I feel like new toothbrush!"

2017-12-29, 02:35   #71
chalsall
If I May

"Chris Halsall"
Sep 2002
Barbados

10,039 Posts

Quote:
 Originally Posted by Batalov That's why we called him Neutron! He is always so positive!
Umm... Wasn't that the Protons?

At least one of the Electrons refused to play game.

2017-12-29, 04:57   #72
gophne

Feb 2017

3·5·11 Posts

Quote:
 Originally Posted by Batalov So after all your talk about n this, n that, your own scribbling show that you suddenly call n-2 "n". Then of course, your "n+2" is n. Congratulations! You proved that all primes are 2-PRP. What is even more impressive is that all composite Mersenne numbers are 2-PRPs (even if you don't know it), so your test will just call them all prime. No false negatives!
hi batalov

I do not understand what you are saying about 2-PRP's ....are you running the algorithm? What are your results?

I do not get all "composite mersenne numbers" to be false positives, on the contrary, e.g 2^9-1 & 2^15-1, do not register as a false positives but as composite in the algorithm.

Please post your results, you could even do the calculation on a calculator or Excel at this level of magnitude.

 2017-12-29, 05:54 #73 gophne   Feb 2017 3·5·11 Posts SAGEMATH CODE for False Positives Here is SAGEMATH code to check for false positive (prime) results (for the algorithm) up to 1,000,000. Should only take a few minutes to run. [1] x=0 [2] for y in range(1,1000000,2): z= next_prime(y) a= y+2; #Modulo Divisor....Number under test b= 2^y-1; #Modulo Dividend c= b%a; #Algorithm Modulo Congruent d= (y+1)/2; #Target Congruent as per Algorithm if c==d: if z>a: x=x+1 print(a,x); # 'a' is the False Positive identified, 'x' is a counter The SAGEMATH software will automatically do the indentation for the code. Last fiddled with by gophne on 2017-12-29 at 05:56 Reason: adding semi-colon to step 8 of cell 2
 2017-12-29, 06:19 #74 gophne   Feb 2017 16510 Posts Restatement of Algorithm for Use and Testing If (2^n-1) mod (n+2) = (n+1)/2, then (n+2) is PRIME, else COMPOSITE, n being an element of the set of positive integers =>1
2017-12-29, 06:41   #75
ewmayer
2ω=0

Sep 2002
República de California

32·1,297 Posts

Quote:
 Originally Posted by gophne If (2^n-1) mod (n+2) = (n+1)/2, then (n+2) is PRIME, else COMPOSITE, n being an element of the set of positive integers =>1
Yeah, we heard you the first million-and-six times. Try (n+2) = 2047 = 23*89 in your formula.

2017-12-29, 06:45   #76
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23·1,201 Posts

Quote:
 Originally Posted by gophne I do not understand what you are saying about 2-PRP's
A person who walks off a 1km cliff also doesn't understand that he is already dead.
But he is.
Quote:
 Originally Posted by gophne Restatement of Algorithm for Use and Testing If (2^n-1) mod (n+2) = (n+1)/2, then (n+2) is PRIME, else COMPOSITE, n being an element of the set of positive integers =>1
This is exactly what is called a 2-PRP test. 1) It is >350 years old. 2) It is false.
Try n+2 == 341. (2^n-1) mod (n+2) = (n+1)/2, then (n+2) is PRIME? Wrong. It is composite. F. Sarrus in 1820 found 341 as one of the first pseudoprimes, to base 2. That was 197 years ago.
Try n+2 == 561. (2^n-1) mod (n+2) = (n+1)/2, then (n+2) is PRIME? Wrong. It is composite.
Try n+2 == 645. (2^n-1) mod (n+2) = (n+1)/2, then (n+2) is PRIME? Wrong. It is composite.

2017-12-29, 06:49   #77
chalsall
If I May

"Chris Halsall"
Sep 2002
Barbados

10,039 Posts

Quote:
 Originally Posted by Batalov A person who walks off a 1km cliff also doesn't understand that he is already dead.
It's not the fall which kills them. It's the hard stop at the end...

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post preda GpuOwl 2734 2021-11-14 05:33 Chair Zhuang Miscellaneous Math 21 2018-03-26 22:33 wildrabbitt Miscellaneous Math 11 2015-03-06 08:17 ewmayer Math 11 2007-04-23 19:07 James Heinrich Software 2 2005-03-19 21:58

All times are UTC. The time now is 21:08.

Sat Nov 27 21:08:23 UTC 2021 up 127 days, 15:37, 0 users, load averages: 1.30, 1.33, 1.21

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.