 mersenneforum.org theory on Mersenne primes ?
 Register FAQ Search Today's Posts Mark Forums Read  2011-11-18, 05:35   #276
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

986910 Posts Quote:
 Originally Posted by science_man_88 Code: 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?

Last fiddled with by LaurV on 2011-11-18 at 05:41  2011-11-18, 08:02   #277
Gammatester

Mar 2009

2×19 Posts Quote:
 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))?

Last fiddled with by Gammatester on 2011-11-18 at 08:10  2011-11-18, 08:31   #278
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

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

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

Last fiddled with by LaurV on 2011-11-18 at 08:44  2011-11-18, 09:06 #279 Gammatester   Mar 2009 1001102 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 2011-11-18 at 09:06  2011-11-18, 09:27 #280 LaurV Romulan Interpreter   "name field" Jun 2011 Thailand 71×139 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 2011-11-18 at 09:40  2011-11-18, 10:42 #281 Gammatester   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.  2011-11-18, 15:04   #282
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

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

Last fiddled with by LaurV on 2011-11-18 at 15:55  2011-11-18, 15:39 #283 science_man_88   "Forget I exist" Jul 2009 Dumbassville 26×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))) 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  2011-11-18, 16:00 #284 fivemack (loop (#_fork))   Feb 2006 Cambridge, England 22×1,613 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 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.  2011-11-18, 16:16 #285 science_man_88   "Forget I exist" Jul 2009 Dumbassville 26·131 Posts ((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. Last fiddled with by science_man_88 on 2011-11-18 at 16:18  2011-11-18, 16:17   #286
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

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

Last fiddled with by LaurV on 2011-11-18 at 16:21  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Miscellaneous Math 3 2017-08-10 13:47 emily Math 34 2017-07-16 18:44 Nick Math 4 2017-04-01 16:26 Nick Number Theory Discussion Group 0 2016-12-03 11:42 optim PrimeNet 13 2004-07-09 13:51

All times are UTC. The time now is 08:49.

Sat Jan 22 08:49:55 UTC 2022 up 183 days, 3:18, 0 users, load averages: 1.62, 1.28, 1.20