Re: [PrimeNumbers] Help with AKS primality proving
- -----BEGIN PGP SIGNED MESSAGE-----
On Saturday 26 July 2003 08:22, purephil wrote:
> I hope you don't mind this post but I could really do with some help!
> I am a University student in the UK trying to
> implement an relatively efficient (..oh...dear...) GMP version
> of AKS (off paper ver_3; change on bound and size of r etc..).
> However, I am not 100% sure how to do the:
> STEP V: Zalen/N[x]/((x^r)-1)
> I understand how to reduce an expanded polynomial, but since I
> appreciate that this will be exponential in the size of
> its input (N) this is the crappiest way ever as I will have to
> expand N coeffecients...
OK, now I don't know anything about AKS and whether these polynomials are
really huge, but once the asymptotics take over, cyclic convolution via FFTs
methods are optimal for this problem.
How big (in terms of degree) are these polynomials?
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (GNU/Linux)
-----END PGP SIGNATURE-----