HP Labs Technical Reports
Click here for full text:
Distribution of the Prime Factors of p+d
O'Connell, Neil; Womack, Thomas
HPLBRIMS9726
Keyword(s): PoissonDirichlet; 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 nonincreasing 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 PoissonDirichlet distribution (with parameter 1). We prove the following: if P is a randomly chosen prime less than n, and d is a fixed nonzero 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
