Loading ...
Sorry, an error occurred while loading the content.
 

Re: [PrimeNumbers] Help with AKS primality proving

Expand Messages
  • Décio Luiz Gazzoni Filho
    ... Hash: SHA1 ... OK, now I don t know anything about AKS and whether these polynomials are really huge, but once the asymptotics take over, cyclic
    Message 1 of 2 , Jul 26, 2003
      -----BEGIN PGP SIGNED MESSAGE-----
      Hash: SHA1

      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?

      Décio
      -----BEGIN PGP SIGNATURE-----
      Version: GnuPG v1.2.2 (GNU/Linux)

      iD8DBQE/Irftce3VljctsGsRAsBkAJwP3ZhEcm8nH3jfQy81Vmp3OIbungCfQWkO
      /vnp0TMvsC9iv5u5IPA6n4c=
      =nP4q
      -----END PGP SIGNATURE-----
    Your message has been successfully submitted and would be delivered to recipients shortly.