mersenneforum.org "New" primality test/check
 Register FAQ Search Today's Posts Mark Forums Read

2018-01-05, 19:41   #199
gophne

Feb 2017

2458 Posts

Quote:
 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

2018-01-05, 19:50   #200
gophne

Feb 2017

3×5×11 Posts

Quote:
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!

2018-01-05, 19:54   #201
Batalov

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

3×5×17×37 Posts

Quote:
 Originally Posted by gophne Hi jnml I was referring to your post #60 it seems. - 0% negatives
Quote:
 Originally Posted by gophne Hi jnml Post #60
Quote:
 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)

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!

2018-01-05, 19:56   #202
jnml

Feb 2012
Prague, Czech Republ

AB16 Posts

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

Last fiddled with by jnml on 2018-01-05 at 19:58 Reason: s/positives/negatives/

2018-01-05, 20:01   #203
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

203008 Posts

Quote:
 Originally Posted by gophne Hi jnml I was referring to your post #60 it seems. - 0% negatives

2018-01-05, 20:02   #204
gophne

Feb 2017

3×5×11 Posts

Quote:
 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

2018-01-05, 20:05   #205
gophne

Feb 2017

A516 Posts

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

2018-01-05, 21:32   #206
gophne

Feb 2017

3×5×11 Posts

Quote:
 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

Last fiddled with by gophne on 2018-01-05 at 21:47 Reason: correction to logic

2018-01-05, 21:36   #207
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 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

Last fiddled with by science_man_88 on 2018-01-05 at 21:45

2018-01-05, 22:07   #208
CRGreathouse

Aug 2006

32×5×7×19 Posts

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

2018-01-05, 22:13   #209
gophne

Feb 2017

3×5×11 Posts

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

 Similar Threads Thread Thread Starter Forum Replies Last Post preda GpuOwl 2711 2021-05-16 01:04 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 05:41.

Sun May 16 05:41:17 UTC 2021 up 38 days, 22 mins, 0 users, load averages: 1.50, 1.82, 1.68