# Information Security and Cryptography Research Group

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

### Ueli Maurer

Cryptography and Coding '92, Oxford University Press, pp. 173–191, Mar 1992.

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 $p_1(n)$ 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}, \dots, 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}, \dots, 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,\dots$ 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} p_1(n)$ 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.

## BibTeX Citation

@inproceedings{Maurer92e,
author       = {Ueli Maurer},
title        = {Some Number-theoretic Conjectures and Their Relation to the Generation of Cryptographic Primes},
editor       = {C. Mitchell},
booktitle    = {Cryptography and Coding~'92},
pages        = 173--191,
year         = 1992,
month        = 3,
publisher    = {Oxford University Press},
}