mathematical explication for mersenne primes
 

A peaceful day for all,

Should not the computional and mathematical part of the
prime generator f(n)=2n^2-1 concerning Mersenne primes
be added in the Mersenne Wicki ?

There was a discussion under
[url]http://www.mersenneforum.org/showthread.php?t=20564[/url]

and a nice webpage from my part under
[url]http://devalco.de/quadr_Sieb_2x%5E2-1.php[/url]

I think the describtion is mathematical correct,
even if the thread was put in the miscelenous Math corner and
last but not least it is indeed an correct explication how mersenne primes are distributed.

Would be nice to get a little bit feedback. :redface::rolleyes::pals:

Greetings from the primes
Bernhard

I thought you got quite a bit of feedback in that thread? Also, getting moved to Misc Math is pretty strong feedback.

[QUOTE=VBCurtis;467415]I thought you got quite a bit of feedback in that thread? Also, getting moved to Misc Math is pretty strong feedback.[/QUOTE]

if we wanted even stronger feedback we could move them to their own blog area (like my blog area, aka trash bin to some extent). I'm still wondering why using this polynomial is quicker than known methods of TF ( I'll admit most of my stuff is also rather jumbled).

[QUOTE=science_man_88;467471]I'm still wondering why using this polynomial is quicker than known methods of TF ( I'll admit most of my stuff is also rather jumbled).[/QUOTE]Your question would be more apt without the "why."

I checked for p < 200, and trial factorization was faster in [i]every case[/i] where 2^p - 1 was composite, in the sense that the smallest k for which q = 2*k*p + 1 is a factor was smaller than the least l for which gcd(2*l^2 - 1, 2^p - 1) > 1.

As I indicated before, this shouldn't be at all surprising. For a given factor q of 2^p - 1, we have q = 2*k*p + 1, and so

(*) k < q/(2*p)

OTOH, if 2*l^2 - 1 == 0 (mod q), the best we can expect in general is

(**) l < q/2

Of course, when q = 2^p - 1 is prime, we have

l = 2^((p-1)/2) and k = (2^(p-1) - 1)/p

so in this case l is smaller, for p > 5. However, when 2^p - 1 is actually prime, LL may be a slightly faster way to prove primality.

A peaceful day for all members,

[QUOTE=VBCurtis;467415] Also, getting moved to Misc Math is pretty strong feedback.[/QUOTE]

You did not contribute one message in the discussion about the prime generator concerning the polynomial f(n)=2n^2-1 for n element N.

I suppose you did not understand the beauty of the described algorithm.

I have described the algorithm in three different explications:
1. mathematical description and explication
2. a programming version in Mupad, which should be easy to understand and
3. a more language descriptivel part.

It is asthonishing for me that you put immediatly this algorithm in the misc Math corner and that you think, that is the right place.

The algorithm under [url]http://devalco.de/quadr_Sieb_2x%5E2-1.php[/url]
gives an explication how Mersenne primes are distributed:
Mersenne numbers are sieved out by the algorithm,
so that the factors f | f(n)=2n^2-1 appear if you increase n.

This is a clear mathematical explication,
perhaps not the fastest for proving Mersenne primes,
but a mathematical correct and proved version.

Therefore i think it is right to put the algorithm to the Mersenne Wiki.

Greetings from the primes :rolleyes::loco::whistle:
Berhard

Did you confuse Mersenne Wiki with a mathematical journal?
Just publish your explications in a mathematical journal.

Let p > 2 be prime, q a prime factor of N = 2^p - 1, k = (q - 1)/(2*p), and 2*l^2 - 1 == 0 (mod q), 0 < l < p/2. Up to the limit 250, we find that k < l for most p. Also up to this limit, the only exceptions occur when q is the [i]largest[/i] prime factor of N.

I note that in this situation, l = lift(Mod(2,q)^((p-1)/2)) is a solution to 2*l^2 - 1 == 0 (mod q). If this l is greater than q/2, take q - l instead.

One could easily compare k's and l's for the known factors of 2^p - 1 for larger values of p. The only reason I stopped at 250 was, I used Pari's factor() to do the factorizations. I have so far been too lazy to figure out how to read in lines from the factor table of 2^n - 1 I downloaded.

