Computer-implemented method and computer for performing modular reduction

Claim 2

In an electronic system involving transmission of data over a network between two computing units, a computer-implemented method comprising the following steps: sending data from one computing unit to another; and processing the data at one of the computing units using a modular reduction operation "X mod M," where X is a number with k+1 blocks written in base α, X=<x k x k-1 . . . x 1 x 0 >, and M is a modulus having n blocks, M=<m n-1 m n-2 . . . m 1 m 0 >, and n<k+1, said processing step comprising defining a constant U that is equal to α n+1 mod M, reducing the number X by an integer multiple of α n+1 to yield an intermediate value that is less than the number X but greater than zero, and compensating for reduction of the number X by adjusting the intermediate value by an amount that is one of (1) an integer multiple of the constant U or (2) an integer multiple of a constant V, where V=M-U, to yield an incrementally reduced value X R that is equivalent modulo M to the number X.

Claim 3

A computer-implemented method as recited in claim 1 wherein the processing step comprises adding the integer multiple of the constant U to the intermediate value.

Claim 4

A computer-implemented method as recited in claim 1 wherein the processing step comprises subtracting the integer multiple of the constant V from the intermediate value.

Claim 5

A computer-implemented method as recited in claim 1 wherein the processing step comprises subtracting the integer multiple of the constant U from the intermediate value.

Claim 6

A computer-implemented method as recited in claim 1 wherein the processing step comprises computing an intermediate value that is equal to X mod α k .

Claim 7

A computer-implemented method as recited in claim 1 wherein the processing step comprises deleting a most significant block x k from the number X to yield the intermediate value.

Claim 8

A computer-implemented method as recited in claim 1 wherein the processing step comprises subtracting a product of a most significant block x k multiplied by α k from the number X to yield the intermediate value.

Claim 9

A computer-implemented method as recited in claim 1 wherein the processing step comprises computing X mod α k to yield the intermediate value.

Claim 10

A computer-implemented method as recited in claim 1 wherein the processing step comprises adding to the intermediate value an amount equal to a product x k *U*α k-n-1 .

Claim 11

A computer-implemented method as recited in claim 1 wherein the processing step comprises one of the following: in an event that X≧0, subtracting an amount that is equal to a product x k *V*α k-n-1 from the intermediate value; and in an event that X<0, subtracting an amount that is equal to a product x k '*U*α k-n-1 , where x k '=α-x k , from the intermediate value.

Claim 12

In an electronic system involving transmission of data over a network between two computing units, a computer-implemented method comprising the following steps: sending data from one computing unit to another; and processing the data at one of the computing units using a modular reduction operation "X mod M," where X is a number with k+1 blocks written in base α, X=<x k x k-1 . . . x 1 x 0 >, and M is a modulus having n blocks, M=<m n-1 m n-2 . . . m 1 m 0 >, and n<k+1, said processing step comprising: a) computing a constant U=α n+1 mod M; b) storing the constant U in a constant register; c) establishing a value Y=<y k y k-1 . . . y 1 y 0 > that is equal to the number X so that y k =x k , y k-1 =x k-1 , . . . y 1 =x 1 , and y 0 =x 0 ; d) storing Y in an intermediate value register; e) initializing a count i=k in a count register; f) retrieving the constant U from the constant register, the value Y from the intermediate value register, and the count i from the count register; g) computing a partially reduced value Y R =Y mod α i +y i *U*α i-n-1 , the partially reduced value Y R being equivalent to Y modulo M; and h) storing the partially reduced value Y R in the intermediate value register to replace the value Y, whereby Y=Y R for any subsequent modular reduction.

Claim 13

In an electronic system involving transmission of data over a network between two computing units, a computer-implemented method comprising the following steps: sending data from one computing unit to another; and processing the data at one of the computing units using a modular reduction operation "X mod M," where X is a number with k+1 blocks written in base α, X=<x k x k-1 . . . x 1 x 0 >, and M is a modulus having n blocks, M=<m n-1 m n-2 . . . m 1 m 0 >, and n<k+1, said processing step comprising: a) computing a constant U=α n+1 mod M; b) storing the constant U in a constant register; c) establishing a value Y=<y k y k-1 . . . y 1 y 0 > that is equal to the number X so that y k =x k , y k-1 =x k-1 , . . . y 1 =x 1 , and y 0 =x 0 ; d) storing Y in an intermediate value register; e) initializing a count i=k in a count register; f) retrieving the constant U from the constant register, the value Y from the intermediate value register, and the count i from the count register; g) computing a partially reduced value Y R =Y mod α i +y i *U*α i-n-1 , the partially reduced value Y R being equivalent to Y modulo M; and h) storing the partially reduced value Y R in the intermediate value register to replace the value Y, whereby Y=Y R for any subsequent modular reduction.

