[seqfan] Re: Help with sequence

[andrew at nevercenter.com]

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.