Alternate memory compression schemes for modular multiplication

A memory compression scheme which reduces the size of the lookup tables for modular multiplication by using a new symmetry property is presented. The compression ratio for a modulus p is equal to 4 and implies a 75% savings except if p is even and small. Although this compression ratio has been achieved before, the present scheme has the advantage of simpler peripheral hardware. A further benefit is that it lends itself to additional reduction of table size by a factor of about two, for a total savings of 87%. This additional reduction requires two stages of table lookup or more complicated addressing circuits. This modification, which achieves table compression by a factor of eight, is quite attractive in applications where long sequences of multiplications are performed. It is shown that by using a multiplication algorithm based on squaring, a compression ratio of roughly p/2 is achievable with moderate hardware complexity, and two lookup steps