Publication

Efficient generation of prime numbers

Serge Vaudenay
2000
Conference Papers

Abstract

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(n4) or O(n4/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

Official source

https://infoscience.epfl.ch/entities/publication/3059d680-dcc8-4c3f-98c5-04dc82790547

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Serge Vaudenay
2000
Conference Papers

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/3059d680-dcc8-4c3f-98c5-04dc82790547

About this result

Related concepts (32)

Safe and Sophie Germain primes

In number theory, a prime number p is a Sophie Germain prime if 2p + 1 is also prime. The number 2p + 1 associated with a Sophie Germain prime is called a safe prime. For example, 11 is a Sophie Germain prime and 2 × 11 + 1 = 23 is its associated safe prime. Sophie Germain primes are named after French mathematician Sophie Germain, who used them in her investigations of Fermat's Last Theorem. One attempt by Germain to prove Fermat’s Last Theorem was to let p be a prime number of the form 8k + 7 and to let n = p – 1.

Prime number

A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 4 is composite because it is a product (2 × 2) in which both numbers are smaller than 4.

Formula for primes

In number theory, a formula for primes is a formula generating the prime numbers, exactly and without exception. No such formula which is efficiently computable is known. A number of constraints are known, showing what such a "formula" can and cannot be. A simple formula is for positive integer , where is the floor function, which rounds down to the nearest integer. By Wilson's theorem, is prime if and only if . Thus, when is prime, the first factor in the product becomes one, and the formula produces the prime number .

Related publications (7)

Efficient generation of prime numbers

Chat with Graph Search

K-Waay: Fast and Deniable Post-Quantum X3DH without Ring Signatures

Clever Arbiters Versus Malicious Adversaries

Multi-terminal Secrecy in a Linear Non-coherent Packetized Networks