mersenneforum.org (https://www.mersenneforum.org/index.php)
-   gophne (https://www.mersenneforum.org/forumdisplay.php?f=149)
-   -   "New" primality test/check (https://www.mersenneforum.org/showthread.php?t=22838)

 Batalov 2017-12-29 00:21

[QUOTE=gophne;475141]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....[COLOR="Red"]n-2[/COLOR] <-- what the hell is this?
#2......b=(2^7-1)-2.............[COLOR="Red"]n~125[/COLOR]
#3......c=1/2*(b+1).............[COLOR="Red"]Target Congruant~63[/COLOR]
#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[/QUOTE]
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!

 gophne 2017-12-29 01:18

[QUOTE=Batalov;475223]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![/QUOTE]
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.........[COLOR="Red"]Modulo Dividend???[/COLOR]~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 [B]25[/B] in step #1. That would make the divisor in step #2, [B]27[/B]~(n+2). or (a+2) if you like. I only used mersenne notation because jnml was working with M[I]n[/I] 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.

 ewmayer 2017-12-29 02:18

[QUOTE=Batalov;475223]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![/QUOTE]

No true negatives, either - but hey, who needs all that negativity, it's harshing the holiday spirit, and stuff.

 Batalov 2017-12-29 02:23

[QUOTE="old TV cartoon"]That's why we called him Neutron! He is always so positive![/QUOTE]
[COLOR=Wheat].[/COLOR]

 chalsall 2017-12-29 02:35

[QUOTE=Batalov;475233]That's why we called him Neutron! He is always so positive![/QUOTE]

Umm... Wasn't that the Protons?

At least one of the Electrons refused to play game.

 gophne 2017-12-29 04:57

[QUOTE=Batalov;475223]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![/QUOTE]
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 [B]2^9-1 & 2^15-1[/B], 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 2017-12-29 05:54

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.

 gophne 2017-12-29 06:19

Restatement of Algorithm for Use and Testing

If (2^n-1) [B]mod[/B] (n+2) = (n+1)/2, then (n+2) is PRIME, else COMPOSITE, [I]n[/I] being an element of the set of positive integers =>1

 ewmayer 2017-12-29 06:41

[QUOTE=gophne;475261]If (2^n-1) [B]mod[/B] (n+2) = (n+1)/2, then (n+2) is PRIME, else COMPOSITE, [I]n[/I] being an element of the set of positive integers =>1[/QUOTE]

Yeah, we heard you the first million-and-six times. Try (n+2) = 2047 = 23*89 in your formula.

 Batalov 2017-12-29 06:45

[QUOTE=gophne;475252]
I do not understand what you are saying about 2-PRP's [/QUOTE]
A person who walks off a 1km cliff also doesn't understand that he is already dead.
But he is.
[QUOTE=gophne;475261][B]Restatement of Algorithm for Use and Testing
[/B]If (2^n-1) [B]mod[/B] (n+2) = (n+1)/2, then (n+2) is PRIME, else COMPOSITE, [I]n[/I] being an element of the set of positive integers =>1[/QUOTE]
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) [B]mod[/B] (n+2) = (n+1)/2, then (n+2) is PRIME? Wrong. It is composite. [URL="https://en.wikipedia.org/wiki/Fermat%27s_little_theorem#Pseudoprimes"]F. Sarrus in 1820 found 341[/URL] as one of the first pseudoprimes, to base 2. That was 197 years ago.
Try n+2 == 561. (2^n-1) [B]mod[/B] (n+2) = (n+1)/2, then (n+2) is PRIME? Wrong. It is composite.
Try n+2 == 645. (2^n-1) [B]mod[/B] (n+2) = (n+1)/2, then (n+2) is PRIME? Wrong. It is composite.

 chalsall 2017-12-29 06:49

[QUOTE=Batalov;475266]A person who walks off a 1km cliff also doesn't understand that he is already dead.[/QUOTE]

It's not the fall which kills them. It's the hard stop at the end...

All times are UTC. The time now is 05:12.