MPQS b-parameter and Pell-like equations

[Till]

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

[R. Gerbicz]

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

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

[Till]

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]

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.

[R. Gerbicz]

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.

[Till]

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

[R. Gerbicz]

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.

[Till]

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.

[jwaltos]

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.

[Till]

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

[xilman]

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.