"New" primality test/check

[gophne]

Originally Posted by CRGreathouse

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.

Hi CRGreathouse

That is correct. the algorithm returns 750 false primes up to 10,000,000 according to SAGEMATH code I ran (Subject to confirmation by others)

The 1st false prime for the algorithm (and Fermat's Primality Test, base 2) occurs at 341.
2047 also returns a false positive as you point out.

[science_man_88]

Originally Posted by gophne

Hi CRGreathouse

That is correct. the algorithm returns 750 false primes up to 10,000,000 according to SAGEMATH code I ran (Subject to confirmation by others)

The 1st false prime for the algorithm (and Fermat's Primality Test, base 2) occurs at 341.
2047 also returns a false positive as you point out.

And how many does Fermat's return ...

[10metreh]

Gophne, as actual proofs don't seem to have persuaded you, let's have a look at an example to see that the two tests are the same. I'm going to avoid modular arithmetic as much as possible because it seems to have caused a bit of confusion.

Suppose we are trying to test 561 for primality, so n = 559 in your test.

Fermat's test declares 561 prime. This is because 2^560 ≡ 1 (mod 561), i.e. 2^560 = 561m + 1 for some m.
Note that m is odd (it must be odd because the LHS is even, but you can also see this by calculating it directly if you wish), so m = 2k+1 for some k.
Therefore 2^560 = 561(2k+1) + 1 = 1122k + 562.
Divide both sides by 2: 2^559 = 561k + 281.
Subtract 1: 2^559 - 1 = 561k + 280
So "(2^559 - 1) mod 561 = 280" (quotation marks because this is bad notation), and 280 = (559+1)/2 so your test declares 561 prime.

Similarly, Fermat primality => gophne primality in general.

Going the other way:

Your test declares 561 prime. This is because (559+1)/2 = 280 and "(2^559 - 1) mod 561 = 280", i.e. 2^559 - 1 = 561k + 280 for some k.
Add 1: 2^559 = 561k + 281.
Multiply by 2: 2^560 = 1122k + 562 = 561(2k+1) + 1
So 2^560 = 561m + 1 for some m, i.e. 2^560 ≡ 1 (mod 561), and Fermat's test declares 561 prime.

Similarly, gophne primality => Fermat primality in general, so they are in fact the same test.

To turn these examples into a proper proof, just replace 559 with n, and remember that we are carrying out the primality tests on n+2 not n.

[gophne]

Originally Posted by science_man_88

And how many does Fermat's return ...

I have not run that myself, but I suspect the same based on the analysis 10metreh has done previously.

[science_man_88]

Originally Posted by gophne

I have not run that myself, but I suspect the same based on the analysis 10metreh has done previously.

Okay so what is your sticking point? Is it that there's many ways to select that many from the set of natural numbers in that interval ?

[gophne]

Originally Posted by 10metreh

Gophne, as actual proofs don't seem to have persuaded you, let's have a look at an example to see that the two tests are the same. I'm going to avoid modular arithmetic as much as possible because it seems to have caused a bit of confusion.

Suppose we are trying to test 561 for primality, so n = 559 in your test.

Fermat's test declares 561 prime. This is because 2^560 ≡ 1 (mod 561), i.e. 2^560 = 561m + 1 for some m.
Note that m is odd (it must be odd because the LHS is even, but you can also see this by calculating it directly if you wish), so m = 2k+1 for some k.
Therefore 2^560 = 561(2k+1) + 1 = 1122k + 562.
Divide both sides by 2: 2^559 = 561k + 281.
Subtract 1: 2^559 - 1 = 561k + 280
So "(2^559 - 1) mod 561 = 280" (quotation marks because this is bad notation), and 280 = (559+1)/2 so your test declares 561 prime.

Similarly, Fermat primality => gophne primality in general.

Going the other way:

Your test declares 561 prime. This is because (559+1)/2 = 280 and "(2^559 - 1) mod 561 = 280", i.e. 2^559 - 1 = 561k + 280 for some k.
Add 1: 2^559 = 561k + 281.
Multiply by 2: 2^560 = 1122k + 562 = 561(2k+1) + 1
So 2^560 = 561m + 1 for some m, i.e. 2^560 ≡ 1 (mod 561), and Fermat's test declares 561 prime.

Similarly, gophne primality => Fermat primality in general, so they are in fact the same test.

To turn these examples into a proper proof, just replace 559 with n, and remember that we are carrying out the primality tests on n+2 not n.

Hi 10metreh

Now how was I expected to know/understand that! But it all make sense again, and I yet again must (for the last time, I promise) agree that the two algorithms are the same as you have explained again...(gnashing of teeth).

Just a few questions to you that I would like you to honestly answer please.

1) How many people out there would have been able to do the reduction that you have just done? I suspect very few, and very few ppl would be able to even understand what you have done right now, eccept of course math people that have studied these things assiduously.

2) How was Fermat's Little Theorem/Fermat's Primality Test "derived". I am asking out of interest, if you know.

3) Having now finally accepted that the two theorems are the same because of your explaination/reductions (and awmayer I think), would you agree that by using the algorithm in the form of the mersenne number modulo is a very interesting way to do it, since it establishes a direct relationship between mersenne numbers and ALL prime numbers -the hidden pattern of Prime numbers.....surely the holy grail everybody in prime exploration was looking for. Was the Fermat Little theorem/Primality test ever presented or investigated in this way? Can you give some references (or other contributors could as well if the have the info)?

