Method and apparatus for modulus reduction

摘要

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.

主权项

1. A computer implemented method in a computing device 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, via a processor of the computing device, 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 arranged in a bit pattern to represent a value of that word; b) eliminating, via the processor, 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, each such word having an order higher than that of said lower order word for which such equivalent value is substituted, said substitution, being absent a multiplication operation step and applying a bit pattern representing said lower order word in said sequence to higher order words to provide said equivalent value, said substitution eliminating each said lower order word at each iteration to result in higher order words remaining in said sequence; c) propagating, via the processor, carries and borrows stored in a memory of the computing device and arising during said substitutions of said equivalent values and performing further reduction in response to a presence of said carries indicated in the memory and subsequent to said propagation to maintain not more than g words in said sequence; and, d) utilizing, via the processor, the ordered sequence of g words remaining from the memory as a representation of the reduction of the value modulo p and,
wherein said equivalent value includes a negative higher order word and said substitution includes a summation of like-order words and attribution of a borrow to an adjacent word of higher order when said summation produces a value less than a minimum word value.