Efficient generation of prime numbers

The generation of prime numbers underlies the use of most public-key schemes, essentially as a major primitive needed for the creation of key pairs or as a computation stage appearing during various cryptographic setups. Surprisingly, despite decades of intense mathematical studies on primality testing and an observed progressive intensification of cryptographic usages, prime number generation algorithms remain scarcely investigated and most real-life implementations are of rather poor performance. Common generators typically output an n-bit prime in heuristic average complexity O(n<sup>4</sup>) or O(n<sup>4</sup>/logn) and these figures, according to experience, seem impossible to improve significantly: this paper rather shows a simple way to substantially reduce the value of hidden constants to provide much more efficient prime generation algorithms. We apply our techniques to various contexts (DSA primes, safe primes, ANSI X9.31-compliant primes, strong primes, etc.) and show how to build fast implementations on appropriately equipped smart-cards, thus allowing on-board key generation


Published in:
Cryptographic Hardware and Embedded Systems - CHES 2000, Second International Workshop, 1965, 340-354
Presented at:
Cryptographic Hardware and Embedded Systems - CHES 2000, Second International Workshop, Worcester, MA, USA, August 17-18, 2000
Year:
2000
Other identifiers:
Laboratories:




 Record created 2007-01-18, last modified 2018-03-17

n/a:
Download fulltext
PS

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)