Claim 14

A computer-implemented method as recited in claim 11 wherein in an event that the computing step (g) yields a partially reduced value of Y R ≧α i , the computing step (g) additionally comprises further reducing the partially reduced value Y R by replacing the partially reduced value Y R with an amount equal to Y R mod α i +U*α i-n-1 .

Claim 15

A computer-implemented method as recited in claim 11, wherein said processing step further comprises the following additional steps: i) decrementing the count i in the count register; and j) in an event that count i≧n+1, repeating steps (f)-(h).

Claim 16

In an electronic system involving transmission of data over a network between two computing units, a computer-implemented method comprising the following steps: sending data from one computing unit to another; and processing the data at one of the computing units using a modular reduction operation "X mod M," where X is a number with k+1 blocks written in base α, X=<x k x k-1 . . . x 1 x 0 >, and M is a modulus having n blocks, M=<m n-1 m n-2 . . . m 1 m 0 >, and n<k+1, said processing step comprising: a) computing a constant U=α n+1 mod M; b) storing the constant U in a first constant register; c) computing a constant V=M-U; d) storing the constant V in a second constant register; e) establishing a value Y=<y k y k-1 . . . y 1 y 0 > that is equal to the number X so that y k =x k , y k-1 =x k-1 , . . . y 1 =x 1 , and y 0 =x 0 ; f) storing Y in an intermediate value register; g) initializing a count i=k in a count register; h) determining whether Y≧0; i) in the event that the step (h) determination yields Y≧0, then performing steps of (1) retrieving the constant V from the second constant register, the value Y from the intermediate value register, and the count i from the count register, and (2) computing a partially reduced value Y R =Y mod α i -y i *V*α i-n-1 , the partially reduced value Y R being equivalent to the value Y modulo M; j) in the event that the step (h) determination yields Y<0, then performing steps of (1) retrieving the constant U from the first constant register, the value Y from the intermediate value register, and the count i from the count register, and (2) computing a partially reduced value Y R =Y mod α i -y i '*U*α i-n-1 where y i '=α-y i , the partially reduced value Y R being equivalent to Y modulo M; and k) storing the partially reduced value Y R in the intermediate value register to replace the value Y, whereby Y=Y R for any subsequent modular reduction.

Claim 17

In an electronic system involving transmission of data over a network between two computing units, a computer-implemented method comprising the following steps: sending data from one computing unit to another; and processing the data at one of the computing units using a modular reduction operation "X mod M," where X is a number with k+1 blocks written in base α, X=<x k x k-1 . . . x 1 x 0 >, and M is a modulus having n blocks, M=<m n-1 m n-2 . . . m 1 m 0 >, and n<k+1, said processing step comprising: a) computing a constant U=α n+1 mod M; b) storing the constant U in a first constant register; c) computing a constant V=M-U; d) storing the constant V in a second constant register; e) establishing a value Y=<y k y k-1 . . . y 1 y 0 > that is equal to the number X so that y k =x k , y k-1 =x k-1 , . . . y 1 =x 1 , and y 0 =x 0 ; f) storing Y in an intermediate value register; g) initializing a count i=k in a count register; h) determining whether Y≧0; i) in the event that the step (h) determination yields Y≧0, then performing steps of (1) retrieving the constant V from the second constant register, the value Y from the intermediate value register, and the count i from the count register, and (2) computing a partially reduced value Y R =Y mod α i -y i *V*α i-n-1 , the partially reduced value Y R being equivalent to the value Y modulo M; j) in the event that the step (h) determination yields Y<0, then performing steps of (1) retrieving the constant U from the first constant register, the value Y from the intermediate value register, and the count i from the count register, and (2) computing a partially reduced value Y R =Y mod α i -y i '*U*α i-n-1 where y i '=α-y i , the partially reduced value Y R being equivalent to Y modulo M; and k) storing the partially reduced value Y R in the intermediate value register to replace the value Y, whereby Y=Y R for any subsequent modular reduction.

Claim 18

