[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


> 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