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

2018-01-06, 10:39   #221
10metreh

Nov 2008

2×33×43 Posts

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

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

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

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

 2018-01-06, 13:14 #222 science_man_88     "Forget I exist" Jul 2009 Dartmouth NS 100000111000102 Posts My thought was work backwards as though the 2 in n+2 was n+1 and solve the congruence to be 0. Last fiddled with by science_man_88 on 2018-01-06 at 13:36
 2018-01-06, 16:43 #223 science_man_88     "Forget I exist" Jul 2009 Dartmouth NS 2×3×23×61 Posts 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. Last fiddled with by science_man_88 on 2018-01-06 at 17:12 Reason: Fixed statement of theorem
 2018-01-06, 21:50 #224 gophne   Feb 2017 3×5×11 Posts N-th Value Primality Algorithm 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. Last fiddled with by gophne on 2018-01-06 at 21:55 Reason: Formating spaces
2018-01-06, 21:59   #225
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts

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

Last fiddled with by science_man_88 on 2018-01-06 at 22:09

2018-01-07, 06:13   #226
gophne

Feb 2017

3×5×11 Posts

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

Last fiddled with by gophne on 2018-01-07 at 06:14 Reason: typo's

 2018-01-07, 06:44 #227 axn     Jun 2003 153C16 Posts 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.
2018-01-07, 07:28   #228
gophne

Feb 2017

3×5×11 Posts

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

2018-01-07, 09:24   #229
10metreh

Nov 2008

91216 Posts

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

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

Last fiddled with by 10metreh on 2018-01-07 at 09:25

2018-01-07, 11:10   #230
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

2·5,827 Posts
Uncompromisingly monosyllabic

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

Last fiddled with by xilman on 2018-01-07 at 11:11

 2018-01-07, 11:30 #231 M344587487     "Composite as Heck" Oct 2017 3A516 Posts Petition to call the simplified form of this test the Gophne-Axn Little Lemma. Last fiddled with by M344587487 on 2018-01-07 at 11:31 Reason: word

 Similar Threads Thread Thread Starter Forum Replies Last Post preda GpuOwl 2908 2023-01-30 01:25 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 09:30.

Tue Jan 31 09:30:42 UTC 2023 up 166 days, 6:59, 0 users, load averages: 1.22, 1.19, 1.18