Performing constant modulo arithmetic
First Claim
1. A binary logic circuit for determining y=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 reduce x to a sum of a first m-bit integer β and
a second m-bit integer γ
; and
fixed function addition logic configured tocalculate 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 a 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 a string of bit values represented by γ
, andthe binary value 1; and
output the result as corresponding to the value y.
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.
4 Citations
20 Claims
-
1. A binary logic circuit for determining y=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 reduce x to a sum of a first m-bit integer β and
a second m-bit integer γ
; andfixed function 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 a 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 a string of bit values represented by γ
, andthe binary value 1; and output the result as corresponding to the value y. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17)
- 1), where x is an n-bit integer, y is an m-bit integer, and n>
-
18. A method for determining y=x mod(2m−
- 1) in a binary logic circuit comprising fixed function reduction logic and fixed function addition logic, where x is an n-bit integer, y is an m-bit integer, and n≥
m, the method comprising;reducing, at the fixed function reduction logic, x to a sum of a first m-bit integer β and
a second m-bit integer γ
;at least partially calculating, at the fixed function addition logic, a result for the sum of; 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 γ
; andthe binary value 1; and using the m least significant bits of the result right-shifted by m as γ
.- View Dependent Claims (19)
- 1) in a binary logic circuit comprising fixed function reduction logic and fixed function addition logic, where x is an n-bit integer, y is an m-bit integer, and n≥
-
20. 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 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 reduce x to a sum of a first m-bit integer β and
a second m-bit integer γ
; andfixed function 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 γ
; andthe binary value 1.
- 1), where x is an n-bit integer, y is an m-bit integer, and n>
Specification