I also note that, if n is any odd number, the prime factors of the "primitive part" of 2^n - 1 (polcyclo(n) evaluated at x = 2, with any "intrinsic prime factors" divided out) will always be congruent to 1 (mod 2*n). Thus, q = 2*n*k + 1, just as when the exponent is prime, and

k < q/(2*n).

Also, just as when the exponent is prime, the congruence

2*x^2 - 1 == 0 (mod q) is solvable; x = \pm (Mod(2,q)^((n-1)/2). One of these will have a lift l, 0 < l < q/2.

Again, the best we can guarantee is l < q/2 (as opposed to k < q/(2*n)).

This does raise a non-trivial question: If q ranges over primes congruent to 1 or 7 (mod 8), how are the square roots of 1/2 (mod p) distributed? Obviously, the smallest possible solution is around sqrt(q/2). I'm guessing such small solutions don't happen very often. In particular, primes of the form 2*x^2 - 1 are likely fairly thin on the ground.

This being the case, it seems very unlikely that for odd n, using 2*x^2 - 1 will produce a factor of (the primitive part of) 2^n - 1 before trial factorization, looking for primes q = 2*k*n + 1.

[QUOTE=Dr Sardonicus;467553] I have so far been too lazy to figure out how to read in lines from the factor table of 2^n - 1 I downloaded.[/QUOTE]

readvec may help.

[QUOTE=science_man_88;467578]readvec may help.[/QUOTE]
No, it's just a matter of reading in a line, and then parsing the (completely straightforward) format. There's the exponent, followed by a tab character, followed by factors, which when printed out in decimal are separated by periods. However, in some entries, the last factor is not printed out in decimal, but represented as Pxxx or Cxxx (meaning a prime or composite number of xxx decimal digits). Factors so designated are preceded by a tab character.

Perfectly straightforward, but writing code to parse text is (to put it mildly) not my forte. When I feel motivated enough, I'll bear down and get 'er done.

[QUOTE=Dr Sardonicus;467553]
One could easily compare k's and l's for the known factors of 2^p - 1 for larger values of p. The only reason I stopped at 250 was, I used Pari's factor() to do the factorizations. I have so far been too lazy to figure out how to read in lines from the factor table of 2^n - 1 I downloaded.[/QUOTE]

[QUOTE=Dr Sardonicus;467601]No, it's just a matter of reading in a line, and then parsing the (completely straightforward) format. There's the exponent, followed by a tab character, followed by factors, which when printed out in decimal are separated by periods. However, in some entries, the last factor is not printed out in decimal, but represented as Pxxx or Cxxx (meaning a prime or composite number of xxx decimal digits). Factors so designated are preceded by a tab character.

Perfectly straightforward, but writing code to parse text is (to put it mildly) not my forte. When I feel motivated enough, I'll bear down and get 'er done.[/QUOTE]

Perhaps I'm misunderstanding what you're trying to do, but if you only care about factors of 2^p - 1 and not 2^n - 1, then you can go to [url]https://www.mersenne.org/report_factors/[/url] and define your desired "Exponent range" and then check the "Print simple text report" box and uncheck the "Display date found" box, and then click on "Get factors", you will get a simple one-factor-per line output in a text box, in the form:

p1,f1
p1,f2
p1,f3
p2,f1
p3,f1
p3,f2
...

where p1 in the example has 4 known factors (the largest cofactor, often extremely large, is always omitted from this listing), p2 has 2 factors (with the same caveat), etc.

So this format should be very easy to parse.

The easiest way to do the cut and paste of the entire possibly very long text box contents, if you're using Windows, would be to click in the text box and then enter Ctrl-A followed by Ctrl-C.

Of course, there is a selection bias here, because the known factors of 2^p - 1 for any sizable p beyond Cunningham project range will be the very smallest ones, except for the 316 prime exponents known to be fully factored or probably-fully factored.

[QUOTE=GP2;467616][...] you will get a simple one-factor-per line output in a text box, in the form:

p1,f1
p1,f2
p1,f3
p2,f1
p3,f1
p3,f2
...

where p1 in the example has 4 known factors (the largest cofactor, often extremely large, is always omitted from this listing), p2 has 2 factors (with the same caveat), etc.

So this format should be very easy to parse.
[...]
Of course, there is a selection bias here, because the known factors of 2^p - 1 for any sizable p beyond Cunningham project range will be the very smallest ones, except for the 316 prime exponents known to be fully factored or probably-fully factored.[/QUOTE]
Thanks very much for the prime-exponent resource. Yes, that looks easy enough that even *I* can parse it
;-)

