Shamir´s shared secret scheme in GF(pm)

A. Shamir´s (1979) shared secret scheme is adapted to operate over an extension field GF(p)[x]/x^m-ω where p is an odd prime p. Both multiplication and multiplicative inverse in such a field can be efficiently computed on 8-bit microcontrollers with appropriate choice of p and exploiting the built-in byte-multiply instruction. In applications with fixed p, m, and ω further acceleration can be achieved via a small set of pre-computed values. Pre-computation also eliminates the necessity for division at the sub-field level. A brief discussion on efficiency and memory trade-off is provided. It is found that reconstruction of a 128-bit secret under a (2,3) threshold scheme on a low-end smart card is not impractical