A computer-implemented method as recited in claim 14, wherein the processing step further comprises the following additional steps: l) decrementing the count i in the count register; and m) in an event that count i≧n+1, repeating steps (h)-(k).

Claim 19

A computer-implemented method as recited in claim 15, wherein the processing step further comprises the following additional step: n) in an event that, subsequent to step (m), the partially reduced value Y R <0, computing Y R =Y R mod α n+1 -U.

Claim 20

A computer for performing at least partially a modular reduction operation "X mod M" where X is a number with k+1 blocks written in base α, X=<x k x k-1 . . . x 1 x 0 >, and M is a modulus having n blocks, M=<m n-1 m n-2 . . . m 1 m 0 >, and n<k+1, the computer comprising: a data processor; said data processor being programmed with computer-executable instructions, including: (a) computer-executable instructions to direct the data processor to precompute a constant U that is equal to α n+1 mod M; (b) computer-executable instructions to direct the data processor to reduce the number X by an integer multiple of α n+1 to yield an intermediate value that is less than the number X but greater than zero; and (c) computer-executable instructions to direct the data processor to compensate for reduction of the number X by adjusting the intermediate value by an amount that is one of (1) an integer multiple of the constant U or (2) an integer multiple of a constant V, where V=M-U, to yield an incrementally reduced value X R that is equivalent modulo M to the number X.

Claim 21

A computer for performing at least partially a modular reduction operation "X mod M" where X is a number with k+1 blocks written in base α, X=<x k x k-1 . . . x 1 x 0 >, and M is a modulus having n blocks, M=<m n-1 m n-2 . . . m 1 m 0 >, and n<k+1, the computer comprising: a data processor; said data processor being programmed with computer-executable instructions, including: (a) computer-executable instructions to direct the data processor to precompute a constant U that is equal to α n+1 mod M; (b) computer-executable instructions to direct the data processor to reduce the number X by an integer multiple of α n+1 to yield an intermediate value that is less than the number X but greater than zero; and (c) computer-executable instructions to direct the data processor to compensate for reduction of the number X by adjusting the intermediate value by an amount that is one of (1) an integer multiple of the constant U or (2) an integer multiple of a constant V, where V=M-U, to yield an incrementally reduced value X R that is equivalent modulo M to the number X.

Claim 22

A computer as recited in claim 17 wherein the data processor is further programmed with computer-executable institutions to direct the data processor to add the integer multiple of the constant U to the intermediate value.

Claim 23

A computer as recited in claim 17 wherein the data processor is further programmed with computer-executable instructions to direct the data processor to subtract the integer multiple of the constant V from the intermediate value.

Claim 24

A computer as recited in claim 17 wherein the data processor is further programmed with computer-executable instructions to direct the data processor to subtract the integer multiple of the constant U from the intermediate value.

Claim 25

A computer as recited in claim 17 wherein the data processor is further programmed with computer-executable instructions to direct the data processor to delete a most significant block x k from the number X to yield the intermediate value.

Claim 26

A computer as recited in claim 17 wherein the data processor is further programmed with computer-executable instructions to direct the data processor to subtract a product of a most significant block x k multiplied by α k from the number X to yield the intermediate value.

Claim 27

A computer as recited in claim 17 wherein the data processor is further programmed with computer-executable instructions to direct the data processor to compute X mod α k to yield the intermediate value.

Claim 28

A computer as recited in claim 17 wherein the data processor is further programmed with computer-executable instructions to direct the data processor to reduce the number X to an intermediate value that is equal to X mod α k .

Claim 29

A computer as recited in claim 17 wherein the data processor is further programmed with computer-executable instructions to direct the data processor to add to the intermediate value an amount that is equal to a product x k *U*α k-n-1 .

Claim 30

A computer as recited in claim 17 wherein the data processor is further programmed with computer-executable instructions to direct the data processor to: in an event that X≧0, subtract an amount that is equal to a product x k *V*α k-n-1 from the intermediate value; and in an event that X<0, subtract an amount that is equal to a product x k '*U*α k-n-1 where x k '=α-x k , from the intermediate value.

Claim 31

