Accelerated prime sieving using architecture-optimized partial prime product table
US7552164B1 · kind B1 · utility
1Cited by
1References
1Claims
0Family size
Assignee
Inventors
Key dates
| Filing date | Apr 24, 2008 |
| Grant date | Jun 23, 2009 |
| Priority date | — |
| Expiry date | Apr 24, 2028 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L2209/127
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
This embodiment teaches a variation of GCD-based sieving, building tables of prime products, but intentionally restricting the size of table entries to fit within a single machine word. This combination allows one to mix advantages of the two most popular sieves, while retaining the simple and straightforward structure of the simpler one. Divisor length restriction can provide significant savings in the number of long divisions, but may be implemented with only two very specific primitives. The two primitives offer better optimization capabilities than a fully generic multiword arithmetic library.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.