# [seqfan] Re: Help with sequence

David Wilson dwilson at gambitcomm.com
Tue Aug 25 22:35:05 CEST 2009

```I don't think you are going to find what you want.

If, for any given a and n, you were quickly able to solve

n = y^2 - a^2x^2

then by choosing a = 1, you could quickly solve

n = y^2 - x^2

which is the same as solving

n = (y + x)(y - x)

This translates to a quick factorization algorithm for n.

In other words, your problem is equivalent to the factorization of n you
wish to avoid.

andrew at nevercenter.com wrote:
> Quoting Ignacio Larrosa Cañestro <ilarrosa at mundo-r.com>:
>> n = y^2 - a^2x^2 = (y + ax)(y - ax)
>>
>> and reduces to a system of linear equations
>>
>> y + ax = d1
>>
>> y - ax = d2
>>
>> where d1*d2 = n, and easy to solve.
>
> Yes, this is assuming you know the factors of n. I'm curious, though,
> if something along these lines could be used to "profile" a^2*x^2,
> without having to directly factor n.
>
> If, via the Hasse-Minkowski theorem, you can show that a^2*x^2 + n =
> y^2 has solutions for some set A = {a_1, a_2, ... a_n}, where a_i is
> prime, then these would be very good candidates for inclusion in your
> factor base when running the quadratic sieve algorithm. For values of
> a where there are no solutions, there's a simple way to extend the
> approach so that you can generate a bunch of linear congruences of the
> form x == r_j mod (a_i), which can be joined to make a sort of sieve
> to narrow down possible values for x.

```