A computer for performing at least partially a modular reduction operation "X mod M" where X is a number with k+1 blocks written in base α, X=<x k x k-1 . . . x 1 x 0 >, and M is a modulus having n blocks, M=<m n-1 m n-2 . . . m 1 m 0 >, and n<k+1, the computer comprising: a data processor; said data processor being programmed with computer-executable instructions, including: (a) computer-executable instructions to direct the data processor to precompute a constant U=α n+1 mod M; and (b) computer-executable instructions to direct the data processor to compute an incrementally reduced value X R =X mod α k +x k *U*α k-n-1 where the incrementally reduced value X R is equivalent to X modulo M.

Claim 32

A computer for performing at least partially a modular reduction operation "X mod M" where X is a number with k+1 blocks written in base α, X=<x k x k-1 . . . x 1 x 0 >, and M is a modulus having n blocks, M=<m n-1 m n-2 . . . m 1 m 0 >, and n<k+1, the computer comprising: a data processor; said data processor being programmed with computer-executable instructions, including: (a) computer-executable instructions to direct the data processor to precompute a constant U=α n+1 mod M; and (b) computer-executable instructions to direct the data processor to compute an incrementally reduced value X R =X mod α k +x k *U*α k-n-1 where the incrementally reduced value X R is equivalent to X modulo M.

Claim 33

A computer as recited in claim 27 wherein the computer-executable instructions of part (b) direct the data processor to iteratively compute the reduced value X R for iterations i=k down to n+1.

Claim 34

A computer as recited in claim 27 wherein the computer-executable instructions of part (b) direct the data processor to iteratively compute the reduced value X R for iterations i=k down to i>n+1.

Claim 35

A computer for performing at least partially a modular reduction operation "X mod M" where X is a number with k+1 blocks written in base α, X=<x k x k-1 . . . x 1 x 0 >, and M is a modulus having n blocks, M=<m n-1 m n-2 . . . m 1 m 0 >, and n<k+1, the computer comprising: a data processor; said data processor being programmed with computer-executable instructions, including: (a) computer-executable instructions to direct the data processor to precompute a constant U=α n+1 mod M; (b) computer-executable instructions to direct the data processor to precompute a constant V=M-U; (c) computer-executable instructions to direct the data processor to determine whether X≧0; (d) in the event that X≧0, computer-executable instructions to direct the data processor to compute X R =X mod α k -x k *V*α k-n-1 ; and (e) in the event that X<0, computer-executable instructions to direct the data processor to compute X R =X mod α k -x k '*U*α k-n-1 where x k '=α-x k .

Claim 36

A computer for performing at least partially a modular reduction operation "X mod M" where X is a number with k+1 blocks written in base α, X=<x k x k-1 . . . x 1 x 0 >, and M is a modulus having n blocks, M=<m n-1 m n-2 . . . m 1 m 0 >, and n<k+1, the computer comprising: a data processor; said data processor being programmed with computer-executable instructions, including: (a) computer-executable instructions to direct the data processor to precompute a constant U=α n+1 mod M; (b) computer-executable instructions to direct the data processor to precompute a constant V=M-U; (c) computer-executable instructions to direct the data processor to determine whether X≧0; (d) in the event that X≧0, computer-executable instructions to direct the data processor to compute X R =X mod α k -x k *V*α k-n-1 ; and (e) in the event that X<0, computer-executable instructions to direct the data processor to compute X R =X mod α k -x k '*U*α k-n-1 where x k '=α-x k .

Claim 37

A computer as recited in claim 30 wherein the computer-executable instructions of parts (c)-(e) direct the data processor to iteratively compute the reduced value X R for iterations i=k down to n+1.

Claim 38

A computer as recited in claim 30 wherein the computer-executable instructions of parts (c)-(e) direct the data processor to iteratively compute the reduced value X R for iterations i=k down to i>n+1.

Claim 39

A math processing unit for performing at least partially a cryptographic function using a modular reduction operation "X mod M" where X is a number with k+1 blocks written in base α, X=<x k x k-1 . . . x 1 x 0 >, and M is a modulus having n blocks, M=<m n-1 m n-2 . . . m 1 m 0 >, and n<k+1, the math processing unit comprising: a first register to store the number X; a second register to store a precomputed constant U, where U=α n+1 mod M; and means coupled to receive the number X from the first register and to receive the precomputed constant U from the second register for computing a cryptographic function by, in part, modularly reducing the number X to produce an incrementally reduced value X R that is equal to X mod α k +x k *U*α k-n-1 .

Claim 40

