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},
}

Files and Links