Hello Sheueling,
You wrote:
>Robert, I have seen the following "polynomial Invert" code in your
>ecdl12K-108.32bit.c file.
>This is a very clean algorithm compared to the standard "polynomial divide".
>I am looking for a whitepaper that explains the math
>of this algorithm, i.e., how this algorithm works mathematically.
>Can you tell me where the source of this algorithm is from?
I'm afraid I don't know of any whitepaper. I just took a plain binary
Euclidean algorithm with the invariant mentioned in the code:
/* Maintain: u.y = a and v.y = b modulo t^109+t^9+t^2+t+1. */
and optimised it heavily. The binary Euclidean algorithm is described
in lots of references, but only for integers. The changes for
polynomials over GF(2) are easy however.
If you want similar code for a field other than GF(2^109), then just
let me know; I would be happy to provide it.
There is a simple variant where you count shifts, by maintaining u.y =
a<<n and v.y = b<<n instead, and apply them at the end. I think it
goes under the name "almost inverse" algorithm since somebody claimed
to have invented it and wrote about it in proceedings of some crypto
conference (can't remember which one though - a quick Web search
suggests that it might be Crypto'95).
Bye,
Rob.
This archive was generated by hypermail 2b29 : Mon May 22 2000 - 15:43:47 MET DST