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

Looking for resources

Expand Messages
  • Phil Carmody
    I m many miles from home, and without my C&P, and floundering with my google searches. I don t suppose someone could provide some links, or a few quick hints
    Message 1 of 1 , Jul 7, 2005
    • 0 Attachment
      I'm many miles from home, and without my C&P, and floundering with my google
      searches. I don't suppose someone could provide some links, or a few quick
      hints for the following.

      Is it possible to evaluate a polynomial (in Z_p[x]) of degree n at many, say m,
      points efficiently? i.e. o(m*n) operations mod p.
      How about evaluating the product of all of the above evaluations directly,
      without needing to generate their individual values?

      My memory is telling me that there is such an FFT-based technique, but for the
      life of me I can't re-invent it.

      Phil


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

      [stolen with permission from Daniel B. Cristofani]



      ____________________________________________________
      Sell on Yahoo! Auctions – no fees. Bid on great items.
      http://auctions.yahoo.com/
    Your message has been successfully submitted and would be delivered to recipients shortly.