20111011, 08:24  #1 
Romulan Interpreter
"name field"
Jun 2011
Thailand
10005_{10} Posts 
question: decidability for quadratic residues modulo a composite
How hard is to decide if a given x is a quadratic residue modulo a composite number n? I am aware of Legendre and Jacobi symbols and their properties, that could be used to check if a number x is a quadratic residue modulo n, for a prime n. My question is how hard is this problem for a composite n, assuming the Jacobi symbol is 1 (when it is 1, the answer is clear, x is not a quadratic residue mod the composite n, and I assume that the factors of n are not known, so x does not divide n, i.e. Jacobi symbol is not 0). Any known algorithms? Is this problem equivalent to integer factorization for general case? (large old composites without special properties). How about special cases, like Mersenne, Fermat, etc numbers? Does any algorithm exists to find out if a given x is a quadratic residue modulo a composite Mersenne number Mp, for example?

20111011, 10:09  #2  
"Bob Silverman"
Nov 2003
North of Boston
1110100101000_{2} Posts 
Quote:


20111011, 14:06  #3 
Romulan Interpreter
"name field"
Jun 2011
Thailand
3×5×23×29 Posts 
So, it is equivalent with integer factorization... Thanks for the answer.
This seems to be the logical answer, but I hopped... Now, if some Joe Average is coming with his magic hat, and I give him some x, and he puts my x in his magical hat and he tells me at once if my x is quadratic residue or not, how could I use this information to factor n? Only one x is allowed, and I assume I can "carefully" select this x, before giving it to Joe... Any tips and tricks? Links to the math? Last fiddled with by LaurV on 20111011 at 14:09 
20111011, 14:52  #4  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}×3×311 Posts 
Quote:
(given exponentially many such q.r.'s it can be done by an old technique of D.H. Lehmer known as exclusion moduli.) Use the a_i to restrict the search in Fermat's Method. Given enough a_i, one can severely restrict the possible set of x_i such that x_i^2 = y^2 mod N. 

20111011, 16:33  #5 
Apr 2010
3^{2}·17 Posts 
Testing one x with Joe's magic hat gives about 1 bit of information. You need about a quarter of the bitlength of the number to be factored before you can dismiss Joe and his hat. Therefore, allowing only one test does not make sense.

20111012, 02:27  #6 
Romulan Interpreter
"name field"
Jun 2011
Thailand
10011100010101_{2} Posts 
It does make sense, I have something I am driving at. That's why I especially added that part. Right now I want to understand better what is going on. Still reading about exclusion moduli, I found some nice papers on the web. By the way, is anyone having the books of Richard A Mollin in some readable format and "uncensored" text? (on google books they have "previews" from which about half of the pages are missing, like one page is shown or not, on random basis, and I have to reload the preview many times to get the missing pages).

20111015, 02:30  #7 
Apr 2010
3^{2}×17 Posts 
If all that you can get is one yes or no, then this cannot help much. Otherwise you could as well guess, or try both cases. Then you would not need Joe and his hat at all.
Last fiddled with by ccorn on 20111015 at 02:55 
20111015, 11:36  #8 
Romulan Interpreter
"name field"
Jun 2011
Thailand
3×5×23×29 Posts 
Yo can't guess. You need a precise answer. I will give you an example:
Assume p is a prime and m=Mp its correspondent mersenne number. Let x=2^((p1)/2)+1. If neither x nor x is quadratic residue, then Mp is composite. I don't know if this result is known, but if it is not known, it is because nobody bothered to compute it, because the proof is really elementary calculus. So, how "guessing" will help you in this case? If you have Joe's hat, he could tell you at once if x or x are residues. If none of them is, then you don't need to run a LL test. If one of them turn out to be a residue (in this example only one can be residue, because Mp is 4k+3 and 1 is never a quadratic residue, so only one of z and z can be qr, for any z), then in that case you still don't know anything about primality of Mp. 
20111015, 11:48  #9  
"Forget I exist"
Jul 2009
Dumbassville
2·5·839 Posts 
Quote:


20111015, 12:12  #10 
Jun 2003
1010100001010_{2} Posts 

20111015, 19:24  #11  
Apr 2010
3^{2}·17 Posts 
Quote:
Edit: OK, it's just one question because only one Jacobi symbol can be +1, and the other one need not be asked. Yet, this is is not about determining factors. Anyway, seeing that the idea makes you read about exclusion moduli (and perhaps even Lehmer's bicycle chain sieve), I'll stop grunting and let you follow your thoughts. Last fiddled with by ccorn on 20111015 at 19:52 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Basic Number Theory 18: quadratic equations modulo n  Nick  Number Theory Discussion Group  4  20170327 06:01 
quadratic residues  zippy  Math  6  20150720 13:09 
residues and non residues of general quadratic congruences  smslca  Math  0  20121012 06:42 
Quadratic Residues  Romulas  Math  3  20100509 03:27 
a question on decidability  Orgasmic Troll  Math  3  20050901 04:42 