A math processing unit for performing at least partially a cryptographic function using a modular reduction operation "X mod M" where X is a number with k+1 blocks written in base α, X=<x k x k-1 . . . x 1 x 0 >, and M is a modulus having n blocks, M=<m n-1 m n-2 . . . m 1 m 0 >, and n<k+1, the math processing unit comprising: a first register to store the number X; a second register to store a precomputed constant U, where U=α n+1 mod M; and means coupled to receive the number X from the first register and to receive the precomputed constant U from the second register for computing a cryptographic function by, in part, modularly reducing the number X to produce an incrementally reduced value X R that is equal to X mod α k +x k *U*α k-n-1 .

Claim 41

A math processing unit as recited in claim 33 wherein said means is configured for calculating an incrementally reduced value X R by (1) deleting a most significant block x k from the number X to provide an intermediate value and (2) adding a product x k *U*α k-n-1 to the intermediate value.

Claim 42

A math processing unit as recited in claim 33 wherein the means is configured for calculating an incrementally reduced value X R by (1) subtracting a product x k *α k from the number X and (2) adding a product x k *U*α k-n-1 to the result of the subtraction.

Claim 43

A math processing unit as recited in claim 33 wherein the means is configured for calculating an incrementally reduced value X R by (1) subtracting X mod α k to provide an intermediate value, and (2) adding a product x k *U*α k-n-1 to the intermediate value.

Claim 44

A microprocessor comprising a math processing unit as recited in claim 33.

Claim 45

A smart card comprising a math processing unit as recited in claim 33.

Claim 46

A math processing unit for performing at least partially a cryptographic function using a modular reduction operation "X mod M" where X is a number with k+1 blocks written in base α, X=<x k x k-1 . . . x 1 x 0 >, and M is a modulus having n blocks, M=<m n-1 m n-2 . . . m 1 m 0 >, and n <k+1, the math processing unit comprising: a first register to store the number X; a second register to store a precomputed constant U, where U=α n+1 mod M; a third register to hold a precomputed constant V, where V=M-U; and means coupled to receive the number X from the first register, to receive the precomputed constant U from the second register, and to receive the precomputed constant V from the third register, for computing a cryptographic function by, in part, modularly reducing the number X to an incrementally reduced value X R that is equal to either (1) X mod α k -x k *V*α k-n-1 in the event that X≧0, or (2) X mod α k -x k '*U*α k-n-1 , where x k '=α-k k , in the event that X<0.

Claim 47

A math processing unit for performing at least partially a cryptographic function using a modular reduction operation "X mod M" where X is a number with k+1 blocks written in base α, X=<x k x k-1 . . . x 1 x 0 >, and M is a modulus having n blocks, M=<m n-1 m n-2 . . . m 1 m 0 >, and n <k+1, the math processing unit comprising: a first register to store the number X; a second register to store a precomputed constant U, where U=α n+1 mod M; a third register to hold a precomputed constant V, where V=M-U; and means coupled to receive the number X from the first register, to receive the precomputed constant U from the second register, and to receive the precomputed constant V from the third register, for computing a cryptographic function by, in part, modularly reducing the number X to an incrementally reduced value X R that is equal to either (1) X mod α k -x k *V*α k-n-1 in the event that X≧0, or (2) X mod α k -x k '*U*α k-n-1 , where x k '=α-k k , in the event that X<0.

Claim 48

A math processing unit as recited in claim 39 wherein the means is configured for calculating an incrementally reduced value X R by (1) deleting a most significant block x k from the number X to provide an intermediate value, and (2) subtracting from the intermediate value either (a) a product x k *V*α k-n-1 in the event that X≧0, or (b) a product x k '*U*α k-n-1 in the event that X<0.

Claim 49

A math processing unit as recited in claim 39 wherein the means is configured for calculating an incrementally reduced value X R by (1) subtracting a product x k *α k from the number X, and (2) further subtracting either (a) a product x k *V*α k-n-1 in the event that X≧0, or (b) a product x k '*U*α k-n-1 in the event that X<0.

Claim 50

A math processing unit as recited in claim 39 wherein the means is configured for calculating an incrementally reduced value X R by (1) subtracting X mod α k to provide an intermediate value, and (2) subtracting from the intermediate value either (a) a product x k *V*α k-n-1 in the event that X≧0, or (b) a product x k '*U*α k-n-1 in the event that X<0.

Claim 51

A microprocessor comprising a math processing unit as recited in claim 39.

Claim 52

A smart card comprising a math processing unit as recited in claim 39.

Claim 53

