[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