Method and apparatus for modulus reduction
AssigneeCerticom Corp.
InventorRobert John LAMBERT
Life of this patent
Estimating the term…
Abstract
A modulo reduction is performed on a value a represented as an ordered sequence of computer readable words. The lowest order words are eliminated by substituting an equivalent value represented by higher order words for each of the lower order words. The lowest order words are eliminated until the sequence has a word length corresponding to the modulus. Carries and borrows resulting from the substitution are propagated from lower order words to higher order words. Further reduction is performed to maintain the word length of the sequence to that of the modulus. The further reduction may be determined by examination of a carryover bit or may be performed a predetermined number of times without examination.
Claims27
A method for reducing a value a to a reduction of the value modulo a modulus p, said modulus being represented by a data string having a length of g words, said method comprising:
- a) representing the value a as an ordered sequence of f words, where f is greater than g, said sequence thereby including (f−g) lower order words, each of said words of said sequence having a predetermined number of computer readable bits:
- b) eliminating said (f−g) lower order words of said sequence so that not more than g words remain in said sequence by, for each of said lower order words, performing a substitution in said sequence of an equivalent value, modulo p, said equivalent value being represented by at least one word and each such word having an order higher than that of said lower order word for which such equivalent value is substituted;
- c) propagating carries and borrows arising during said substitutions of said equivalent values and performing such further reduction as necessary to maintain not more than g words in said sequence;
- and,
- d) utilizing the ordered sequence of g words remaining as a representation of the reduction of the value modulo p.
A cryptographic module on a computing device to perform cryptographic operations, said module comprising:
- a) a reduction machine for reducing a value, a, to a reduction of the value modulus p, said modulus p being represented as a data string having a length of g words, said reduction machine including
- i) register files to store data;
- and
- ii) an arithmetic logic unit to read data from said register files, perform computations on said data, and return results of computations to said register files;
- and
- b) a controller for controlling operation of said reduction machine, based on executable instructions, by controlling operation of said register files and said arithmetic logic unit;
- wherein said instructions are configured to cause said reduction machine to
- I) enter said value a in said register files as an ordered sequence of f words, where f is greater than g;
- said register files including (f−g) lower order words, each of said words of said sequence having a predetermined number of computer readable bits
- II) eliminate said (f−g) lower order words of said sequence so that not more than g words remain in said sequence by, for each of said lower order words, performing a substitution in said sequence of an equivalent value, modulo p, said equivalent value being represented by at least one word and each such word having an order higher than that of said lower order word for which such equivalent value is substituted;
- III) propagate carries and borrows arising during said substitutions of said equivalent values and perform such further reduction as necessary to maintain not more than g words in said sequence;
- and
- IV) output from said register files the ordered sequence of g words remaining as a representation of the reduction of the value modulo p.
A computer readable medium having stored thereon computer executable instructions for performing a method for reducing a value a to a reduction of the value modulo a modulus p, said modulus being represented by a data string having a length of g words, the computer executable instructions comprising instructions:
- a) representing the value a as an ordered sequence of f words, where f is greater than g, said sequence thereby including (f−g) lower order words, each of said words of said sequence having a predetermined number of computer readable bits:
- b) eliminating said (f−g) lower order words of said sequence so that not more than g words remain in said sequence by, for each of said lower order words, performing a substitution in said sequence of an equivalent value, modulo p, said equivalent value being represented by at least one word and each such word having an order higher than that of said lower order word for which such equivalent value is substituted;
- c) propagating carries and borrows arising during said substitutions of said equivalent values and performing such further reduction as necessary to maintain not more than g words in said sequence;
- and
- d) outputting the ordered sequence of g words remaining as a representation of the reduction of the value modulo p.
Dependencies are inferred from the claim text.