研FMIS-Ch3-DistributionOfPrimeNumbers

《研FMIS-Ch3-DistributionOfPrimeNumbers》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、有限域与计算数论FiniteFieldandComputationalNumberTheory张文芳信息科学与技术学院wfzhang@swjtu.edu.cn西南交通大学2012级硕/博研究生课程1ZhangWenfangEmail:wfzhang@swjtu.edu.cnSchoolofInformationScience&TechnologySouthwestJiaotongUniversityPart2ElementaryNumberTheory有限域与计算数论FiniteFieldandComputationalNumberTheory2Part2ElementaryNumber

2、TheoryChapter2TheoryofDivisibilityChapter3DistributionofPrimeNumbersChapter4TheoryofCongruencesChapter5ArithmeticofEllipticCurves3Chapter3DistributionofPrimeNumbers3.1Euler’sFunction3.2PrimeDistributionFunction3.3Approximationsof(x)byx/lnx43.1Euler’sFunctionDefinition3.1.1Letnbeapositiveinteger.Eu

3、ler’s–function,(n),isdefinedtobethenumberofpositiveintegersklessthannwhicharerelativelyprimeton:Example3.1.1Wehaven12345678910100101102103(n)1122426464401003210253.1Euler’sFunctionTheorem3.1.1Letnbeapositiveinteger.Then(1)Euler’s–function(n)ismultiplicative,thatis,ifgcd(m,n)=1,then(mn)=(m)(

4、n).(2)Ifnisaprime,sayp,then(p)=p1.(Conversely,ifpisapositiveintegerwith(p)=p1,thenpisprime.)(3)Ifnisaprimepowerpawitha>1,then(pa)=papa1.63.1Euler’sFunctionTheorem3.1.1Letnbeapositiveinteger.Then(4)Ifnisacompositeandhasthestandardprimefactorization:73.1Euler’sFunctionRemark3.1.1Supposenisknow

5、ntobetheproductoftwodistinctprimespandq.Thenknowledgeofpandqisequivalenttoknowledgeof(n),since(n)=(p1)(q1).Remark3.1.2Thereisnoknownefficientmethodtocompute(n)Iftheprimefactorizationofnisnotknown.Moreprecisely,onecancompute(n)frompandqinO(logn)bitoperations,andonecancomputepandqfromnand(n)in

6、O(logn)3bitoperations.8Chapter3DistributionofPrimeNumbers3.1Euler’sFunction3.2PrimeDistributionFunction3.3Approximationsof(x)byx/lnx93.2PrimeDistributionFunctionDefinition3.2.1Letxbeapositiverealnumber>1.Then(x),isdefinedasfollows:Example3.2.1Theprimenumbersupto100are:2,3,5,7,11,13,17,19,23,29,31

7、,41,43,47,53,59,61,67,71,73,79,83,89,97.Wehavex123102030405075100(x)012481012152125Thatis(x)isthenumberofprimeslessthanorequaltox;itisalsocalledtheprimecountingfunction(theprimedistributionfunction).103.2