mersenneforum.org > Math question: decidability for quadratic residues modulo a composite
 Register FAQ Search Today's Posts Mark Forums Read

 2011-10-11, 08:24 #1 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 1000510 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?
2011-10-11, 10:09   #2
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

11101001010002 Posts

Quote:
 Originally Posted by LaurV 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, ?
Factor n

2011-10-11, 14:06   #3
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

3×5×23×29 Posts

Quote:
 Originally Posted by R.D. Silverman Factor n
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 2011-10-11 at 14:09

2011-10-11, 14:52   #4
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

23×3×311 Posts

Quote:
 Originally Posted by LaurV So, it is equivalent with integer factorization... Thanks for the answer. This seems to be the logical answer, but I hopped...
It is equivalent in one direction. I do not know of a way to factor n in polynomial time given that (say) a_1, a_2, a_3, ... a_k are known q.r.'s
(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.

2011-10-11, 16:33   #5
ccorn

Apr 2010

32·17 Posts

Quote:
 Originally Posted by LaurV 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?
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.

 2011-10-12, 02:27 #6 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 100111000101012 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).
2011-10-15, 02:30   #7
ccorn

Apr 2010

32×17 Posts

Quote:
 Originally Posted by LaurV It does make sense, I have something I am driving at. That's why I especially added that part.
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 2011-10-15 at 02:55

 2011-10-15, 11:36 #8 LaurV 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^((p-1)/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.
2011-10-15, 11:48   #9
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

2·5·839 Posts

Quote:
 Originally Posted by LaurV 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^((p-1)/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.
see the statement that MP is 4k+3 is useful in deleting half the needed checks then because 3+3+1 = 7 mod 4 =3 mod 4 so if one is then ever single MP after that must also be 3=3 mod 4 7= 3 mod 4 15 = 3 mod 4 etc. so since all are for every case we'd only need half the checks.

2011-10-15, 12:12   #10
axn

Jun 2003

10101000010102 Posts

Quote:
 Originally Posted by LaurV Yo can't guess. You need a precise answer. I will give you an example:
Sure you can. First time, you proceed as if Joe said "yes". If that doesn't work out, you proceed as if Joe said "no". IOW, Joe giving a precise answer will only cut your effort by half.

2011-10-15, 19:24   #11
ccorn

Apr 2010

32·17 Posts

Quote:
 Originally Posted by LaurV 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.
That's two questions already. And this setup is not about determining factors.

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 2011-10-15 at 19:52

 Similar Threads Thread Thread Starter Forum Replies Last Post Nick Number Theory Discussion Group 4 2017-03-27 06:01 zippy Math 6 2015-07-20 13:09 smslca Math 0 2012-10-12 06:42 Romulas Math 3 2010-05-09 03:27 Orgasmic Troll Math 3 2005-09-01 04:42

All times are UTC. The time now is 19:35.

Wed Aug 10 19:35:09 UTC 2022 up 34 days, 14:22, 3 users, load averages: 2.10, 1.80, 1.76