"New" primality test/check

[10metreh]

CRGreathouse has answered most of the questions so there isn't much more for me to say.

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.

According to the Prime Pages, Fermat noticed that 2p divides 2^p-2 for p prime while studying perfect numbers, which are of course closely related to Mersenne primes. I don't think we have any record of how he proved his theorem. Nick has given links to proofs if you want to see those.

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.

Neither form really has an advantage over the other in base 2, because the two forms are equivalent: you can get very quickly from one to the other as I showed in my last post. However, it is harder to generalise your form to bases other than 2. The reason your form works is that (n+1)/2 is an integer for any n that is not a multiple of 2. But if we change 2 to 3, this is no longer true.

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.

As far as I can tell, you're just saying that if you calculate 2^n-1 mod every odd number in turn, and you find that 2^n-1 ≡ 0 mod m for some odd number m, then m is a factor of 2^n-1. This is a very slow way of factoring Mersenne numbers - it's just trial division, and it's not even efficient trial division.

[science_man_88]

My thought was work backwards as though the 2 in n+2 was n+1 and solve the congruence to be 0.

[science_man_88]

Equivalents generalize to:

2^(n-1)==1 mod n
Subtract 2^y or some natural y≤n
2^(n-1)-2^y == n-(2^y-1) mod n
Divide by 2^y
2^(n-y-1)-1 == (n-(2^y-1))/(2^y) mod n
Replace n by n+2^y
2^(n+2^y-y-1)-1== (n+1)/(2^y) mod (n+2^y)

Unless I messed up a step.edit: or the statement for Fermat's theorem like I did originally. Edit 2: I think you may find it can be changed still to a modular arithmetic statement about double mersennes with 2 more steps though.

[gophne]

Hi Everybody

Time for playing with another possible new/unusual ? Primality Algorithm on the

mersenneforum.org>Extra Stuff>Blogorrhea>gophne>"New"primality test/check Forum.

Not sure if anybody would be interested, but at risk of missing out on a possible "new" primality test/algorithm, which is the equivalent to missing out on M50

The Algorithm is as follows;

For the series of odd numbers, where the 1st term of the series is 1, to the n-th term VALUE, increment 2, step 1,

where n is an element of the set of integers =>1, and the n-th term results in the series having an odd number of terms,


In sigma notation the series would look something like this:


n-th (VALUE)

Z (2n-1) Z representing Sigma in lieu of

n=1


Then for any of the terms of the series so constituted, starting at the 2nd term to the term whose value would be equal to the value of the n-th value -2.
If any of the terms in the test range is a multiple of, or shares a common factor with, the n-th value, then the n-th value is Composite, else Prime.


To do an example just so to clarify the wording (I am not familiar with Latex on this Site yet);

Let the nth-value be equal to 7, then the algorithm series, applying Sigma, would be;

01,03,05,07

The test "range" according to the algorithm would be;

03,05......................................................Constituting the "seed" terms in the test range.

03 + 14 =17
05 + 14 =19

Since both these derived values are not multiples, or do not share a common factor with any of the "seed" terms, the n-th value , namely "7" is Prime, as per the algorithm.

Let us try n-th value is equal to 2047

The test range would be;

03,05,07,09,11,13,15.......2045.........Test range/Seed terms

For this test range the derived algorithm values would be seed terms + 4094

The Seed/Algorithm pairs formed would be;

(3,34097) (5,4099),(7,5001),(9,5003), (11, 5005), (13,5007)......

But the 5th term of these pairings share a common factor "11", so according to the algorithm the n-th value is Composite.

Could anybody confirm or refute that this primality algorithm is true for all Composites/Primes.

Would the above constitute a legitimate primality algorithm?

[I]Caveat: Not sure if anybody else worked on or published any similar primality algorithms, but I could not find anything similar looking it up in Wikipedia.

[science_man_88]

Originally Posted by gophne

Hi Everybody

Time for playing with another possible new/unusual ? Primality Algorithm on the

mersenneforum.org>Extra Stuff>Blogorrhea>gophne>"New"primality test/check Forum.

Not sure if anybody would be interested, but at risk of missing out on a possible "new" primality test/algorithm, which is the equivalent to missing out on M50

The Algorithm is as follows;

For the series of odd numbers, where the 1st term of the series is 1, to the n-th term VALUE, increment 2, step 1,

where n is an element of the set of integers =>1, and the n-th term results in the series having an odd number of terms,


In sigma notation the series would look something like this:


n-th (VALUE)

Z (2n-1) Z representing Sigma in lieu of

n=1


Then for any of the terms of the series so constituted, starting at the 2nd term to the term whose value would be equal to the value of the n-th value -2.
If any of the terms in the test range is a multiple of, or shares a common factor with, the n-th value, then the n-th value is Composite, else Prime.


To do an example just so to clarify the wording (I am not familiar with Latex on this Site yet);

Let the nth-value be equal to 7, then the algorithm series, applying Sigma, would be;

01,03,05,07

The test "range" according to the algorithm would be;

03,05......................................................Constituting the "seed" terms in the test range.

03 + 14 =17
05 + 14 =19

Since both these derived values are not multiples, or do not share a common factor with any of the "seed" terms, the n-th value , namely "7" is Prime, as per the algorithm.

Let us try n-th value is equal to 2047

The test range would be;

