Method for generating a prime number by testing co-primalty between a prime candidate and a predetermined prime number in a binary base
US11281433B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Feb 9, 2018 |
| Grant date | Mar 22, 2022 |
| Priority date | — |
| Expiry date | Apr 2, 2038 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F2207/7204
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
The present invention relates to a method for generating a prime number and using it in a cryptographic application, comprising the steps of: a) determining at least one binary base B with a small size b=log2(B) bits and for each determined base B at least one small prime pi such that B mod pi=1, with i an integer, b) selecting a prime candidate YP, c) decomposing the selected prime candidate YP in a base B selected among said determined binary bases : YP=ΣyjBid) computing a residue yPB from the candidate YP for said selected base such that yPB=Σyje) testing if said computed residue yPB is divisible by one small prime pi selected among said determined small primes for said selected base B, f) while said computed residue yPB is not divisible by said selected small prime, iteratively repeating above step e) until tests performed at step e) prove that said computed residue yPB is not divisible by any of said determined small primes for said selected base B, g) when said computed residue yPB is not divisible by any of said determined small primes for said selected base B, iteratively repeating steps c) to f) for each base B among said determined binary bases, h) when, for all determine…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.