question: decidability for quadratic residues modulo a composite

LaurV · 2011-10-11, 08:24

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?

R.D. Silverman · 2011-10-11, 10:09

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

LaurV · 2011-10-11, 14:06

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?

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

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.

ccorn · 2011-10-11, 16:33

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.

LaurV · 2011-10-12, 02:27

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

ccorn · 2011-10-15, 02:30

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.

LaurV · 2011-10-15, 11:36

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.

science_man_88 · 2011-10-15, 11:48

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.

axn · 2011-10-15, 12:12

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.

ccorn · 2011-10-15, 19:24

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.

2011-10-11, 08:24	#1
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 10005₁₀ 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?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Basic Number Theory 18: quadratic equations modulo n	Nick	Number Theory Discussion Group	4	2017-03-27 06:01
quadratic residues	zippy	Math	6	2015-07-20 13:09
residues and non residues of general quadratic congruences	smslca	Math	0	2012-10-12 06:42
Quadratic Residues	Romulas	Math	3	2010-05-09 03:27
a question on decidability	Orgasmic Troll	Math	3	2005-09-01 04:42

2011-10-12, 02:27	#6
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 10011100010101₂ 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, 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.