03,05,07,09,11,13,15.......2045.........Test range/Seed terms

For this test range the derived algorithm values would be seed terms + 4094

The Seed/Algorithm pairs formed would be;

(3,34097) (5,4099),(7,5001),(9,5003), (11, 5005), (13,5007)......

But the 5th term of these pairings share a common factor "11", so according to the algorithm the n-th value is Composite.

Could anybody confirm or refute that this primality algorithm is true for all Composites/Primes.

Would the above constitute a legitimate primality algorithm?

[I]Caveat: Not sure if anybody else worked on or published any similar primality algorithms, but I could not find anything similar looking it up in Wikipedia.

Offuscated trial division.

[gophne]

Originally Posted by science_man_88

Offuscated trial division.

Hi science_man_88

I love you, but your monosyllabic answers does not help. Please explain some more or even better, do the "offuscated trial division" for the two examples given. Thanx.

[axn]

So your algorithm:

Take odd N (which we're checking if it is prime or composite)

For all odd n = 1,3,... < N, check if gcd(n, n+2*N) > 1. if so, you found a factor of N, and it is composite, otherwise it is prime.


Trial division algortihm:

Take odd N (which we're checking if it is prime or composite)

For all odd prime n = 3,5,7,.. < sqrt(N), check if n divides N. if so, you found a factor of N, and it is composite, otherwise it is prime.


As you can see, you're just doing a much slower version of trial division.

What? The gcd(n, n+2*N) is nothing like checking if "n divides N"? Please... Stop kidding yourselves.

[gophne]

Originally Posted by axn

So your algorithm:

Take odd N (which we're checking if it is prime or composite)

For all odd n = 1,3,... < N, check if gcd(n, n+2*N) > 1. if so, you found a factor of N, and it is composite, otherwise it is prime.


Trial division algortihm:

Take odd N (which we're checking if it is prime or composite)

For all odd prime n = 3,5,7,.. < sqrt(N), check if n divides N. if so, you found a factor of N, and it is composite, otherwise it is prime.


As you can see, you're just doing a much slower version of trial division.

What? The gcd(n, n+2*N) is nothing like checking if "n divides N"? Please... Stop kidding yourselves.

Hmmmmm

Not exactly I think. Trial division divided the TEST number by the set of odd numbers up to the sqaure root of that number, until a possible divisor (that leaves a residue of 0 is found). If no such divisors are found, the number is Prime.

The algorithm states that if any of the odd numbers + 2 times the nth Value in the test range has a common factor, independant of the number being tested. I know it would be cumbersome for very large numbers (so is trial division), but I am trying to establish a "Primality" Test relationship here. There are many Primality Tests out there that are very cumbersome or even incalculable after a few steps, but are still recognised as Primality Tests never-the-less.

Thanks for distilling "my" algorithm into a more clear form for readers to evaluate the "primality test" aspect of it. Much better than my attempt, so if readers could please use axn's form of it.

[10metreh]

Originally Posted by gophne

Hmmmmm

Not exactly I think. Trial division divided the TEST number by the set of odd numbers up to the sqaure root of that number, until a possible divisor (that leaves a residue of 0 is found). If no such divisors are found, the number is Prime.

The algorithm states that if any of the odd numbers + 2 times the nth Value in the test range has a common factor, independant of the number being tested. I know it would be cumbersome for very large numbers (so is trial division), but I am trying to establish a "Primality" Test relationship here. There are many Primality Tests out there that are very cumbersome or even incalculable after a few steps, but are still recognised as Primality Tests never-the-less.

Thanks for distilling "my" algorithm into a more clear form for readers to evaluate the "primality test" aspect of it. Much better than my attempt, so if readers could please use axn's form of it.

I don't think you've taken on board what axn meant by this:

Originally Posted by axn

What? The gcd(n, n+2*N) is nothing like checking if "n divides N"? Please... Stop kidding yourselves.

The point is that, if n is odd, then gcd(n, n+2N) = gcd(n, N) and so you are just checking if n has any common factors with N. But if N is not prime, then the smallest n that has a common factor with N is the smallest prime factor of N, so in fact when you first find n such that gcd(n, n+2N) > 1, that n is a factor of N. So you're just doing inefficient trial division.

I guess that technically counts as a "primality test" in that it does correctly determine primality or otherwise of N.
But it's easy to come up with useless primality tests. Here's one: if N>4, then N is prime if and only if N does not divide (N-1)!. Unlike trial division, it's got only one step, so what could possibly go wrong...?

As for why gcd(n, n+2N) = gcd(n, N), it's time for another basic number theory lesson:
Suppose d divides n and n+2N.
Then d must divide their difference, which is 2N.
But d divides n, which is odd, so d is odd, and thus d must divide N.
Conversely, suppose d divides n and N.
Then clearly d divides n+N+N = n+2N.
So the sets of common factors of (n, n+2N) and (n, N) are exactly the same, and in particular gcd(n, n+2N) = gcd(n, N).

[xilman]

Originally Posted by gophne

Hi science_man_88

I love you, but your monosyllabic answers does not help. Please explain some more or even better, do the "offuscated trial division" for the two examples given. Thanx.

That phrase in quotes is not as you say, nor is it spelled right.

I think "You hide a test which splits by small primes, one by one" may be good.

Paul.

[M344587487]

Petition to call the simplified form of this test the Gophne-Axn Little Lemma.