ETH Zürich » Computer Science » Theory » Cryptography

Publications: Abstract

Some Number-theoretic Conjectures and Their Relation to the Generation of Cryptographic Primes

Ueli Maurer

The purpose of this paper is to justify the claim that a method for generating primes presented at EUROCRYPT'89 generates primes with virtually uniform distribution. Using convincing heuristic arguments, the conditional probability distributions of the size of the largest prime factor $\pon$ of a number $n$ on the order of $N$ is derived, given that $n$ satisfies one of the conditions $2n+1$ is prime, $2an+1$ is prime for a given $a$, or the $d$ integers $u_{1}\pp u_{d}$, where $u_{1}=2a_{1}n+1$ and $u_{t}=2a_{t}u_{t-1}+1$ for $2\leq t\leq d$, are all primes for a given list of integers $a_{1}\pp a_{d}$. In particular, the conditional probabilities that $n$ is itself a prime, or is of the form ``$k$ times a prime" for $k=2,3\pp$ is treated for the above conditions. It is shown that although for all $k$ these probabilities strongly depend on the condition placed on $n$, the probability distribution of the relative size $\sigma_{1}(n)=\log_{N}\pon$ of the largest prime factor of $n$ is virtually independent of any of these conditions. Some number-theoretic conjectures related to this analysis are stated. Furthermore, the probability distribution of the size of the smaller prime factor of an RSA-modulus of a certain size is investigated.