a computational introduction to number theory and algebra - victor shoup

《a computational introduction to number theory and algebra - victor shoup》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、TEAMLinGAComputationalIntroductiontoNumberTheoryandAlgebra(Version1)VictorShoupTEAMLinGTEAMLinGThisPDFdocumentcontainshyperlinks,andonemaynavigatethroughitbyclickingontheorem,definition,lemma,equation,andpagenumbers,aswellasURLs,andchapterandsectiontitlesinthet

2、ableofcontents;mostPDFviewersshouldalsodisplayalistof“bookmarks”thatallowdirectaccesstochaptersandsections.TEAMLinGCopyright
c2005byVictorShoupAllrightsreserved.TherighttopublishordistributethisworkinprintformbelongsexclusivelytoCambridgeUniv

3、ersityPress;however,thiselectronicversionisdistributedunderthetermsandconditionsofaCreativeCommonslicense(Attribution-NonCommercial-NoDerivs2.0):Youarefreetocopy,distribute,anddisplaythiselectronicversionunderthefollowingconditions:Attribution.Youmustgivetheor

4、iginalauthorcredit.Noncommercial.Youmaynotusethiselectronicversionforcommercialpurposes.NoDerivativeWorks.Youmaynotalter,transform,orbuilduponthiselectronicversion.Foranyreuseordistribution,youmustmakecleartoothersthelicensetermsofthiswork.Anyoftheseconditions

5、canbewaivedifyougetpermissionfromtheauthor.Formoreinformationaboutthelicense,visitcreativecommons.org/licenses/by-nd-nc/2.0.TEAMLinGContentsPrefacepagexPreliminariesxiv1Basicpropertiesoftheintegers11.1Divisibilityandprimality11.2Idealsandgreatestcommondivisors

6、41.3Someconsequencesofuniquefactorization82Congruences132.1Definitionsandbasicproperties132.2Solvinglinearcongruences152.3Residueclasses202.4Euler’sphifunction242.5Fermat’slittletheorem252.6ArithmeticfunctionsandM¨obiusinversion283Computingwithlargeintegers333.

7、1Asymptoticnotation333.2Machinemodelsandcomplexitytheory363.3Basicintegerarithmetic393.4ComputinginZn483.5Fasterintegerarithmetic(∗)513.6Notes524Euclid’salgorithm554.1ThebasicEuclideanalgorithm554.2TheextendedEuclideanalgorithm584.3ComputingmodularinversesandC

8、hineseremaindering624.4Speedingupalgorithmsviamodularcomputation634.5Rationalreconstructionandapplications664.6Notes73vTEAMLinGviContents5Thedistributionofprimes745.1Chebyshev’sthe