Patent ID: 7031468

Claim:
A method for performing a cryptographic operation that comprises transforming digital information, the method comprising: providing digital information; providing a digital operator having a component selected from a large set of elements; expanding the component into a plurality of factors, each factor having a low hamming weight; and transforming the digital information using the digital operator, said transforming comprising computing multiples; said method further comprising: selecting a ring R; selecting an R-module M; selecting two or more subsets R 1 , R 2 , . . . , R k of R with the property that r 1 is an element in R 1 , r 2 is an element in R 2 , . . . and r k is an element in R k ; computing r*m, where r is in R and m is in M, by expanding r as r 1 *r 2 . . . r k , where k is an integer and computing the quantity r 1 *(r 2 *( . . . (r k *m).