"New" primality test/check

[gophne]

Originally Posted by jnml

> Quote:
> Originally Posted by gophne
> 5) Running the suspect algorithm for false negatives up to 1,000,000 none was found
> This has been confirmed unintentionally by one of the senior contributors on the site that
> was running the algorithm in Pari, I think -check some of the earlier posts.
> Fermat's Primality check has a problem with false negatives (Carmichael Numbers).

Please link that post you're talking about. Making claims that no one can verify is a typical crackpot tactic. Don't be a crackpot.

Hi jnml

Post #60

[gophne]

Originally Posted by science_man_88

http://www.mersenneforum.org/showthread.php?t=14901

Hi science_man_88

Thanks for the link....the way things are going, soon I am going to become very math literate, and as a consequence, much more of a gentleman and a scholar!

[Batalov]

Originally Posted by gophne

Hi jnml

I was referring to your post #60 it seems. - 0% negatives

Originally Posted by gophne

Hi jnml

Post #60

Originally Posted by Batalov

What is even more impressive is that all composite Mersenne numbers are 2-PRPs (even if you don't know it)

Read my lips.

Every 2^p-1 will be called prime by this method.

You could just as well use this test in its equivalent form:Input: 2^p-1. Return: prime!

That is why nobody uses 2-PRP method on Mersenne numbers. You get no new information. You run some calculation for some time and get a result: prime! My great test is so much better: Input: 2^p-1. Return: prime!

Do you understand?
Or do you need this repeated to you by five more people? They will!

[jnml]

Originally Posted by gophne

Post #60

That's not Pari code, that's Go code. No wonder I was not able to find it.

However, your interpretation of the results is mistaken. The "algorithm" simply clasified
every single candidate exponent in the range tested (below 10.000 BTW, not
1.000.000) as a probable prime, ie. the code demonstrated it's completely useles. However,
the side effect is that such "test" really has no false negatives, admitted.

Crosspoted with #201 above.

[science_man_88]

Originally Posted by gophne

Hi jnml

I was referring to your post #60 it seems. - 0% negatives

[gophne]

Originally Posted by Batalov

Read my lips.

Every 2^p-1 will be called prime by this method.

You could just as well use this test in its equivalent form:Input: 2^p-1. Return: prime!

That is why nobody uses 2-PRP method on Mersenne numbers. You get no new information. You run some calculation for some time and get a result: prime! My great test is so much better: Input: 2^p-1. Return: prime!

Do you understand?
Or do you need this repeated to you by five more people? They will!

Noted. Give me some time to digest what you say.

Regards

[gophne]

Originally Posted by jnml

That's not Pari code, that's Go code. No wonder I was not able to find it.

However, your interpretation of the results is mistaken. The "algorithm" simply clasified
every single candidate exponent in the range tested (below 10.000 BTW, not
1.000.000) as a probable prime, ie. the code demonstrated it's completely useles. However,
the side effect is that such "test" really has no false negatives, admitted.

Crosspoted with #201 above.

I was about to comment that you must mean "no false negatives" and not " no false positives", which you have now corrected.

[gophne]

Originally Posted by Batalov

Read my lips.

Every 2^p-1 will be called prime by this method.

You could just as well use this test in its equivalent form:Input: 2^p-1. Return: prime!

That is why nobody uses 2-PRP method on Mersenne numbers. You get no new information. You run some calculation for some time and get a result: prime! My great test is so much better: Input: 2^p-1. Return: prime!

Do you understand?
Or do you need this repeated to you by five more people? They will!

Hi Batalov

The algorithm does not return "positive" for all mersenne numbers 2^n-1

Algorithm: 2^n-1 mod (n+2) = (n+1)/2...if true (n+2) is prime, else composite, barring false positives :(

Check n = 5, 7, 9, 11 & 13...checking primality for (n+2)

n=05........2^n-1 mod (n+2) = 0031 mod 07 = 03 ........= (n+1)/2..........True, hence (n+2) is Prime
n=07........2^n-1 mod (n+2) = 0127 mod 09 = 01 ........<> (n+1)/2........False, hence (n+2) is Composite
n=09........2^n-1 mod (n+2) = 0511 mod 11 = 05 ........= (n+1)/2..........True, hence (n+2) is Prime
n=11........2^n-1 mod (n+2) = 2047 mod 13 = 06 ........= (n+1)/2..........True, hence (n+2) is Prime
n=13........2^n-1 mod (n+2) = 8191 mod 15 = 01 ........= (n+1)/2..........False, hence (n+2) is Composite

[science_man_88]

Originally Posted by gophne

Hi Batalov

The algorithm does not return "positive" for all mersenne numbers 2^n-1

Algorithm: 2^n-1 mod (n+2) = (n+1)/2...if true (n+2) is prime, else composite, barring false positives :(

Check n = 5, 7, 9 & 11...checking primality for (n+2)

n=05........2^n-1 mod (n+2) = 0031 mod 07 = 03 ........= (n+1)/2..........True, hence (n+2) is Prime
n=07........2^n-1 mod (n+2) = 0127 mod 07 = 01 ........<> (n+1)/2........False, hence (n+2) is Composite
n=09........2^n-1 mod (n+2) = 0511 mod 11 = 05 ........= (n+1)/2..........True, hence (n+2) is Prime!!!!!..... False Prime
n=11........2^n-1 mod (n+2) = 2047 mod 13 = 06 ........= (n+1)/2..........True, hence (n+2) is Prime!!!!!

11 is a prime. Check the case n= 339

[CRGreathouse]

Originally Posted by gophne

Hi Batalov

The algorithm does not return "positive" for all mersenne numbers 2^n-1

Batalov's claim is that if n+2 = 2^p - 1, your algorithm returns "prime" regardless of whether 2^p - 1 is prime or composite. If n+2 is composite. For example, set n = 2045 and check that the test is passed

2^n-1 mod (n+2) =? (n+1)/2
2^2045 - 1 mod 2047 =? 1023
1023 = 1023

but note that 2047 = 23*89.

[gophne]

Originally Posted by science_man_88

11 is a prime. Check the case n= 339

Hi science_man _88

Sorry "11" was a logic error, I corrected my post for that subsequently.

Correct. For n=341 and (n+2) =341 returns as a false prime (1st false prime of the algorithm). There are 750 false primes up to 10,000,000 as per SAGEMATH code that I ran...[result subject to confirmation by others]

Sorry for the mistake, due to cut & paste.