Efficient computation of the modulo operation based on divisor (2n-1)
US7849125B2 · kind B2 · utility
Assignee
Inventor
Key dates
| Filing date | Jul 7, 2006 |
| Grant date | Dec 7, 2010 |
| Priority date | — |
| Expiry date | Oct 6, 2029 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F7/727
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A system and method for computing A mod (2n−1), where A is an m bit quantity, where n is a positive integer, where m is greater than or equal to n. The quantity A may be partitioned into a plurality of sections, each being at most n bits long. The value A mod (2n−1) may be computed by adding the sections in mod(2n−1) fashion. This addition of the sections of A may be performed in a single clock cycle using an adder tree, or, sequentially in multiple clock cycles using a two-input adder circuit provided the output of the adder circuit is coupled to one of the two inputs. The computation A mod (2n−1) may be performed as a part of an interleaving/deinterleaving operation, or, as part of an encryption/decryption operation.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.