The fact that only the smallest factors are known for larger exponents is fine with me. The only basis for comparison I can see at the moment, is between using values of 2*x^2 - 1 and trial division.

And for this purpose, the comparison seems to be between the size of the integer x with


(*) q divides 2*x^2 - 1, 0 < x < q/2, and

(**) k = (q - 1)/(2*n).

My instincts tell me that x is unlikely to be a really small fraction of q/2 (though of course it does happen occasionally), as k is guaranteed to be by (**). If my instincts are correct, then trial division is likely to be a much faster way to find small factors.

Another way to investigate this is to look at (*) for q congruent to 7 (mod 8) (the multiplicative order of 2 (mod q) is always odd for such q), and for q congruent to 1 (mod 8), perhaps checking whether the multiplicative order (mod 2) is odd. For q congruent to 1 (mod 8), the order of 2 (mod q) will even, unless 2 is [i]at least[/i] an eighth power residue (mod q). So q congruent to 1 (mod 8) for which znorder(Mod(2,q)) is odd, will not be terribly common.

Exploiting the fact that

2*l^2 - 1 == 0 (mod p)

is easy to solve when p == 7 (mod 8) [one solution is Mod(2,p)^((p-3)/4)], that the multiplicative order of 2 (mod p) is automatically odd in this case, and that I had primelimit set above 64000000, I did a quick check on the distribution of the least value of l in comparison to p/2.

The script

? j=0;v=vector(100);forprime(p=7,64000000,r=p%8;if(r==7,j++;l=lift(Mod(2,p)^((p-3)/4));if(l+l>p,l=p-l);f=2.*l/p;m=floor(100*f);v[m+1]=v[m+1]+1));print(j)

found j = 946648 primes p == 7 (mod 8). For each, l is the value < p/2 for which p divides 2*l^2 - 1. In the vector v, v[i] is the number of p for which

(i-1)/100 < 2*l/p < i/100.

[9471, 9426, 9368, 9426, 9499, 9452, 9339, 9539, 9562, 9419, 9612, 9498, 9416, 9576, 9495, 9442, 9453, 9403, 9401, 9484, 9339, 9348, 9367, 9511, 9509, 9424, 9520, 9547, 9605, 9594, 9419, 9627, 9463, 9482, 9474, 9440, 9323, 9530, 9543, 9454, 9497, 9552, 9397, 9306, 9427, 9406, 9558, 9463, 9466, 9520, 9345, 9435, 9338, 9454, 9389, 9396, 9442, 9495, 9461, 9500, 9539, 9593, 9549, 9567, 9399, 9375, 9454, 9600, 9425, 9473, 9463, 9472, 9425, 9430, 9456, 9406, 9601, 9587, 9442, 9628, 9382, 9543, 9487, 9328, 9603, 9524, 9436, 9547, 9475, 9441, 9461, 9456, 9448, 9414, 9443, 9410, 9403, 9501, 9379, 9436]

I'm no expert at statistics, but the distribution looks reasonably close to uniform.

I cheerfully admit that I didn't look at primes congruent to 1 (mod 8). I didn't see any faster way to solve the congruence than using factormod(). Also, I didn't want to bother checking whether the multiplicative order of 2 (mod p) was odd. But I have no reason to expect anything other than uniform distribution in this case either.

If q is a divisor of (the primitive part of) 2^n - 1, n odd, then q = 2*n*k + 1, so k < q/(2*n). Assuming uniform distribution of l-values in (0,q/2) one could say that there's a 1 in n chance that

f(x) = 2*x^2 - 1

will find the factor q before trial factorization. As n increases, the chances decrease, with no positive lower bound.