A high performance ROM-based structure for modular exponentiation

Modular processing of large numbers requires high speed computing resources. In particular an operation slowing the whole computing process heavily is modular exponentiation. A previous method reduces the computation of x powered to e mod m to at most n simpler modular exponentiations (x sub i) powered to eta mod (m sub i), where m sub i is an element of the factorization of m, x sub i is equal to x mod (m sub i) and eta<(m sub i). A technique speeding up (x sub i) powered to eta mod (m sub i) is presented. The idea is to extend the discrete logarithm, reducing to a sole fixed base exponentiation, which can be tabulated. More precisely, depending on modulus value, specific expressions are devised leading to the definition of an extension of the discrete logarithm. Using these expressions a method based on tables is presented and evaluated in term of table size. An implementation of the method is also presented and its response time is derived; for moduli up to about 28 bits long it amounts to 120 - 150 nanoseconds