HP Labs Technical Reports

Distribution of the Prime Factors of p+d

O'Connell, Neil; Womack, Thomas

HPL-BRIMS-97-26

Keyword(s): Poisson-Dirichlet; GEM; random partition; prime factors; p+1

Abstract: For each positive integer m, there is a natural representation for the factorisation of m as a partition of the unit interval. The elements of this partition can be arranged in non-increasing order, and represented as a point V (m) on the infinite- dimensional simplex. In 1972, Billingsley proved that, if N is a randomly chosen positive integer less than n, then for large n, the law of V (N) can be approximated by the Poisson-Dirichlet distribution (with parameter 1). We prove the following: if P is a randomly chosen prime less than n, and d is a fixed non-zero integer, then for large n the distribution of V (P + d )can be approximated by the same Poisson- Dirichlet distribution. We will discuss some implications of this result in cryptography.

8 Pages

Back to Index