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