mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Abstract Algebra & Algebraic Number Theory

Reply
 
Thread Tools
Old 2016-01-13, 08:05   #1
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

419 Posts
Default 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
Till is offline   Reply With Quote
Old 2016-01-13, 09:16   #2
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

22·5·71 Posts
Default

Quote:
Originally Posted by Till View Post
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 View Post
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???
R. Gerbicz is offline   Reply With Quote
Old 2016-01-13, 09:23   #3
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

419 Posts
Default

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
Till is offline   Reply With Quote
Old 2016-01-13, 09:34   #4
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

419 Posts
Default

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
Till is offline   Reply With Quote
Old 2016-01-13, 10:22   #5
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

22×5×71 Posts
Default

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
R. Gerbicz is offline   Reply With Quote
Old 2016-01-13, 11:50   #6
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

419 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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
Till is offline   Reply With Quote
Old 2016-01-13, 14:49   #7
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

22×5×71 Posts
Default

Quote:
Originally Posted by Till View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2016-01-13, 15:27   #8
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

419 Posts
Default

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.
Till is offline   Reply With Quote
Old 2016-01-13, 18:39   #9
jwaltos
 
jwaltos's Avatar
 
Apr 2012

349 Posts
Default

Quote:
Originally Posted by Till View Post
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
jwaltos is offline   Reply With Quote
Old 2016-01-13, 19:22   #10
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

419 Posts
Default

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
Till is offline   Reply With Quote
Old 2016-01-13, 19:40   #11
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

25·52·13 Posts
Default

Quote:
Originally Posted by Till View Post
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
xilman is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Generalized Pell Equation. jwaltos Miscellaneous Math 0 2015-08-29 02:13
The MPQS differs from the QS Sam Kennedy Factoring 3 2012-12-22 15:41
Implementing MPQS: SOS! smoking81 Factoring 10 2007-10-02 12:30
poly selection in MPQS bsquared Factoring 3 2007-02-28 14:22
Generalized Pell Numbers T.Rex Math 0 2005-03-29 21:16

All times are UTC. The time now is 18:53.

Sat Dec 5 18:53:10 UTC 2020 up 2 days, 15:04, 0 users, load averages: 2.53, 2.67, 2.77

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.