I want to multiply and divide polynomials, and implement the extended Euclidean algorithm for polynomial greatest common divisors, over a Galois Field of size $2^{128}$. Moreover, I want to use the previous algorithms on an 8-bit microcontroller (ATMega128). Where can I find relevant libraries in C or Assembly? Ι would prefer C, if the implementation is not too inefficient. Thanks in advance.


The RELIC library has support for binary fields. Check the functions fb_inv_exgcd for inversion and fb_mul_lodah (which calls fb_muln_low and fb_rdcn_low) for multiplication. There is even a ATMega128 backend written in assembly, though it does not support 128-bit fields (but should give you a head start if you need to write it).

You will need to make a few adjustments in order to isolate the multiplication code, but it shouldn't be too hard. Or you can simply use the library as is.

(Disclosure: I'm one of its developers)

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.