theory on Mersenne primes ?

[LaurV]

Originally Posted by science_man_88

forprime(n=2,200,if(n%4==3 && isprime(2*n+1),next(),if(sigma(2^n)-sigma(2^n-1)==2^n-1,print1(n","))))

this is what I have so far.

ok, it is about the same story, the improvement is that you skip SG primes (why I did not think to it??) but on the other hand you compute 2^n three times and by a slower method (pari uses exponentiation for that). If you use 1<<n-1 is much faster, and if you will put it to a variable first time, then you compute it only once and can use the variable second time.

But as we said, there is no point in doing it, as pari need to factor the integer to get its sigma.

edit: by the way, I found an ugly bug in pari/gp for modular square root, it directly tries to factor the integer, without checking if it is a perfect square, so for example if you try "sqrt(Mod(9,x))" you will get an error if 3 is not a quadratic residue. Very ugly! Where could I report it?

[Gammatester]

Originally Posted by LaurV

edit: by the way, I found an ugly bug in pari/gp for modular square root, it directly tries to factor the integer, without checking if it is a perfect square, so for example if you try "sqrt(Mod(9,x))" you will get an error if 3 is not a quadratic residue. Very ugly! Where could I report it?

What version of pari/gp? Can you give an example? Versions 2.3.4 and 2.4.2 give the correct root Mod(3,x) for sqrt(Mod(9,x)) for quick tests with x=17,19,101 even though 3 is not a quadratic residue x.

Edit: Or do you mean the error messages for e.q. sqrt(Mod(9,35)) and sqrt(Mod(3,35))?

[LaurV]

Originally Posted by Gammatester

What version of pari/gp? Can you give an example? Versions 2.3.4 and 2.4.2 give the correct root Mod(3,x) for sqrt(Mod(9,x)) for quick tests with x=17,19,101 even though 3 is not a quadratic residue x.

Edit: Or do you mean the error messages for e.q. sqrt(Mod(9,35)) and sqrt(Mod(3,35))?

Yes, the last one. He should check first if the number is perfect square. Theoretically, sqrt(Mod(3,35)) does not exists, as 3 is not a QR mod 5 or mod 7. And that is why you can not extract sqrt of Mod(3*x,35), no matter what x it is, unless 3*x is a perfect square, and in such case you can extract the square root in "normal" (integer) way. So, "sqrt(Mod(9,35))" as per your example, it does very exists! and it is equal to 3, or to 32 (that is -3 mod 35). The "not quadratic residue in gsqrt" is an ugly error in this case (as same as the one for 4).

(15:31:51) gp > sqrt(Mod(3,11))
%1 = Mod(5, 11)  ----correct, a quadratic residue mod a prime
(15:32:10) gp > sqrt(Mod(7,11))
  ***   at top-level: sqrt(Mod(7,11))     ----correct, not a quadratic residue mod a prime
  ***                 ^---------------
  *** sqrt: non quadratic residue in gsqrt
  ***   Break loop: type 'break' to go back to GP
break>
(15:32:17) gp > sqrt(Mod(9,11))
%2 = Mod(3, 11)                    ----correct, a quadratic residue
(15:32:21) gp > sqrt(Mod(9,35))
  ***   at top-level: sqrt(Mod(9,35))  ----WRONG, he detects that 3 is not a quadratic residue, but he does not need to do that, 9 IT IS a quadratic residue mod both 5 and 7, as it is a perfect square
  ***                 ^---------------
  *** sqrt: non quadratic residue in gsqrt
  ***   Break loop: type 'break' to go back to GP
break>
(15:32:30) gp > sqrt(Mod(4,35)) ----same as above
  ***   at top-level: sqrt(Mod(4,35))
  ***                 ^---------------
  *** sqrt: non quadratic residue in gsqrt
  ***   Break loop: type 'break' to go back to GP
break>
(15:32:46) gp > Mod(3,35)^2    ----proof
%3 = Mod(9, 35)
(15:34:05) gp > Mod(32,35)^2  ----proof
%4 = Mod(9, 35)
(15:34:09) gp >

[Gammatester]

I see. But I wonder what to do with e.g. sqrt(Mod(29,35))? Is there a systematic approach to get the solutions 8,13,22,27 mod 35?

[LaurV]

I don't know any, without factoring the composite number. End even that, to take square roots modulo a prime, I think there are known algorithms only when the prime is 3 mod 4 (not sure about it, but I don't know any method to take a square root modulo a prime p of the form p=4k+1).

Someone else could put some light into this (missing RDS! :D)

edit: well I was not exactly correct in my assumption about taking the modular square root, it seems that the only strange case is when p=8k+1, as for n=8k+5 there is some formula coming from Legendre (wiki link).

[Gammatester]

