mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > gophne

Reply
 
Thread Tools
Old 2018-01-06, 10:39   #221
10metreh
 
10metreh's Avatar
 
Nov 2008

2×33×43 Posts
Default

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

Quote:
Originally Posted by gophne View Post
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.
10metreh is offline   Reply With Quote
Old 2018-01-06, 13:14   #222
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

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
science_man_88 is offline   Reply With Quote
Old 2018-01-06, 16:43   #223
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

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
science_man_88 is offline   Reply With Quote
Old 2018-01-06, 21:50   #224
gophne
 
Feb 2017

3·5·11 Posts
Default 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
gophne is offline   Reply With Quote
Old 2018-01-06, 21:59   #225
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by gophne View Post
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
science_man_88 is offline   Reply With Quote
Old 2018-01-07, 06:13   #226
gophne
 
Feb 2017

3×5×11 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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
gophne is offline   Reply With Quote
Old 2018-01-07, 06:44   #227
axn
 
axn's Avatar
 
Jun 2003

12B616 Posts
Default

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.
axn is offline   Reply With Quote
Old 2018-01-07, 07:28   #228
gophne
 
Feb 2017

3·5·11 Posts
Default

Quote:
Originally Posted by axn View Post
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.
gophne is offline   Reply With Quote
Old 2018-01-07, 09:24   #229
10metreh
 
10metreh's Avatar
 
Nov 2008

2·33·43 Posts
Default

Quote:
Originally Posted by gophne View Post
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 View Post
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
10metreh is offline   Reply With Quote
Old 2018-01-07, 11:10   #230
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

37·281 Posts
Default Uncompromisingly monosyllabic

Quote:
Originally Posted by gophne View Post
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
xilman is online now   Reply With Quote
Old 2018-01-07, 11:30   #231
M344587487
 
M344587487's Avatar
 
"Composite as Heck"
Oct 2017

10101111012 Posts
Default

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
M344587487 is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
gpuOwL: an OpenCL program for Mersenne primality testing preda GpuOwl 2610 2020-12-04 14:53
GQQ: a "deterministic" "primality" test in O(ln n)^2 Chair Zhuang Miscellaneous Math 21 2018-03-26 22:33
Aouessare-El Haddouchi-Essaaidi "test": "if Mp has no factor, it is prime!" wildrabbitt Miscellaneous Math 11 2015-03-06 08:17
"New primality proving test from Alex Petrov" ewmayer Math 11 2007-04-23 19:07
P-1 B1/B2 selection with "Test=" vs "Pfactor=" James Heinrich Software 2 2005-03-19 21:58

All times are UTC. The time now is 12:07.

Sat Dec 5 12:07:14 UTC 2020 up 2 days, 8:18, 0 users, load averages: 1.76, 1.79, 1.89

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.