mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2011-10-11, 08:24   #1
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

24·13·47 Posts
Default 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?
LaurV is offline   Reply With Quote
Old 2011-10-11, 10:09   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by LaurV View Post
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
R.D. Silverman is offline   Reply With Quote
Old 2011-10-11, 14:06   #3
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

24×13×47 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
LaurV is offline   Reply With Quote
Old 2011-10-11, 14:52   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2011-10-11, 16:33   #5
ccorn
 
ccorn's Avatar
 
Apr 2010

2×3×52 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.
ccorn is offline   Reply With Quote
Old 2011-10-12, 02:27   #6
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

24×13×47 Posts
Default

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).
LaurV is offline   Reply With Quote
Old 2011-10-15, 02:30   #7
ccorn
 
ccorn's Avatar
 
Apr 2010

9616 Posts
Default

Quote:
Originally Posted by LaurV View Post
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
ccorn is offline   Reply With Quote
Old 2011-10-15, 11:36   #8
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

24×13×47 Posts
Default

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.
LaurV is offline   Reply With Quote
Old 2011-10-15, 11:48   #9
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.
science_man_88 is offline   Reply With Quote
Old 2011-10-15, 12:12   #10
axn
 
axn's Avatar
 
Jun 2003

514910 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.
axn is offline   Reply With Quote
Old 2011-10-15, 19:24   #11
ccorn
 
ccorn's Avatar
 
Apr 2010

9616 Posts
Default

Quote:
Originally Posted by LaurV View Post
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
ccorn is offline   Reply With Quote
Reply

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

All times are UTC. The time now is 01:48.


Thu Oct 21 01:48:14 UTC 2021 up 89 days, 20:17, 1 user, load averages: 1.85, 1.55, 1.40

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.