Prime number generation method, prime number generation apparatus, and cryptographic system
US7043018B1 · kind B1 · utility
Assignees
Inventors
Key dates
| Filing date | Nov 24, 1999 |
| Grant date | May 9, 2006 |
| Priority date | — |
| Expiry date | Nov 24, 2019 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L2209/08
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
A prime number generation method for efficiently generating prime numbers that are highly resistant to the P−1 and P+1 methods. These prime numbers are used in a cryptosystem. Prime candidates are first generated, and the generated prime candidates are subjected to prime number judgment by either a probabilistic primality testing method or a deterministic primality testing method. A prime candidate P′ is generated using odd random numbers, a judgment is made as to whether or not that prime candidate P′ satisfies the expression P′≡0, ±1 (mod pi) (where 3≦i≦n) for prime numbers from p3 to pn (where pn is the n'th prime). When that expression is satisfied, that prime candidate P′ is excluded. Only those prime candidates P′ that do not satisfy that condition are subjected to the prime number judgment.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.