20111118, 05:35  #276  
Romulan Interpreter
Jun 2011
Thailand
21673_{8} Posts 
Quote:
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? Last fiddled with by LaurV on 20111118 at 05:41 

20111118, 08:02  #277  
Mar 2009
2·19 Posts 
Quote:
Edit: Or do you mean the error messages for e.q. sqrt(Mod(9,35)) and sqrt(Mod(3,35))? Last fiddled with by Gammatester on 20111118 at 08:10 

20111118, 08:31  #278  
Romulan Interpreter
Jun 2011
Thailand
21673_{8} Posts 
Quote:
Code:
(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 toplevel: 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 toplevel: 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 toplevel: 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 > Last fiddled with by LaurV on 20111118 at 08:44 

20111118, 09:06  #279 
Mar 2009
2·19 Posts 
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?
Last fiddled with by Gammatester on 20111118 at 09:06 
20111118, 09:27  #280 
Romulan Interpreter
Jun 2011
Thailand
21673_{8} Posts 
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). Last fiddled with by LaurV on 20111118 at 09:40 
20111118, 10:42  #281 
Mar 2009
2·19 Posts 
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. 
20111118, 15:04  #282  
Romulan Interpreter
Jun 2011
Thailand
3×3,049 Posts 
Quote:
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^k1, 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 318=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. Last fiddled with by LaurV on 20111118 at 15:55 

20111118, 15:39  #283 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Code:
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 Code:
for(k=1,127,if((((1)*k+1)*k+1)==127,print(k))) 
20111118, 16:00  #284 
(loop (#_fork))
Feb 2006
Cambridge, England
7·911 Posts 
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 nonresidue. In practice you start at 2 and have found the quadratic nonresidue in onaveragetwo quadraticresiduosity computations, but nobody is able to prove that there is not a number whose smallest quadratic nonresidue is enormous.

20111118, 16:16  #285 
"Forget I exist"
Jul 2009
Dumbassville
10000011000000_{2} Posts 
((6*4+6)*4+7) is the way to get to 127(2^71) in 3 steps ( bits in binary(7))
so that get to solve for 2^1271 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. Last fiddled with by science_man_88 on 20111118 at 16:18 
20111118, 16:17  #286  
Romulan Interpreter
Jun 2011
Thailand
3·3,049 Posts 
Quote:
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. Last fiddled with by LaurV on 20111118 at 16:21 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Mersenne Primes p which are in a set of twin primes is finite?  carpetpool  Miscellaneous Math  3  20170810 13:47 
Distribution of Mersenne primes before and after couples of primes found  emily  Math  34  20170716 18:44 
Mersenne primes and class field theory  Nick  Math  4  20170401 16:26 
Basic Number Theory 11: Gaussian primes  Nick  Number Theory Discussion Group  0  20161203 11:42 
Mersenne Wiki: Improving the mersenne primes web site by FOSS methods  optim  PrimeNet  13  20040709 13:51 