[Cado-nfs-discuss] the theory behind the computation of alpha value
Zimmermann Paul
Paul.Zimmermann at loria.fr
Mon Aug 20 16:01:22 CEST 2012
Hi,
> Date: Mon, 20 Aug 2012 21:55:25 +0800
> From: mqseagle at sohu.com
>
> Hello all,
> I read the c code about the computation of alpha value in auxiliary.c, which can be used to measure the root properties of a polynomial. Though I can use it directly, I don't know why to do that way. Would someone be kind to explain the theory behind the algorithm or recommend some papers?
> Thank you.
> Best regards,
> Sincerely Meng
a reference is given in the source code of get_alpha():
/* Compute the value alpha(F) from Murphy's thesis, page 49:
alpha(F) = sum(prime p <= B, (1 - q_p*p/(p+1)) log(p)/(p-1))
where q_p is the number of roots of F mod p, including the number of
projective roots (i.e., the zeros of the reciprocal polynomial mod p).
alpha(F) is an estimate of the average logarithm of the part removed
from sieving, compared to a random integer.
We want alpha as small as possible, i.e., alpha negative with a large
absolute value. Typical good values are alpha=-4, -5, ...
*/
See www.cs.ox.ac.uk/people/richard.brent/ftp/Murphy-thesis.ps.gz
Paul Zimmermann
More information about the Cado-nfs-discuss
mailing list