# 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.