A Study of Prime factors among Integers

Victor Youdom Kemmoe

Abstract

We study prime factors within a sample of integers and provide some probabilistic

arguments about their repetition.

1 Introduction

Primefactorsamongintegersplayanimportantroleinnumbertheoryandcryptography. Forinstance,

innumbertheory,theChineseRemainderTheoremtellsusthatforanintegern,wecandecompose

theringZ/nZintothedirectsumoftheringsZ/pk 11Z,...,Z/pk nnZ,wherep iisaprimefactorofn

andpki isthelargestpowerofp thatdividesn. Incryptography,thesecurityofseveralschemessuch

i i

astheRSAencryptionisbasedontheintractabilityoffactoringanintegern. However,itisknown

√ √

thatncanbefactoredintimeexp(( 2+O(1) logploglogp)onaclassicalcomputer,wherep

representsthesmallestprimefactorofn[LLMP93],andthisshowsagaintheimportanceofhaving

aninsightontheprimefactorsofaninteger. Beyondfactoring,KemmoeandLysyanskaya[KL24]

showedhowusingintegersthatarenotsmooth(integersthatonlyhavesmallprimefactors)canhelp

improvetherunningtimeofsomecryptographicschemes,suchascryptographicaccumulators[CL02]

andverifiabledelayfunctions[Wes20],thatrequiretheuseofprimenumbers. Themainideawasto

replacethoseprimenumberswithnon-smoothintegers.

Inthisarticle,weattempttoprovideananalysisofprimefactorsthatappearwithinasetofintegers

sampleduniformlyatrandom.

2 Preliminaries

Notations WeuseN∗torepresentN andforanya∈N∗,letaN∗ ={n∈N∗ :n≡0moda},

>0

[a] = {1,...,a}, andP+(a) todenotes thelargest primefactor ofa. Given twofunctions f,g :

R → R, we use f(x) ∼ g(x) (x → x ) to denote that lim f(x)/g(x) = 1. For a finite

0 x→x0

setS,weuseU(S)todenotetheuniformdistributionoverS and#S todenotethecardinalityof

S. Let Odds(a,b) = {a ≤ n ≤ b : n ≡ 1mod2}. We use Primes to denotethe set ofpositive

primeintegers. Asperconvention,weuseptodenoteaprimeinteger. Afunctionh:R→[0,1]is

negligibleifh(x)∈o(x−c)forallc∈N.

Lemma1. Letp∈N∗beaprimeandleta ,a ∈N∗suchthatp|a a . Then,p|a orp|a .

1 2 1 2 1 2

Proof. Supposep ∤ a . Thengcd(a ,p) = 1,andbyapplyingtheExtendedEuclideanalgorithm,

1 1

wecanfindr,s ∈ N∗ suchthata r+ps = 1. Thisimpliesthata br+bps = b. Sincep | a b,it

1 1 1

followsthatthereexistk ∈N∗suchthata b=kp. Thereforep(kr+bs)=b. Hencep|b.

1

Corollary1. Letp ∈ N∗ beaprimeandleta ,...,a ∈ N∗ suchthatp | (cid:81)n a . Then,there

1 n i=1 i

existi∈[n]suchthatp|a .

i

37thConferenceonNeuralInformationProcessingSystems(NeurIPS2023).

Proof. AproofcaneasilybederivedbyiterativelyapplyingthestrategyusedtoproveLemma1

Lemma2(Euler’sproduct). Letζ : C → CbetheRiemannZetafunction. Then,foranys ∈ C,

suchthatℜ(s)>1,i.e.,therealpartofsisgreaterthan1,

(cid:89)

(cid:18)

1

(cid:19)−1

ζ(s)= 1−

ps

p∈Primes

The proof of the above lemma is beyond the scope of this article. However, the read can find a

detailedproofin([Ove15],Chap3)or([Ten15],Chap1).

Lemma3(Mertens’sformula). Foranyx≥2,

(cid:89) (cid:18) 1(cid:19) e−γ (cid:18) (cid:18) 1 (cid:19)(cid:19)

1− = 1+O

p logx logx

p≤x,p∈Primes

whereγ isEuler’sconstant.

Theproofoftheabovelemmaisbeyondthescopeofthisarticle. However,wepointthereaderto

([Ten15],Chap1)or([Kou20],Chap3)foradetailedproof.

2.1 Probabilitiesovernaturalnumbers

Inthissection,weprovideabackgroundonthenotionofasymptoticdensity. ItisusedinAnalytical

NumberTheorytoapproximatethenotionofaprobabilitymeasureovertheintegers.

First,weintroduceatheoremextractedfromTenenbaum[Ten15]thatshowsthatwecannotdefine

aprobabilitymeasureoverN∗thatsatisfiestheconditionthatanintegeradividesanotherinteger

sampleduniformlyatrandomwithprobability1/a,whichheuristicallyholdstrue.

Theorem1(([Ten15],Chap3)). Foranya∈N∗,theredoesnotexistaprobabilitymeasureµover

N∗suchthatµ[aN∗]=1/a.

Proof. Assume for contradiction sake that there exist a probability measure µ that satisfies the

proposedcondition. Foranya,b∈N∗,ifgcd(a,b)=1,thenaN∗∩bN∗ =abN∗,andthisimplies

that under the probability measure µ, the events aN∗ and bN∗ are independent. In addition, it

impliesthattheeventsN∗\aN∗andN∗\bN∗,whicharecomplementsoftheeventaN∗andbN∗,

respectively,areindependent.Therefore,µ[N∗\aN∗∩N∗\bN∗]=(cid:0)

1−

1(cid:1)(cid:0)

1−

1(cid:1)

.Moregenerally,

a b

foranya ,...,a ∈N∗suchthatgcd(a ,...,a )=1,theeventsN∗\a N∗,...,N∗\a N∗are

1 m 1 m 1 n

independents.

Foranym,n∈N∗suchthatm

 (cid:12)     (cid:12)   

(cid:12) (cid:12)

µ[{m}]=µ{m}(cid:12) (cid:12) (cid:92) N∗\pN∗ µ (cid:92) N∗\pN∗ +µ{m}(cid:12) (cid:12) (cid:91) pN∗ µ (cid:91) pN∗ 

(cid:12) (cid:12)

(cid:12)m

 (cid:12)   

(cid:12)

=µ{m}(cid:12) (cid:12) (cid:92) N∗\pN∗ µ (cid:92) N∗\pN∗ 

(cid:12)

(cid:12)m

 

(cid:92)

≤µ N∗\pN∗ 

m

(cid:18) (cid:19)

(cid:89) 1

= 1−

p

m

2

However,

(cid:16) (cid:17)

(cid:81) 1− 1

(cid:89)

(cid:18) 1(cid:19)

p≤n

p

1− =

(cid:16) (cid:17)

p (cid:81) 1− 1

m

p≤m

logm 1+O(1/logn)

= · (FromTheorem3)

logn 1+O(1/logm)

(cid:16) (cid:17)

Takingn→∞,wehave (cid:81) 1− 1 =0. Therefore,foranym′ ≥1,µ[{m′}]=0.

p

m

Finally,sinceforc∈N∗,wehaveµ[cN∗]=(cid:80)

µ[{α}]=0,whichisacontradiction.

α∈cN∗

Definition1(AsymptoticDensity). LetA⊆N∗. TheasymptoticdensityofthesetA,denotedby

d(A),isgivenbythefollowinglimitwhenitexists:

|A∩[x]|

d(A)= lim (1)

x→∞ x

Furthermore, givenasetB ⊂ N∗, theasymptoticdensityofthesetAoverthesetB, denotedby

d (A),isgivenbythefollowinglimitwhenitexists:

B

|A∩B∩[x]|

d (A)= lim (2)

B x→∞ |B∩[x]|

Informally,foranysetA,B ⊂N∗,theasymptoticdensityd(A),whenitexists,canbeinterpreted

as the probability that a non-zero natural number sampled uniformly at random is in A, and the

asymptoticdensityd (A),whenitexists,canbeinterpretedastheprobabilitythatanintegersampled

B

uniformlyatrandomfromBisinA.

Lemma4. Foranya∈N∗,d(aN∗)=1/a.

Proof. Supposea∈N∗. Foranyx∈N∗,wehavex/a−1≤|aN∗∩[x]|≤x/a. Therefore,

|aN∗∩[x]| 1

lim =

x→∞ x a

2.2 NumberTheoriticfunctions

Inthissection,wepresentnumbertheoreticfunctionsthatwillhelpusgetsomeinsightsonthelargest

primefactorofaninteger.

Dickman-ρ function Let ρ : R → [0,1] be the continuous function that is a solution to the

≥0

differentialequationuρ′(u)+ρ(u−1)=0foru>1subjectedtotheinitialconditionsρ(u)=1

for0≤u≤1.

Lemma5([dB51]). Foru>1,

(cid:18) (cid:18) (cid:18) (cid:19)(cid:19)(cid:19)

loglogu

ρ(u)=exp −u logu+loglogu−1+O

logu

FromtheLemma5,wecaninferthatρ(u) ∼ (ulogu)−u asu → ∞,whichistheapproximation

that we will use. We refer the reader to the work of de Bruijn [dB51] for a detailed proof of the

Lemma.

3

Smoothintegercountingfunction Givenx,y,a,q ∈N∗suchthatx>y,let

Ψ (x,y)=#{n∈[x]:(P+(n)≤y)∧(n≡amodq)

a,q

bethefunctionthatcountthenumberofy-smoothintegers(integerswithprimefactorssmallerthan

y)havingtheforma+kq,withk ∈N,intheinterval[x]. Forinstance,ifweseta=1andq =2,

thenΨ (x,y)countsthenumberofy-smoothintegersamongtheoddintegersin[x].

1,2

Lemma6([HT93]). Letx,y,a,q ∈N∗suchthatx>yandgcd(a,q)=1. Foranyϵ>0suchthat

u=log(x)/log(y)≪(log x)1−ϵ,

2

(cid:18) (cid:18) (cid:19)(cid:19)

xρ(u) 1

Ψ (x,y)= 1+O √

a,q q ulogy

From the above Lemma 6, it follows that Ψ (x,y) ∼ xρ(u)/q as y → ∞. In addition, from

a,q

Lemma 6, it follows that an integer n sampled uniformly random in the interval [x] such that

n=a+kq,withk ∈N,isy-smoothwithprobabilityρ(u)/q. Wepointthereadertothesurveyof

HildebrandandTenenbaum[HT93]foradetailedproofofLemma6.

3 PrimeFactorsamongIntegers

Inthissection,weprovideananalysisofprimefactorsofintegerssampleduniformlyatrandom.

First,weprovideatheoremontheprobabilitythatthereexistsaprimefactorthatdividesallintegers

withinafinitesetsampleduniformlyatrandom. Next,wepresentatheoremontheprobabilitythat

anintegersampleduniformlyatrandomisnotsmooth. Thisallowsustodeduceaboundonthe

probabilitythatintegerswithinasetofsampleduniformlyatrandomdivideeachother.

Theorem2. Foranya ,...,a ∈N∗sampleduniformlyatrandom,

1 m

Pr[gcd(a ,...,a )=1]=1/ζ(m)

1 m

whereζ(·)istheRiemannZetafunction.

Proof. Supposea ,...,a ∈N∗aresampleduniformlyatrandom. FromLemma4,weknowthat

1 m

theprobabilitythataprimepdividesa toa is1/pm. Inaddition,gcd(a ,...,a ) = 1ifand

1 m 1 m

onlytheredoesnotexistaprimeqsuchthatqdividesa toa . Therefore,

1 m

(cid:18) (cid:19)

(cid:89) 1

Pr[gcd(a ,...,a )=1]= 1−

1 m pm

p∈Primes

1

= (FromLemma2)

ζ(m)

ItshouldnotbesurprisingthattheequalitygiveninTheorem2quicklyreaches1asmincreases. For

instance,takingm=5,wehave1/ζ(5)≈0.96. However,thisisnotenoughforsomecryptographic

applications. Forinstance,itispossibletosamplea ,...,a ∈ N∗ suchasgcd(a ,...,a ) = 1

1 m 1 m

butthereexistsa ∈{a ,...,a }suchthata

|(cid:81)m

a . Thiscanhappenwithnon-negligible

i 1 m i j=1,j̸=i j

probabilityifa issmooth. Insomecryptographicsettings,suchastheissuanceofcryptographic

i

proofsthatanelementispartofaset,suchaseventcanbedeleterious. Inthefollowinglines,we

presentaTheoremextractedfromtheworkofKemmoeandLysyanskaya[KL24]thatattemptsto

provideabetterboundattheprobabilityintegerssampleuniformlyarenotsmoothanddonotdivide

eachother.

Theorem 3 ([KL24]). Let ℓ ∈ N∗ be a sufficiently large natural number. Suppose x ∼

√

U(Odds(2ℓ−1,2ℓ−1)). Forevery1≤c≤ 4ℓ,

√

(cid:32)√ (cid:33)−4ℓ

(cid:104) √ (cid:105) 4ℓ

Pr P+(x)≤2c ℓ ≤ logℓ

4

4

√ √

Proof. Let x ∼ U(Odds(2ℓ−1,2ℓ −1)) and suppose 1 ≤ c ≤ 4ℓ. The event “P+(x) ≤ 2c ℓ”

√ √

is exactly the event that x is 2c ℓ-smooth. Let η be the number of 2c ℓ-smooth integers in

Odds(2ℓ−1,2ℓ−1). Therefore,

√ √

η =Ψ (2ℓ−1,2c ℓ)−Ψ (2ℓ−1,2c ℓ)

1,2 1,2

( =♠)

1 (2ℓ−1)(cid:32)√

ℓ

log(cid:32)√ ℓ(cid:33)(cid:33)−√ ℓ/c −2ℓ−1(cid:18)

ℓ− √1

log(cid:18)

ℓ−

√1(cid:19)(cid:19)−(ℓ−1)/c√ ℓ



2 c c c ℓ c ℓ

√

(cid:32)√ (cid:32)√ (cid:33)(cid:33)− ℓ/c

ℓ ℓ 2ℓ−1 ℓ−1

≈2ℓ−2 log (sinceforlargeℓ, ≈1and ≈1)

c c 2ℓ ℓ

√

(cid:32)√ (cid:33)−4ℓ

4ℓ √

≤2ℓ−2 logℓ (settingc= 4ℓ)

4

Equation(♠)isobtainedbyreplacingΨ (x,y)andρ(u)withtheirapproximationderivedfrom

a,q

Lemma6andLemma5,respectively. SinceOdds(2ℓ−1,2ℓ−1)=2ℓ−2,itfollowsthat

√

(cid:32)√ (cid:33)−4ℓ

(cid:104) √ (cid:105) η 4ℓ

Pr P+(x)≤2c ℓ = ≤ logℓ

2ℓ−2 4

√

Corollary 2 ([KL24]). Let ℓ ∈ N∗ be a sufficiently large integer and 1 ≤ c ≤ 4ℓ. Suppose

x ,...,x ∼ U(cid:0) Odds(2ℓ−1,2ℓ−1)(cid:1) ,withm ∈ N∗. LetEbetheeventthatthereexistsi ∈ [m]

1 m

suchthatP+(a )|(cid:81) a . Then,

i j∈[m]\{i} j

 (cid:32)√ (cid:33)−√ 4ℓ

1 4ℓ

Pr[E]≤m2  + logℓ 

2ℓ3/4 4

√

Proof. Let ℓ ∈ N∗ be a sufficiently large integer and m ∈ N∗. Suppose 1 ≤ c ≤ 4ℓ and

x ,x ,...,x ∼ U(cid:0) Odds(2ℓ−1,2ℓ−1)(cid:1) . LetE betheeventhatP+(a )divides (cid:81) a .

1 2 m i i j∈[m]\{i} j

SinceP+(a )isaprime,fromCorollary1,itfollowsthatE isexactlytheeventthatthereexists

i i

j ∈[m]\{i}suchthatP+(a )dividesa . Wehave

i j

Pr[E ]≤ (cid:88) Pr(cid:2) P+(a )dividesa (cid:3)

i i j

j∈[m]\{i}

(cid:88) (cid:104) √ (cid:105) (cid:104) √ (cid:105)

≤ Pr P+(a )dividesa |P+(a )>2c ℓ +Pr P+(a )≤2c ℓ

i j i i

j∈[m]\{i}

√

(cid:32)√ (cid:33)−4ℓ

(1) (cid:88) 1 4ℓ

≤ √ + logℓ

2c ℓ 4

j∈[m]\{i}

 (cid:32)√ (cid:33)−√ 4ℓ

1 4ℓ

=(m−1) √ + logℓ 

2c ℓ 4

 (cid:32)√ (cid:33)−√ 4ℓ

1 4ℓ √

≤(m−1) + logℓ  (Settingc= 4ℓ)

2ℓ3/4 4

Inequality(1)followsfromthefactthatwehave#Odds(2ℓ−1,2ℓ−1)/P+(a )multiplesofP+(a )

i i

inOdds(2ℓ−1,2ℓ−1). SinceE=∪m E ,itfollowsthat

i=1 i

(cid:88)m



1

(cid:32)√

4ℓ

(cid:33)−√ 4ℓ

Pr[E]≤ Pr[E i]≤m2 

2ℓ3/4

+

4

logℓ 

i=1

5

4 Futureworks

Initially,thegoalofthisarticlewastoimproveontheboundgiveninTheorem3. However,duetoa

lackoftime,wewerenotabletoachievethatobjective.

Wepresentsomeoftheavenuesthatweattemptedtoexploreandweleavethemaspotentialfuture

works.

Hardy-RamanujanTheorem Foranintegern∈N∗,letω(n)bethenumberofprimefactorsofn.

ItwasshownbyHardyandRamanujanthatω(n)isarandomvariablewhosedistributionisnormal

withmeanloglognandvarianceloglogn[Pin14]. Isitpossibletoincorporatethisinformationin

theanalysisofprimefactorsofanintegerbyseeinganintegernasacompositionofω(n)binswhere

aprimepfallsinabinwithprobability1/pwiththetotalnumberofballs/primestobethrownis

π(n)≈n/lognaccordingtothePrimeNumberTheorem?

Consideringthek-thlargestprime KnuthandPardo[KP76]anaylizedthedistributionofthe

k-thlargestprimeofaninteger,extendingtheworkssummarizedinthesurveyofHildebrandand

Tenenbaum[HT93]onthedistributionofthelargestprimeofaninteger. Theyconsideredthefunction

Ψ (x,x1/α)thatcountsthenumberofintegersintheset[x]whosek-thlargestprimearelessthanor

k

equaltox1/α. TheyprovedthatΨ (x,x1/α)=ρ (α)x+O(x/logx)whereρ (α)isrecursively

k k k

definedasfollows:

 (cid:82)α

1− (ρ (t−1)−ρ (t−1))dt/t forα>1,k ≥1

 1 k k−1

ρ (α)= 1 for0≤α≤1,k ≥1

k

0 forα≤0ork =0

However,theycameshortfromprovidingasimpleapproximationforρ (·)asdeBruijndidforthe

k

casek =1[dB51]. Clearly,withabetterapproximationofρ (·)andΨ (·,·),oneshouldbeableto

k k

improvetheboundprovidedinCorollary2byconsideringaboutonthesecondlargestprimeofan

integer. Wepostponefurtheranalysisoftheρ (·)functiontofuturework.

k

References

[CL02] JanCamenischandAnnaLysyanskaya. Dynamicaccumulatorsandapplicationtoeffi-

cientrevocationofanonymouscredentials. InMotiYung,editor,AdvancesinCryptology

—CRYPTO2002,pages61–76,Berlin,Heidelberg,2002.SpringerBerlinHeidelberg.

[dB51] NicolaasGdeBruijn. Theasymptoticbehaviourofafunctionoccuringinthetheoryof

primes. JournaloftheIndianMathematicalSociety.NewSeries,15:25–32,1951.

[HT93] AdolfHildebrandandGeraldTenenbaum. Integerswithoutlargeprimefactors. Journal

dethéoriedesnombresdeBordeaux,5(2):411–484,1993.

[KL24] Victor Youdom Kemmoe and Anna Lysyanskaya. Rsa-based dynamic accumulator

withouthashingintoprimes. CryptologyePrintArchive,Paper2024/505,2024. https:

//eprint.iacr.org/2024/505.

[Kou20] Dimitris Koukoulopoulos. The distribution of prime numbers. Graduate Studies in

Mathematics.AmericanMathematicalSociety,Providence,RI,July2020.

[KP76] DonaldE.KnuthandLuisTrabbPardo. Analysisofasimplefactorizationalgorithm.

TheoreticalComputerScience,3(3):321–348,1976.

[LLMP93] A.K.Lenstra,H.W.Lenstra,M.S.Manasse,andJ.M.Pollard. Thenumberfieldsieve.

InArjenK.LenstraandHendrikW.Lenstra,editors,Thedevelopmentofthenumber

fieldsieve,pages11–42,Berlin,Heidelberg,1993.SpringerBerlinHeidelberg.

[Ove15] MariusOverholt. Acourseinanalyticnumbertheory. Graduatestudiesinmathematics.

AmericanMathematicalSociety,Providence,RI,February2015.

6

[Pin14] Ross G. Pinsky. The Hardy–Ramanujan Theorem on the Number of Distinct Prime

Divisors,pages81–87. SpringerInternationalPublishing,Cham,2014.

[Ten15] GeraldTenenbaum. Introductiontoanalyticandprobabilisticnumbertheory. Graduate

studies in mathematics. American Mathematical Society, Providence, RI, 3 edition,

August2015.

[Wes20] Benjamin Wesolowski. Efficient verifiable delay functions. Journal of Cryptology,

33(4):2113–2147,Oct2020.

7