Re: Shamir sharing and GF(2^n)

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Ah, FFT...I'm having this much trouble wrapping my head around GFs and
now you wanna bring FFT into it... :-) Well, if indeed I have a
practical application for an FFT it might be worth my while to
understand it. I don't have the money for any new textbooks at the
moment--if I did, I'd probably be glued to Applied Cryptography right
now--but I am curious about your paper (as long as using some of the
information therein doesn't involve any patent licenses...).

To put it another way, yes, I'm interested. Would you mind letting me
have a look?

Thanks -- PSM

Ben Rudiak-Gould wrote:
You can do the encoding in O(n log n) time and the decoding in O(n log^2
n) time with FFT techniques. Various O(n polylog n) algorithms for this
general problem are described in chapter 5 of _Modern Computer Algebra_
by von zur Gathen and Gerhard. I have an unpublished paper describing
very efficient and relatively simple algorithms for the special case of
fields of order 2^(2^i), which I can email to the OP if he's interested.
(Also, the paper describes a way of constructing the fields without
finding an irreducible polynomial.)
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.2 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFFIsE1ei6R+3iF2vwRAmc3AKC8CcyJp9nNxmGsnyMmQzYvpwOqagCfRFFA
tX/Tyu1NtqIUg8rvQZCUzVk=
=c2xZ
-----END PGP SIGNATURE-----
.

Relevant Pages

  • Re: FFT algoritms
    ... trying to infer, from the illustration, what the rhyme or reason there ... place algorithms without bit-reversal. ... if you compare a highly optimized in-order FFT like FFTW ... One reason to be cautious here is that O&S is comparing apples and ...
    (comp.dsp)
  • Re: dft : property of symmetry for real & even seq
    ... *begin rant* ... In the same section ("Other FFT algorithms") as the one where the ... What they are referring to is the fact that higher radices can reduce ... The discussion of the Winograd algorithms in NR is mostly garbled; ...
    (comp.dsp)
  • Re: (Execution Cycles) Timing Budget for TI eZdspf2812
    ... I am designing different algorithms on the DSP to work in real ... filter and FFT i can design to run in real time. ...
    (comp.dsp)
  • Re: implementation dilema
    ... algorithms are different.. ... For instance (algorithm_ab1/ab2/ab4 is comprised of an FFT, ... Statistics like mean and standard deviation are intrinsic properties of data collections. ...
    (comp.object)
  • Re: dft : property of symmetry for real & even seq
    ... a few times slower than highly composite N). ... Bluestein FFT or Rader FFT). ... are many distinct FFT algorithms, in addition to the most well known ... (I've been repeatedly correcting the popular misconception that N log ...
    (comp.dsp)
Loading