Re: NFS Square root

From: Big Boy (no@email.com)
Date: 04/14/03 

From: Big Boy <no@email.com>
Date: 13 Apr 2003 20:41:32 -0500

On Fri, 11 Apr 2003 07:00:10 +0100, Chris Card <ctcard@hotmail.com>
wrote:

>On Thu, 10 Apr 2003 17:34:47 -0400, Eric <no@email.com> wrote:
>
>
>> The closest I got to a rough estimate is in that last mentioned paper,
>> that is
>>
>> |B(m)| <= d^((d+5)/2) * N * (2 u sqrt(d) N^(1/d))^(#S/2) for
>> polynomial f(x) of drgree 'd' specifically choosen. And that paper
>> itself reffer to another one on how to estimate 'u' and '#S', that
>> isn't immediately available to me.
>>
>> Help would greatly be appreciated.
>> Thanks.
>>
>> Eric.
>>
>Surely you don't have to estimate 'u' and '#S', since they are defined in
>Couveignes paper:
>"we let u be an upper bound for all numbers |a|,|b| for which (a,b) are in
>S" where S is the set of relations used to form the squares and #S is the
>size
>of S.
>
>Chris

Yes, I saw in that last paper I mentioned the note about 'u'. And I
figured that #S was the number of (a+b<alpha>) relations. I did some
quick tests and the values seem very rough indeed.

Well, I'm currently trying to implement the idea about doing an
estimate with complex numbers instead, we'll see if I can code
algorithm that arrive somewhat to the intended result ;-) I didn't
want to mess with complex numbers but finally, it isn't that bad!

Thanks.