Performing constant modulo arithmetic
First Claim
1. A binary logic circuit for reducing x to a sum of a first m-bit integer) β
- and a second m-bit integer γ
, for use in determining y=x mod(2m−
1), where x is an n-bit integer, y is an m-bit integer, and n>
m, the binary logic circuit comprising fixed function reduction logic configured to;
interpret x as a sum of m-bit rows x′
, each row representing m consecutive bits of x such that each bit of x contributes to only one row and all of the bits of x are allocated to a row;
reduce the sum of such m-bit rows x′
in a series of reduction steps so as to generate the sum of the first m-bit integer β and
the second m-bit integer γ
.
1 Assignment
0 Petitions
Accused Products
Abstract
A binary logic circuit for determining y=x mod(2m−1), where x is an n-bit integer, y is an m-bit integer, and n>m, includes reduction logic configured to reduce x to a sum of a first m-bit integer β and a second m-bit integer γ; and addition logic configured to calculate an addition output represented by the m least significant bits of the following sum right-shifted by m: a first binary value of length 2m, the m most significant bits and the m least significant bits each being the string of bit values represented by β; a second binary value of length 2m, the m most significant bits and the m least significant bits each being the string of bit values represented by γ; and the binary value 1.
-
Citations
14 Claims
-
1. A binary logic circuit for reducing x to a sum of a first m-bit integer) β
- and a second m-bit integer γ
, for use in determining y=x mod(2m−
1), where x is an n-bit integer, y is an m-bit integer, and n>
m, the binary logic circuit comprising fixed function reduction logic configured to;interpret x as a sum of m-bit rows x′
, each row representing m consecutive bits of x such that each bit of x contributes to only one row and all of the bits of x are allocated to a row;reduce the sum of such m-bit rows x′
in a series of reduction steps so as to generate the sum of the first m-bit integer β and
the second m-bit integer γ
. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
- and a second m-bit integer γ
-
13. A method of reducing x to a sum of a first m-bit integer β
- and a second m-bit integer γ
for use in determining y=x mod(2m−
1) in a binary logic circuit comprising fixed function reduction logic, where x is an n-bit integer, y is an m-bit integer, and n>
m, the method comprising;interpreting, by the fixed function reduction logic, x as a sum of m-bit rows x′
, each row representing m consecutive bits from x such that each bit of x contributes to only one row and all of the bits of x are allocated to a row; andreducing, by the fixed function reduction logic, the sum of m-bit rows, x′
, in a series of reduction steps so as to generate the sum of the first m-bit integer β and
the second m-bit integer γ
.
- and a second m-bit integer γ
-
14. A non-transitory computer readable storage medium having stored thereon computer readable instructions that, when processed at a computer system for generating a manifestation of an integrated circuit, cause the computer system to generate a manifestation of a binary logic circuit for reducing x to a sum of a first m-bit integer β
- and a second m-bit integer γ
for use in determining y=x mod(2m−
1), where x is an n-bit integer, y is an m-bit integer, and n>
m, the binary logic circuit comprising fixed function reduction logic configured to;interpret x as a sum of m-bit rows x′
, each row representing m consecutive bits of x such that each bit of x contributes to only one row and all of the bits of x are allocated to a row;reduce the sum of such m-bit rows x′
in a series of reduction steps so as to generate the sum of the first m-bit integer β and
the second m-bit integer γ
.
- and a second m-bit integer γ
Specification