"New" primality test/check

[Batalov]

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!

[gophne]

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.

[ewmayer]

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.

[Batalov]

Originally Posted by old TV cartoon

That's why we called him Neutron! He is always so positive!

.

[chalsall]

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.

[gophne]

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.

[gophne]

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]

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

[ewmayer]

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.

[Batalov]

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.

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.

[chalsall]

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...