A computer-readable memory used to direct a computer to perform at least partially a modular reduction operation "X mod M" where X is a number with k+1 blocks written in base α, X=<x k x k-1 . . . x 1 x 0 >, and M is a modulus having n blocks, M=<m n-1 m n-2 . . . m 1 m 0 >, and n<k+1, the computer-readable memory having computer-executable instructions for directing the computer, including: (a) computer-executable instructions to direct the computer to precompute a constant U that is equal to α n+1 mod M; (b) computer-executable instructions to direct the computer to reduce the number X by an integer multiple of α n+1 to yield an intermediate value that is less than the number X but greater than zero; and (c) computer-executable instructions to direct the computer to compensate for reduction of the number X by adjusting the intermediate value by an amount that is one of (1) an integer multiple of the constant U or (2) an integer multiple of a constant V, where V=M-U, to yield an incrementally reduced value X R that is equivalent modulo M to the number X.

Claim 54

A computer-readable memory used to direct a computer to perform at least partially a modular reduction operation "X mod M" where X is a number with k+1 blocks written in base α, X=<x k x k-1 . . . x 1 x 0 >, and M is a modulus having n blocks, M=<m n-1 m n-2 . . . m 1 m 0 >, and n<k+1, the computer-readable memory having computer-executable instructions for directing the computer, including: (a) computer-executable instructions to direct the computer to precompute a constant U that is equal to α n+1 mod M; (b) computer-executable instructions to direct the computer to reduce the number X by an integer multiple of α n+1 to yield an intermediate value that is less than the number X but greater than zero; and (c) computer-executable instructions to direct the computer to compensate for reduction of the number X by adjusting the intermediate value by an amount that is one of (1) an integer multiple of the constant U or (2) an integer multiple of a constant V, where V=M-U, to yield an incrementally reduced value X R that is equivalent modulo M to the number X.

Claim 55

A computer-readable memory as recited in claim 45, wherein the computer-executable instructions of part (b) direct the computer to reduce the number X to an intermediate value that is equal to X mod α k .

Claim 56

A computer-readable memory as recited in claim 16, wherein the computer-executable instructions of part (c) direct the computer to add to the intermediate value an amount that is equal to a product x k *U*α k-n-1 .

Claim 57

A computer-readable memory as recited in claim 16, wherein the computer-executable in instruction of part (c) direct the computer to: in an event that X≧0, subtract an amount that is equal to a product x k *V*α k-n-1 from the intermediate value; and in an event that X≧0, subtract an amount that is equal to a product x k '*U*α k-n-1 where x k '=α-x k , from the intermediate value.

Claim 58

A smart card comprising a computer-readable memory as recited in claim 45.

Claim 59

In a cryptographic system, a computer-implemented method comprising the following steps: processing a message according to a cryptographic function; and said processing step including to at least partially computing a modular reduction operation "X mod M" as part of the cryptographic function, where X is a number with k+1 blocks written in base α, X=<x k x k-1 . . . x 1 x 0 >, and M is a modulus having n blocks, M=<m n-1 m n-2 . . . m 1 m 0 >, and n<k+1, said computing comprising the following steps: defining a constant U that is equal to α n+1 mod M; reducing the number X by an integer multiple of α n+1 to yield an intermediate value that is less than the number X but greater than zero; and compensating for reduction of the number X by adjusting the intermediate value by an amount that is one of (1) an integer multiple of the constant U or (2) an integer multiple of a constant V, where V=M-U, to yield an incrementally reduced value X R that is equivalent modulo M to the number X.

Claim 60

In a cryptographic system, a computer-implemented method comprising the following steps: processing a message according to a cryptographic function; and said processing step including to at least partially computing a modular reduction operation "X mod M" as part of the cryptographic function, where X is a number with k+1 blocks written in base α, X=<x k x k-1 . . . x 1 x 0 >, and M is a modulus having n blocks, M=<m n-1 m n-2 . . . m 1 m 0 >, and n<k+1, said computing comprising the following steps: defining a constant U that is equal to α n+1 mod M; reducing the number X by an integer multiple of α n+1 to yield an intermediate value that is less than the number X but greater than zero; and compensating for reduction of the number X by adjusting the intermediate value by an amount that is one of (1) an integer multiple of the constant U or (2) an integer multiple of a constant V, where V=M-U, to yield an incrementally reduced value X R that is equivalent modulo M to the number X.