mersenneforum.org MPQS b-parameter and Pell-like equations
 Register FAQ Search Today's Posts Mark Forums Read

 2016-01-13, 08:05 #1 Till     "Tilman Neumann" Jan 2016 Germany 1111000012 Posts MPQS b-parameter and Pell-like equations The b-parameter in MPQS, following [Pomerance 1985: "The quadratic sieve algorithm"], is defined as b^2 == N (mod g^2) .......................(1) and has solution b = N^((g^2-g+2)/4) mod g^2 ...........(2) if g == 3 (mod 4) and J(N|g)=1 .......(2b) I think we can transform eq. (1) b^2 == N (mod g^2) <=> b^2 - N == 0 (mod g^2) <=> b^2 - N = d*g^2 <=> b^2 - d*g^2 = N ......................(3) into the form of Pell-like equations. But in contrast to the standard case, here we have g and N given. Here are my questions: 1. Are both conditions in (2b) absolutely necessary ? 2. Does g have to be prime? Or can eq. (3) be solved efficiently as well if g is composite? Eventually in the case N=1 ? Till Last fiddled with by Till on 2016-01-13 at 08:07 Reason: indention of eq-labels
2016-01-13, 09:16   #2
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

151910 Posts

Quote:
 Originally Posted by Till The b-parameter in MPQS, following [Pomerance 1985: "The quadratic sieve algorithm"], is defined as b^2 == N (mod g^2) .......................(1)
What is g???

Quote:
 Originally Posted by Till and has solution b = N^((g^2-g+2)/4) mod g^2 ...........(2) if g == 3 (mod 4) and J(N|g)=1 .......(2b)
N=2;g=15 is a counterexample.
Is it really on that paper???

 2016-01-13, 09:23 #3 Till     "Tilman Neumann" Jan 2016 Germany 13·37 Posts Hi, thanks for the quick reply! I think I copied everything correctly. g is Pomerance's analog of the q-parameter in Contini's thesis; g^2 is the a-parameter. Maybe there is another condition I missed? E.g. it might make sense that N should be an odd integer, because it is a number to be factored. Till
 2016-01-13, 09:34 #4 Till     "Tilman Neumann" Jan 2016 Germany 1111000012 Posts Aah :) Good thing, your counterexample. It is said in the paper that g should be prime. One of the things I wanted to know is if that is really necessary. Your counterexample tells me that it is. So if there is an efficient solution for composite g, then it has to be a different one than eq. (2). I think I should refine my question: Independently of (2), (2b), what I am most interested in is: Given composite g, integer N, does the Pell-like equation b^2 - d*g^2 = N have some efficient solutions, and under which conditions? The special case N=1 would still be interesting, too. Last fiddled with by Till on 2016-01-13 at 09:51 Reason: refined question
 2016-01-13, 10:22 #5 R. Gerbicz     "Robert Gerbicz" Oct 2005 Hungary 72×31 Posts Found that equation: https://math.dartmouth.edu/~carlp/PDF/paper52.pdf (page 178). Don't know why you haven't given it. Anyway that is a trivial equation, one solution is given. If you need, for g=1 mod 4 you can use https://en.wikipedia.org/wiki/Tonell...anks_algorithm to solve the equation in polynomial time. Last fiddled with by R. Gerbicz on 2016-01-13 at 10:22
2016-01-13, 11:50   #6
Till

"Tilman Neumann"
Jan 2016
Germany

1E116 Posts

Quote:
 Originally Posted by R. Gerbicz Anyway that is a trivial equation, one solution is given. If you need, for g=1 mod 4 you can use https://en.wikipedia.org/wiki/Tonell...anks_algorithm to solve the equation in polynomial time.
Tonelli-Shanks does not apply here because the modulus g^2 is not prime.
The formula in Pomerance's paper works at least for a modulus g^2, g prime.

But it was good that you put my nose to the wikipedia article again. There it is said:
"Tonelli–Shanks cannot be used for composite moduli; finding square roots modulo composite numbers is a computational problem equivalent to integer factorization".

So I do not need to search any further.
Till

2016-01-13, 14:49   #7
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

