A method for generating a prime number and using it in a cryptographic application, comprising the steps of: a) determining, via a processing system comprising at least one hardware processor, a test primality circuit and a memory circuit, at least one binary base B with a small size b = log 2 bits and for each determined base B, at least one small prime p i such that B mod p i = 1, with i an integer, b) selecting, via said hardware processor, a prime candidate Y P, c) decomposing, via said hardware processor, the selected prime candidate Y P in a base B selected among said determined binary bases: Y P = ∑ y j B i, d) computing, via said hardware processor, a residue y PB from the candidate Y P for said selected base B such that y PB = ∑ y j, e) testing, via said test primality circuit, if said computed residue y PB is divisible by one small prime pi selected among said determined small primes for said selected base B, f) while said computed residue y PB is not divisible by said selected small prime, iteratively repeating, via said test primality circuit, above step e) until tests performed at step e) prove that said computed residue y PB is not divisible by any of said determined small primes for said selected base B, g) when tests performed at step e) have proven that said computed residue y PB 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 determined bases B, tests performed at step e) have proven that said residue y PB computed for a determined base is not divisible by any of said determined small primes for said determined base B, executing, via said test primality circuit, a known rigorous probable primality test on said candidate Y P, and when the known rigorous probable primality test is a success, storing said prime candidate Y P in said memory circuit and using, via a cryptographic processor, said stored prime candidate Y P in said cryptographic application. a) determining, via a processing system comprising at least one hardware processor, a test primality circuit and a memory circuit, at least one binary base B with a small size b = log 2 bits and for each determined base B, at least one small prime p i such that B mod p i = 1, with i an integer, b) selecting, via said hardware processor, a prime candidate Y P, c) decomposing, via said hardware processor, the selected prime candidate Y P in a base B selected among said determined binary bases: Y P = ∑ y j B i, d) computing, via said hardware processor, a residue y PB from the candidate Y P for said selected base B such that y PB = ∑ y j, e) testing, via said test primality circuit, if said computed residue y PB is divisible by one small prime pi selected among said determined small primes for said selected base B, f) while said computed residue y PB is not divisible by said selected small prime, iteratively repeating, via said test primality circuit, above step e) until tests performed at step e) prove that said computed residue y PB is not divisible by any of said determined small primes for said selected base B, g) when tests performed at step e) have proven that said computed residue y PB 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 determined bases B, tests performed at step e) have proven that said residue y PB computed for a determined base is not divisible by any of said determined small primes for said determined base B, executing, via said test primality circuit, a known rigorous probable primality test on said candidate Y P, and when the known rigorous probable primality test is a success, storing said prime candidate Y P in said memory circuit and using, via a cryptographic processor, said stored prime candidate Y P in said cryptographic application.