20160113, 08:05  #1 
"Tilman Neumann"
Jan 2016
Germany
2^{2}·3·5·7 Posts 
MPQS bparameter and Pelllike equations
The bparameter 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^2g+2)/4) mod g^2 ...........(2) if g == 3 (mod 4) and J(Ng)=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 Pelllike 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 20160113 at 08:07 Reason: indention of eqlabels 
20160113, 09:16  #2  
"Robert Gerbicz"
Oct 2005
Hungary
594_{16} Posts 
Quote:
Quote:
Is it really on that paper??? 

20160113, 09:23  #3 
"Tilman Neumann"
Jan 2016
Germany
2^{2}×3×5×7 Posts 
Hi,
thanks for the quick reply! I think I copied everything correctly. g is Pomerance's analog of the qparameter in Contini's thesis; g^2 is the aparameter. 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 
20160113, 09:34  #4 
"Tilman Neumann"
Jan 2016
Germany
2^{2}·3·5·7 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 Pelllike 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 20160113 at 09:51 Reason: refined question 
20160113, 10:22  #5 
"Robert Gerbicz"
Oct 2005
Hungary
594_{16} 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 20160113 at 10:22 
20160113, 11:50  #6  
"Tilman Neumann"
Jan 2016
Germany
2^{2}×3×5×7 Posts 
Quote:
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 

20160113, 14:49  #7  
"Robert Gerbicz"
Oct 2005
Hungary
2^{2}×3×7×17 Posts 
Quote:
solve y^2==N mod g, the solution is y==+ N^((g+1)/4) mod g if g==3 mod 4 or use TonelliShanks 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==(Ny^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^2g+2)/4) mod g^2. Btw this is still very basic number theory. 

20160113, 15:27  #8 
"Tilman Neumann"
Jan 2016
Germany
2^{2}×3×5×7 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 TonelliShanks says no. 
20160113, 18:39  #9 
Apr 2012
364_{10} Posts 
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 20160113 at 18:49 Reason: added stuff 
20160113, 19:22  #10 
"Tilman Neumann"
Jan 2016
Germany
2^{2}×3×5×7 Posts 
Hi,
your answer looks substantial. I agree with "NPcomplete" 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 
20160113, 19:40  #11  
Bamboozled!
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across
2^{8}·41 Posts 
Quote:
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 20160113 at 19:42 Reason: Fix tipo 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Generalized Pell Equation.  jwaltos  Miscellaneous Math  0  20150829 02:13 
The MPQS differs from the QS  Sam Kennedy  Factoring  3  20121222 15:41 
Implementing MPQS: SOS!  smoking81  Factoring  10  20071002 12:30 
poly selection in MPQS  bsquared  Factoring  3  20070228 14:22 
Generalized Pell Numbers  T.Rex  Math  0  20050329 21:16 