72×31 Posts

Quote:
 Originally Posted by Till Tonelli-Shanks does not apply here because the modulus g^2 is not prime.
No. On the same page you can read the idea from Wagstaff:
solve y^2==N mod g, the solution is y==+- N^((g+1)/4) mod g if g==3 mod 4 or use Tonelli-Shanks algorithm for g==1 mod 4. Then use the so called Hensel lifting (see https://en.wikipedia.org/wiki/Hensel%27s_lemma) to solve x^2==N mod g^2, in this case we can write:

x^2==(y+k*g)^2==N mod g^2 (where k is an integer)
y^2+2*k*g==N mod g^2
k==(N-y^2)/(2*g) mod g is the only solution. So we got x=y+k*g (the other solution is -x)

And with this idea you can get much faster the solution than computing it with x==N^((g^2-g+2)/4) mod g^2.

Btw this is still very basic number theory.

 2016-01-13, 15:27 #8 Till     "Tilman Neumann" Jan 2016 Germany 13·37 Posts What you describe now is just a faster variant of the formula I started with. Both variants require g to be prime, or am I wrong on that? My question was if there is an efficient solution even if g is composite. The Wikipedia page about Tonelli-Shanks says no.
2016-01-13, 18:39   #9
jwaltos

Apr 2012

34×5 Posts

Quote:
 Originally Posted by Till Given composite g, integer N, does the Pell-like equation b^2 - d*g^2 = N have some efficient solutions, and under which conditions?
I may be misinterpreting your question either in part or wholly but I have read that the generalized Pell equation is NP complete. You may alter the equation cosmetically and obtain convenient solutions but nothing fundamentally new. There are many references on this equation given its importance: Lenstra, Granville, Barbeau, Robertson, Matthews, Fermat, Euler, there is a quantum Pell solution..Hall (<-pun intended)..Hallgren? and others. Note that this equation can be generalized to the general conic equation using the coordinate frame of your choice from which you can then proceed down any rabbit hole or turkey trail you choose. One interesting path exists within the lemniscate functions and complex analysis.

Last fiddled with by jwaltos on 2016-01-13 at 18:49 Reason: added stuff

 2016-01-13, 19:22 #10 Till     "Tilman Neumann" Jan 2016 Germany 13·37 Posts Hi, your answer looks substantial. I agree with "NP-complete" since I already found out in this thread "finding square roots modulo composite numbers is a computational problem equivalent to integer factorization". But now I'm off ;) I'll try to follow if this discussion continues, but as a computer scientist I do not know enough math. In the beginning I hoped for a simple solution... So long Till
2016-01-13, 19:40   #11
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

11·17·59 Posts

Quote:
 Originally Posted by Till I agree with "NP-complete" since I already found out in this thread "finding square roots modulo composite numbers is a computational problem equivalent to integer factorization".
Remember, though, that factorization is an example, perhaps the example, of a problem which is clearly in NP but unknown as to whether or not it is in P.

I'm one of the optimists who think that it may be in P. My reasons for optimism have been published here before but can be summarized by:

Primality used to be as hard as factorization. It is now known to be in P.

Until 1970, factorization algorithms took time O(L(1)) --- or exponential in log(N). It was then proved to take L(1/2) or, handwaving furiously, halfway between exponential and polynomial. The NFS was the first L(1/3) algorithm and there are persuasive rumours that an unpublished L(1/4) algorithm has been developed.

Disclaimer: reasons for optimism are very far short of arguments for a proof.

Last fiddled with by xilman on 2016-01-13 at 19:42 Reason: Fix tipo

 Similar Threads Thread Thread Starter Forum Replies Last Post jwaltos Miscellaneous Math 0 2015-08-29 02:13 Sam Kennedy Factoring 3 2012-12-22 15:41 smoking81 Factoring 10 2007-10-02 12:30 bsquared Factoring 3 2007-02-28 14:22 T.Rex Math 0 2005-03-29 21:16

All times are UTC. The time now is 00:54.

Tue Dec 7 00:54:20 UTC 2021 up 136 days, 19:23, 1 user, load averages: 1.22, 1.38, 1.25