[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.
More information about the SeqFan
mailing list