Motivation
• PrimeFactorsplayanimportantroleinNumberTheoryandCryptographic.
◦ FromtheChineseRemainderTheorem,Givenn∈Z,
Z/nZ ∼ = Z/pk1Z⊕···⊕Z/pknZ
1 n
Wherep isaprimefactorofn.
i
◦ Anintegern∈Zcanbefactoredintime
√
(cid:112)
exp(( 2+O(1)) logploglogp)
wherepisthesmallestprimefactorofn[LLMP93]
2/13
Wedonotpresentananswertothesequestions,butwepresentresultsthatattempttogetclosetoan
answer
Motivation
• Givena ,a ∈ N,whatistheprobabilitythattheydonotshareaprime?
1 2
• Moregenerally,givena ,...,a ∈ Nsampleduniformlyatrandom,whatistheprobabilitythat
1 m
eachofthemhasauniqueprime?
2/13
Motivation
• Givena ,a ∈ N,whatistheprobabilitythattheydonotshareaprime?
1 2
• Moregenerally,givena ,...,a ∈ Nsampleduniformlyatrandom,whatistheprobabilitythat
1 m
eachofthemhasauniqueprime?
Wedonotpresentananswertothesequestions,butwepresentresultsthatattempttogetclosetoan
answer
2/13
Proof.Weproceedbycontradiction.Assumeµexists.
Fora,b ∈ N∗suchthatgcd(a,b) = 1,wehaveaN∗∩bN∗ = abN∗.Hence,underµ,aN∗,bN∗are
independent,whichimpliesthatN∗\aN∗,N∗\bN∗areindependent.
Foranym,n ∈ N∗,suchthatm < n,wehave
(cid:92)
Pr[{m}] ≤ Pr N∗\pN∗
m (cid:18) (cid:19) (cid:89) 1 = 1− p m (cid:124) (cid:123)(cid:122) (cid:125) =0asn→∞ Preliminaries Probabilisticnotioninnumbertheory LetN∗ = N >0 Theorem([Ten15],Chap3) TheredoesnotexistaprobabilitymeasureµoverN∗suchthatforanya ∈ N∗,wehaveµ[aN∗] = 1/a. 3/13 Fora,b ∈ N∗suchthatgcd(a,b) = 1,wehaveaN∗∩bN∗ = abN∗.Hence,underµ,aN∗,bN∗are independent,whichimpliesthatN∗\aN∗,N∗\bN∗areindependent. Foranym,n ∈ N∗,suchthatm < n,wehave (cid:92) Pr[{m}] ≤ Pr N∗\pN∗ m (cid:18) (cid:19) (cid:89) 1 = 1− p m (cid:124) (cid:123)(cid:122) (cid:125) =0asn→∞ Preliminaries Probabilisticnotioninnumbertheory LetN∗ = N >0 Theorem([Ten15],Chap3) TheredoesnotexistaprobabilitymeasureµoverN∗suchthatforanya ∈ N∗,wehaveµ[aN∗] = 1/a. Proof.Weproceedbycontradiction.Assumeµexists. 3/13 Foranym,n ∈ N∗,suchthatm < n,wehave (cid:92) Pr[{m}] ≤ Pr N∗\pN∗ m (cid:18) (cid:19) (cid:89) 1 = 1− p m (cid:124) (cid:123)(cid:122) (cid:125) =0asn→∞ Preliminaries Probabilisticnotioninnumbertheory LetN∗ = N >0 Theorem([Ten15],Chap3) TheredoesnotexistaprobabilitymeasureµoverN∗suchthatforanya ∈ N∗,wehaveµ[aN∗] = 1/a. Proof.Weproceedbycontradiction.Assumeµexists. Fora,b ∈ N∗suchthatgcd(a,b) = 1,wehaveaN∗∩bN∗ = abN∗.Hence,underµ,aN∗,bN∗are independent,whichimpliesthatN∗\aN∗,N∗\bN∗areindependent. 3/13 (cid:18) (cid:19) (cid:89) 1 = 1− p m (cid:124) (cid:123)(cid:122) (cid:125) =0asn→∞ Preliminaries Probabilisticnotioninnumbertheory LetN∗ = N >0 Theorem([Ten15],Chap3) TheredoesnotexistaprobabilitymeasureµoverN∗suchthatforanya ∈ N∗,wehaveµ[aN∗] = 1/a. Proof.Weproceedbycontradiction.Assumeµexists. Fora,b ∈ N∗suchthatgcd(a,b) = 1,wehaveaN∗∩bN∗ = abN∗.Hence,underµ,aN∗,bN∗are independent,whichimpliesthatN∗\aN∗,N∗\bN∗areindependent. Foranym,n ∈ N∗,suchthatm < n,wehave (cid:92) Pr[{m}] ≤ Pr N∗\pN∗ m 3/13 Preliminaries Probabilisticnotioninnumbertheory LetN∗ = N >0 Theorem([Ten15],Chap3) TheredoesnotexistaprobabilitymeasureµoverN∗suchthatforanya ∈ N∗,wehaveµ[aN∗] = 1/a. Proof.Weproceedbycontradiction.Assumeµexists. Fora,b ∈ N∗suchthatgcd(a,b) = 1,wehaveaN∗∩bN∗ = abN∗.Hence,underµ,aN∗,bN∗are independent,whichimpliesthatN∗\aN∗,N∗\bN∗areindependent. Foranym,n ∈ N∗,suchthatm < n,wehave (cid:92) Pr[{m}] ≤ Pr N∗\pN∗ m (cid:18) (cid:19) (cid:89) 1 = 1− p m (cid:124) (cid:123)(cid:122) (cid:125) =0asn→∞ 3/13 Preliminaries Probabilisticnotioninnumbertheory Definition LetA ⊆ N∗.TheasymptoticdensityofthesetA,denotedbyd(A),isgivenbythefollowinglimitwhen itexists: |A∩[x]| d(A) = lim (1) x→∞ x 4/13 Proof.Supposea ∈ N∗.Foranyx ∈ N∗,wehavex −1 ≤ |aN∗∩[x]| ≤ x.Therefore, a a |aN∗∩[x]| 1 lim = x→∞ x a Preliminaries Probabilisticnotioninnumbertheory Lemma Foranya ∈ N∗,d(aN∗) = 1/a. 5/13 Preliminaries Probabilisticnotioninnumbertheory Lemma Foranya ∈ N∗,d(aN∗) = 1/a. Proof.Supposea ∈ N∗.Foranyx ∈ N∗,wehavex −1 ≤ |aN∗∩[x]| ≤ x.Therefore, a a |aN∗∩[x]| 1 lim = x→∞ x a 5/13 Proof.Givena ,...,a ∈ N∗,weknowthattheprobabilitythataprimepdividesallofthemis1/pm. 1 m “gcd(a ,...,a ) = 1”istheeventthatthereexistnop ∈ PRIMESsuchthatpdividesallofthem. 1 m Hence, (cid:18) (cid:19) (cid:89) 1 Pr[gcd(a ,...,a ) = 1] = 1− 1 m pm p∈PRIMES 1 = ζ(m) PrimeFactorsamongInteger Theorem Foranya ,...,a ∈ N∗sampleduniformlyatrandom, 1 m Pr[gcd(a ,...,a ) = 1] = 1/ζ(m) 1 m whereζ(·)istheRiemannZetafunction. 6/13 PrimeFactorsamongInteger Theorem Foranya ,...,a ∈ N∗sampleduniformlyatrandom, 1 m Pr[gcd(a ,...,a ) = 1] = 1/ζ(m) 1 m whereζ(·)istheRiemannZetafunction. Proof.Givena ,...,a ∈ N∗,weknowthattheprobabilitythataprimepdividesallofthemis1/pm. 1 m “gcd(a ,...,a ) = 1”istheeventthatthereexistnop ∈ PRIMESsuchthatpdividesallofthem. 1 m Hence, (cid:18) (cid:19) (cid:89) 1 Pr[gcd(a ,...,a ) = 1] = 1− 1 m pm p∈PRIMES 1 = ζ(m) 6/13 Yes,Ifweassumethata ,...,a arelargeoddintegers[KL24] 1 m • However,gcd(a ,...,a ) = 1doesnotimpliesthattheredoesnotexisti ∈ {1,...,m}suchthat 1 m a doesnotdivides(cid:81)m a. i j=1,j̸=i j • Canwedosomethingbetter? PrimeFactorsamongInteger Theorem Foranya ,...,a ∈ N∗sampleduniformlyatrandom, 1 m Pr[gcd(a ,...,a ) = 1] = 1/ζ(m) 1 m whereζ(·)istheRiemannZetafunction. • Form = 2,1/ζ(2) ≈ 0.6andform = 5,wehave1/ζ(5) ≈ 0.9. 7/13 Yes,Ifweassumethata ,...,a arelargeoddintegers[KL24] 1 m • Canwedosomethingbetter? PrimeFactorsamongInteger Theorem Foranya ,...,a ∈ N∗sampleduniformlyatrandom, 1 m Pr[gcd(a ,...,a ) = 1] = 1/ζ(m) 1 m whereζ(·)istheRiemannZetafunction. • Form = 2,1/ζ(2) ≈ 0.6andform = 5,wehave1/ζ(5) ≈ 0.9. • However,gcd(a ,...,a ) = 1doesnotimpliesthattheredoesnotexisti ∈ {1,...,m}suchthat 1 m a doesnotdivides(cid:81)m a. i j=1,j̸=i j 7/13 Yes,Ifweassumethata ,...,a arelargeoddintegers[KL24] 1 m PrimeFactorsamongInteger Theorem Foranya ,...,a ∈ N∗sampleduniformlyatrandom, 1 m Pr[gcd(a ,...,a ) = 1] = 1/ζ(m) 1 m whereζ(·)istheRiemannZetafunction. • Form = 2,1/ζ(2) ≈ 0.6andform = 5,wehave1/ζ(5) ≈ 0.9. • However,gcd(a ,...,a ) = 1doesnotimpliesthattheredoesnotexisti ∈ {1,...,m}suchthat 1 m a doesnotdivides(cid:81)m a. i j=1,j̸=i j • Canwedosomethingbetter? 7/13 PrimeFactorsamongInteger Theorem Foranya ,...,a ∈ N∗sampleduniformlyatrandom, 1 m Pr[gcd(a ,...,a ) = 1] = 1/ζ(m) 1 m whereζ(·)istheRiemannZetafunction. • Form = 2,1/ζ(2) ≈ 0.6andform = 5,wehave1/ζ(5) ≈ 0.9. • However,gcd(a ,...,a ) = 1doesnotimpliesthattheredoesnotexisti ∈ {1,...,m}suchthat 1 m a doesnotdivides(cid:81)m a. i j=1,j̸=i j • Canwedosomethingbetter?Yes,Ifweassumethata ,...,a arelargeoddintegers[KL24] 1 m 7/13 PrimeFactorsamongInteger LetOdds(2ℓ−1,2ℓ−1) = {2ℓ−1 ≤ n ≤ 2ℓ−1 | n ≡ 1 mod 2} LetP+(·)bethefunctionthatreturnthelargestprimefactorofaninteger Theorem([KL24]) √ Letℓ ∈ N∗beasufficientlylargenaturalnumber.Supposex ∼ 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 8/13 PrimeFactorsamongInteger Corollary([KL24]) √ Letℓ ∈ N∗beasufficientlylargeintegerand1 ≤ c ≤ 4 ℓ.Supposex ,...,x ∼ U(cid:0) Odds(2ℓ−1,2ℓ−1)(cid:1) , 1 m withm ∈ N∗.LetEbetheeventthatthereexistsi ∈ [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 9/13 Theorem (cid:18) (cid:18) (cid:19)(cid:19)logx logx logx logy Ψ (x,y) ∼ x log a,q logy logy asy → ∞ PrimeFactorsamongInteger UsefulNumbertheoreticfunction Givenx,y,a,q ∈ N∗suchthatx > y,let Ψ (x,y) = #{n ∈ [x] : (P+(n) ≤ y)∧(n ≡ a mod q)} a,q 10/13 Theorem (cid:18) (cid:18) (cid:19)(cid:19)logx logx logx logy Ψ (x,y) ∼ x log a,q logy logy asy → ∞ PrimeFactorsamongInteger UsefulNumbertheoreticfunction Givenx,y,a,q ∈ N∗suchthatx > y,let Ψ (x,y) = #{n ∈ [x] : (P+(n) ≤ y)∧(n ≡ a mod q)} a,q Ψ (x,y)countsthenumberofintegersintheset{1,...,n}suchthattheirlargestprimefactorisless a,q thanyandtheycanbewrittenasa+kq.Ifa = 1,q = 2,Ψ (x,y)countsthenumberofoddintegers 1,2 whoselargestprimefactorislessthany 10/13 Theorem (cid:18) (cid:18) (cid:19)(cid:19)logx logx logx logy Ψ (x,y) ∼ x log a,q logy logy asy → ∞ PrimeFactorsamongInteger UsefulNumbertheoreticfunction Givenx,y,a,q ∈ N∗suchthatx > y,let Ψ (x,y) = #{n ∈ [x] : (P+(n) ≤ y)∧(n ≡ a mod q)} a,q Ψ (x,y) Pr (cid:2) P+(a) ≤ y(cid:3) = a,q a∼U({n∈[x]:n≡amodq}) x 10/13 PrimeFactorsamongInteger UsefulNumbertheoreticfunction Givenx,y,a,q ∈ N∗suchthatx > y,let Ψ (x,y) = #{n ∈ [x] : (P+(n) ≤ y)∧(n ≡ a mod q)} a,q Ψ (x,y) Pr (cid:2) P+(a) ≤ y(cid:3) = a,q a∼U({n∈[x]:n≡amodq}) x Theorem (cid:18) (cid:18) (cid:19)(cid:19)logx logx logx logy Ψ (x,y) ∼ x log a,q logy logy asy → ∞ 10/13 PrimeFactorsamongInteger Theorem([KL24]) √ Letℓ ∈ N∗beasufficientlylargenaturalnumber.Supposex ∼ 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 √ Proof.Letηbethenumberof2c ℓ-smoothintegersinOdds(2ℓ−1,2ℓ−1) √ √ η = Ψ (2ℓ−1,2c ℓ)−Ψ (2ℓ−1,2c ℓ) 1,2 1,2 1 (cid:32)√ ℓ (cid:32)√ ℓ(cid:33)(cid:33)−√ ℓ/c (cid:18) ℓ−1 (cid:18) ℓ−1(cid:19)(cid:19)−(ℓ−1)/c√ ℓ = (2ℓ−1) log −2ℓ−1 √ log √ 2 c c c ℓ c ℓ √ (cid:32)√ (cid:33)−4ℓ 4 ℓ √ ≤ 2ℓ−2 logℓ (settingc = 4 ℓ) 4 11/13 FutureWorks • Hardy-RamanujanTheorem:Foranintegern ∈ N∗,letω(n)bethenumberofprimefactorsofn. ItwasshownbyHardyandRamanujanthatω(n)isarandomvariablewhosedistributionis normalwithmeanloglognandvarianceloglogn • Consideringthek-thlargestprime:KnuthandPardo[KP76]anaylizedthedistributionofthek-th largestprimeofaninteger.TheyprovedthatΨ (x,x1/α) = ρ (α)x+O(x/logx)whereρ (α)is k k k recursivelydefinedasfollows: (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 12/13 ThankYou 13/13
