mersenneforum.org  

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

Reply
 
Thread Tools
Old 2017-12-29, 00:21   #67
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

17×563 Posts
Default

Quote:
Originally Posted by gophne View Post
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!
Batalov is offline   Reply With Quote
Old 2017-12-29, 01:18   #68
gophne
 
Feb 2017

3·5·11 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.
gophne is offline   Reply With Quote
Old 2017-12-29, 02:18   #69
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

22·5·11·53 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.
ewmayer is offline   Reply With Quote
Old 2017-12-29, 02:23   #70
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100101011000112 Posts
Default

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!"
Batalov is offline   Reply With Quote
Old 2017-12-29, 02:35   #71
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

23×433 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.
chalsall is online now   Reply With Quote
Old 2017-12-29, 04:57   #72
gophne
 
Feb 2017

101001012 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.
gophne is offline   Reply With Quote
Old 2017-12-29, 05:54   #73
gophne
 
Feb 2017

3·5·11 Posts
Default 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
gophne is offline   Reply With Quote
Old 2017-12-29, 06:19   #74
gophne
 
Feb 2017

3×5×11 Posts
Exclamation 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
gophne is offline   Reply With Quote
Old 2017-12-29, 06:41   #75
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

22·5·11·53 Posts
Default

Quote:
Originally Posted by gophne View Post
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.
ewmayer is offline   Reply With Quote
Old 2017-12-29, 06:45   #76
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

17·563 Posts
Default

Quote:
Originally Posted by gophne View Post
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 View Post
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.
Batalov is offline   Reply With Quote
Old 2017-12-29, 06:49   #77
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

26E716 Posts
Default

Quote:
Originally Posted by Batalov View Post
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...
chalsall 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 2733 2021-10-13 10:39
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 22:27.


Fri Oct 22 22:27:57 UTC 2021 up 91 days, 16:56, 0 users, load averages: 1.99, 2.08, 2.25

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.