mersenneforum.org  

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

Closed Thread
 
Thread Tools
Old 2011-11-18, 05:35   #276
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

216738 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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
LaurV is offline  
Old 2011-11-18, 08:02   #277
Gammatester
 
Gammatester's Avatar
 
Mar 2009

2·19 Posts
Default

Quote:
Originally Posted by LaurV View Post
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
Gammatester is offline  
Old 2011-11-18, 08:31   #278
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

216738 Posts
Default

Quote:
Originally Posted by Gammatester View Post
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
LaurV is offline  
Old 2011-11-18, 09:06   #279
Gammatester
 
Gammatester's Avatar
 
Mar 2009

2·19 Posts
Default

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
Gammatester is offline  
Old 2011-11-18, 09:27   #280
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

216738 Posts
Default

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
LaurV is offline  
Old 2011-11-18, 10:42   #281
Gammatester
 
Gammatester's Avatar
 
Mar 2009

2·19 Posts
Default

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.
Gammatester is offline  
Old 2011-11-18, 15:04   #282
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

3×3,049 Posts
Default

Quote:
Originally Posted by Gammatester View Post
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
LaurV is offline  
Old 2011-11-18, 15:39   #283
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

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
science_man_88 is offline  
Old 2011-11-18, 16:00   #284
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

7·911 Posts
Default

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.
fivemack is offline  
Old 2011-11-18, 16:16   #285
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

((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
science_man_88 is offline  
Old 2011-11-18, 16:17   #286
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

3·3,049 Posts
Default

Quote:
Originally Posted by fivemack View Post
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
LaurV is offline  
Closed Thread

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 2017-08-10 13:47
Distribution of Mersenne primes before and after couples of primes found emily Math 34 2017-07-16 18:44
Mersenne primes and class field theory Nick Math 4 2017-04-01 16:26
Basic Number Theory 11: Gaussian primes Nick Number Theory Discussion Group 0 2016-12-03 11:42
Mersenne Wiki: Improving the mersenne primes web site by FOSS methods optim PrimeNet 13 2004-07-09 13:51

All times are UTC. The time now is 11:29.

Tue Jan 19 11:29:56 UTC 2021 up 47 days, 7:41, 0 users, load averages: 1.56, 1.69, 1.73

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.