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

Re: AKS implementation

Expand Messages
  • Phil Carmody
    From: Elena Erbiceanu ... If you re not using NTL, then you should be. Yves Gallot implemented several versions in C, using various bignum libraries, and
    Message 1 of 4 , Jun 28, 2005
      From: Elena Erbiceanu
      > I have done yesterday the "hiding" into a larger
      > prime,
      > and it does work, but it is awfully slow:
      > the whole AKS test required about 1800 iterations
      > (of the exponentiation), and it performed only about
      > 225 since 7 o'clock last night until this morning at
      > eight (for the number 1 000 000 007, the poly is
      > reduced modulo X^3623-1, and is hidden into a number
      > of 960 bits, which must be raised to the 1 000 000
      > 007'th power).

      If you're not using NTL, then you should be. Yves Gallot implemented
      several versions in C, using various bignum libraries, and various
      polynomial libraries. NTL shone as the fastest. Google for AKS
      implementations, and follow Anton Stiglic's little FAQ.

      Phil


      () ASCII ribbon campaign () Hopeless ribbon campaign
      /\ against HTML mail /\ against gratuitous bloodshed

      [stolen with permission from Daniel B. Cristofani]



      ____________________________________________________
      Yahoo! Sports
      Rekindle the Rivalries. Sign up for Fantasy Football
      http://football.fantasysports.yahoo.com
    Your message has been successfully submitted and would be delivered to recipients shortly.