Method for generating a prime number by testing co-primalty between a prime candidate and a predetermined prime number in a binary base

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=log(B) bits and for each determined base B at least one small prime psuch that B mod p=1, with i an integer, b) selecting a prime candidate Y, c) decomposing the selected prime candidate Yin a base B selected among said determined binary bases : Y=ΣyBd) computing a residue yfrom the candidate Yfor said selected base such that y=Σe) testing if said computed residue yis divisible by one small prime pi selected among said determined small primes for said selected base B, f) while said computed residue yis not divisible by said selected small prime, iteratively repeating above step e) until tests performed at step e) prove that said computed residue yis not divisible by any of said determined small primes for said selected base B, g) when said computed residue yis 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 determined bases B, said residue ycomputed for a determined base is not divisible by any of said determined small primes for said determined base B, executing a known rigorous probable primality test on said candidate Y, and when the known rigorous probable primality test is a success, storing said prime candidate Yand using said stored prime candidate Yin said cryptographic application.