4) Do you agree that the "mersenne number" way of expressing then the Fermat's Little theorem, base 2 could also help with factorization of mersenne numbers, something the standard form of the Fermat Primality Test does not do. This is because when you are testing the mersenne numbers modulo vs the odd numbers, the remainders of the modulo operation is cyclical, starting with 1 and terminating with (n+1)/2, when the odd number is prime or a false prime I suspect as well. When a particular odd number is a factor of a particular mersenne number, the the 0 remainder, falls at the centre of the modulo cycle that ends with (n+1)/2. This could be algorithmized into some sort of checker for mersenne number compositeness.

5) Lastly, as you have shown again so eloquently, that the "mersenne form" algorithm, is one and the same as the Fermat Primality Test, why did some expert ppl at first crack up the"algorithm" as "nonsense". Are they saying that Fermat's Primality Test is nonsense (or did they not know what you know?)

Thank you (and awmayer in the first place) for your definitive explanation.

[gophne]

Originally Posted by science_man_88

Okay so what is your sticking point? Is it that there's many ways to select that many from the set of natural numbers in that interval ?

Nope it is clear, check 10metreh's post #212

[chalsall]

Originally Posted by gophne

Nope it is clear, check 10metreh's post #212

Wow! This is almost as painful as watching Trump implode.

[gophne]

Originally Posted by chalsall

Wow! This is almost as painful as watching Trump implode.

Hi chalsall

How is it similar?...are you comparing me to President Trump/ or are you feelling pain at President Trump's implosion, or both?

Very interesting, please elucidate a little bit more.

[CRGreathouse]

I'm not 10metreh but I'll take a whack at it.

Originally Posted by gophne

1) How many people out there would have been able to do the reduction that you have just done? I suspect very few, and very few ppl would be able to even understand what you have done right now, eccept of course math people that have studied these things assiduously.

I would hope that (almost) everyone with a degree in mathematics could do it. US universities grant ~20,000 bachelor's degrees per year in mathematics and statistics, so maybe on the order of a million people in the US. Of course some people with such degrees couldn't do it, and some people without degrees could, but probably not as few as 100,000 or as many as 10 million in the US. Worldwide, maybe 10 times as many?

Originally Posted by gophne

3) Having now finally accepted that the two theorems are the same because of your explaination/reductions (and awmayer I think), would you agree that by using the algorithm in the form of the mersenne number modulo is a very interesting way to do it, since it establishes a direct relationship between mersenne numbers and ALL prime numbers -the hidden pattern of Prime numbers.....surely the holy grail everybody in prime exploration was looking for.

I would not, because you could use any base, not just base 2. Instead of getting A001567 = 341, 561, 645, 1105, ... as exceptions, you'd get A005935 = 91, 121, 286, 671, 703, 949, .... (base 3), A005936 = 4, 124, 217, 561, 781, 1541, 1729, ... etc. as exceptions. (We refer to them as pseudoprimes, actually.)

Originally Posted by gophne

4) Do you agree that the "mersenne number" way of expressing then the Fermat's Little theorem, base 2 could also help with factorization of mersenne numbers

I don't see an advantage to either form. Regardless, it's an interesting question as to whether Fermat tests (or more likely, Miller tests) could be used to factor numbers. In general I don't see an efficient way to do this, but if you can get some composite to pass many (say, 2 to 20) Fermat/Miller tests, you could probably find a factorization of the number. (It works especially well on Carmichael numbers, where I think you can get polynomial expected time factorizations.)

This is worth studying!

Originally Posted by gophne

5) Lastly, as you have shown again so eloquently, that the "mersenne form" algorithm, is one and the same as the Fermat Primality Test, why did some expert ppl at first crack up the"algorithm" as "nonsense". Are they saying that Fermat's Primality Test is nonsense (or did they not know what you know?)

Reviewing the first few pages of this thread, it seems like no one was calling your algorithm nonsense. Rather, they thought that your claims were unlikely, to wit:

Originally Posted by gophne

The algorithm is very clear.
ALL primes are covered- tested to M34 -2^1,257,787-1, Seriously!
ALL composites are identified!
Time O(log n) -Very very fast. Serious.
ALL primes are defined -NO false primes expected as per algorithm logic.
The algorith is a logical formulation, so can be verified quickly.
If authenticated, will compare to simplicity of Euclid's Proof for Infinite number of Primes.
If true, will be a new frontier in PNT

Let's score these. I think your algorithm is pretty clear. You first defined it, I think, here:

Originally Posted by gophne

2^n-1 mod (n+2)= 1/2*(2^n-1)+1

where the only wrinkle is that you hadn't yet mentioned that it was a test for n+2 rather than n. All primes are covered. You hadn't tested it up to 2^1257787 - 1, though, which you did have the courage to admit in post #36. Not all composites are identified. It doesn't run in O(log n), it's Omega(log^2 n). The algorithm can't be verified at all (let alone quickly) because it doesn't perform as advertised. I'll give you your claim on simplicity -- it's an elegant method. Your final claim is vacuously true... it didn't authenticate, so there's no requirement that it be a new frontier.

All in all, I think the skepticism was warranted. No doubt the skepticism could have been expressed more kindly though; sometimes we're not as welcoming as we'd like to be.

[Nick]

Originally Posted by gophne

2) How was Fermat's Little Theorem/Fermat's Primality Test "derived". I am asking out of interest, if you know.

See http://www.mersenneforum.org/showthread.php?t=21737
and http://www.mersenneforum.org/showthread.php?t=21756