There is no problem to compute sqrt(x) mod p*q or sqrt(x) mod p^k with p,q prime if x is a quadratic residue mod p and mod q.

IMHO the hard case is if the Jacobi symbol (x | p*q) is 1, e.q. (3 | 35) = 1, but 3 is a not a quadratic residue mod 35.

[LaurV]

Originally Posted by Gammatester

There is no problem to compute sqrt(x) mod p*q or sqrt(x) mod p^k with p,q prime if x is a quadratic residue mod p and mod q.

IMHO the hard case is if the Jacobi symbol (x | p*q) is 1, e.q. (3 | 35) = 1, but 3 is a not a quadratic residue mod 35.

Does "no problem" means "without factoring n=p*q into p and q"? I think you can not. Excluding taking all residues from 2 to n and try them. That is brute force.

Try computing sqrt(2) mod M1061, where M1061 is the mersenne number. For sure 2 is a quadratic residue, because for any odd power of 2, you have 2^(k+1)=2 mod 2^k-1, so 2^((k+1)/2) is a square root of 2, therefore 2 is always a quadratic residue.

Example: 2^6=2 mod 31, so 2^3=8 is a square root of 2. Proof: 8^2=2 mod 31. So, the square roots of 2 mod 31 are 8 and -8, that is 31-8=23. Proof: 23^2=2 mod 31. There are no other, as 31 is prime.

For 127, square roots of 2 are 16 and -16 mod 127.

But 2047 is not prime, so it has (at least) 4 square roots of two. Two of them are 64 and -64. Find the other two. No brute force allowed. Just calculus, formula, or efficient algorithm.

Then apply the same calculus to find the other (at least) two square roots of 2 mod M1061 (obviously two of them are 2^531 and its negative).

Congratulations, you just factored M1061.

This related to your first part of the posting. The second part is false. If the number is not a quadratic residue, the square root does not exist. You have nothing to compute.

[science_man_88]

for(k=1,7,if((((1)*k+1)*k+1)==7,print(k)))

1 represents 2^1
k is a power in the algorithm on the math page of mersenne.org

solving

for(k=1,127,if((((1)*k+1)*k+1)==127,print(k)))

but possibly with different k in each place and different powers could let us test 2^(2^7-1)-1 just by knowing the binary representation of 7 is 111. it test 2^2^7 but 2^(2^7-1) is half that and -1 so (2^2^7 mod y== ((0= (2^(2^7-1)-1) mod y +1)*2) so for 0 to work the answer for 2^2^7 must be 2

[fivemack]

There are perfectly good algorithms for square root mod a prime p=4k+1, the only problem is that they work in a quadratic extension field, so you need to find a quadratic non-residue. In practice you start at 2 and have found the quadratic non-residue in on-average-two quadratic-residuosity computations, but nobody is able to prove that there is not a number whose smallest quadratic non-residue is enormous.

[science_man_88]

((6*4+6)*4+7) is the way to get to 127(2^7-1) in 3 steps ( bits in binary(7))

so that get to solve for 2^127-1 using binary(7) instead of binary(127) now to get a general form so I can use binary(127) or binary (7) to search for factors of MM127.

[LaurV]

Originally Posted by fivemack

There are perfectly good algorithms for square root mod a prime p=4k+1, the only problem is that they work in a quadratic extension field, so you need to find a quadratic non-residue. In practice you start at 2 and have found the quadratic non-residue in on-average-two quadratic-residuosity computations, but nobody is able to prove that there is not a number whose smallest quadratic non-residue is enormous.

I know that, and this was the cause for my first error, when I said that we can not compute the square root mod a 4k+1 prime. The point is that given a prime p, half of the values mod p are QR, because each x and -x when squared, will give the same result. Now, the product of two QR is a QR, and the product of two QNR is QNR, but on the other hand, if p=4k+3, then -1 is NOT a QR. This means that for a prime of the form 4k+3, either x or -x is a QR. So, you try both 2 and -2 and you have at least one QNR to start your "perfectly good" algorithm with it.

But if p is 4k+1, then -1 is a quadratic residue always, so you always have either both x and -x are QR, or both are QNR. So, theoretically, as you said, given a very big prime of the form 4k+1, it could be that all QNR are "concentrated" somewhere around p/2, or half of them are around p/3 and the other half at 2p/3, etc, and you need a lot of trials to reach them.

ex: p=11=4k+3; QR: 1,4,9,5,3; QNR: 10,7,2,6,8 (that is -1, -4, -9, -5, -3).
p=13=4k+1; QR: 1,4,9,3,12,10 (that is, regardless of the order, 1,3,4,-1,-3,-4). QNR: the other 6 of them, i.e. 2,5,6,7,8,11, or in negative notation, 2,5,6,-6,-5,-2.