A Computational Instroduction to Number Theory And Algebra V2

《A Computational Instroduction to Number Theory And Algebra V2》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、AComputationalIntroductiontoNumberTheoryandAlgebra(Version2)VictorShoupThisPDFdocumentcontainshyperlinks,andonemaynavigatethroughitbyclick-ingontheorem,definition,lemma,equation,andpagenumbers,aswellasURLs,andchapterandsectiontitlesinthetableofcontents;mostPDFviewer

2、sshouldalsodisplayalistof“bookmarks”thatallowdirectaccesstochaptersandsections.Copyright©2008byVictorShoupTheelectronicversionofthisworkisdistributedunderthetermsandconditionsofaCreativeCommonslicense(Attribution-NonCommercial-NoDerivs3.0):Youaref

3、reetocopy,distribute,anddisplaytheelectronicversionofthisworkunderthefollowingconditions:Attribution.Youmustgivetheoriginalauthorcredit.Noncommercial.Youmaynotusetheelectronicversionofthisworkforcommercialpurposes.NoDerivativeWorks.Youmaynotalter,transform,orbuildu

4、pontheelectronicversionofthiswork.Foranyreuseordistribution,youmustmaketheselicensetermscleartoothers.Anyoftheseconditionscanbewaivedifyougetpermissionfromtheauthor.Formoreinformationaboutthelicense,visitcreativecommons.org/licenses/by-nd-nc/3.0.Allotherrightsreser

5、ved.Inparticular,therighttopublishordistributethisworkinprintformbelongsexclusivelytoCambridgeUniversityPress.ContentsPrefacepagexPreliminariesxiv1Basicpropertiesoftheintegers11.1Divisibilityandprimality11.2Idealsandgreatestcommondivisors51.3Someconsequencesofuniqu

6、efactorization102Congruences152.1Equivalencerelations152.2Definitionsandbasicpropertiesofcongruences162.3Solvinglinearcongruences192.4TheChineseremaindertheorem222.5Residueclasses252.6Euler’sphifunction312.7Euler’stheoremandFermat’slittletheorem322.8Quadraticresidue

7、s352.9Summationsoverdivisors453Computingwithlargeintegers503.1Asymptoticnotation503.2Machinemodelsandcomplexitytheory533.3Basicintegerarithmetic553.4ComputinginZn643.5Fasterintegerarithmetic()693.6Notes714Euclid’salgorithm744.1ThebasicEuclideanalgorithm744.2Theext

8、endedEuclideanalgorithm774.3ComputingmodularinversesandChineseremaindering82vviContents4.4Speedingupalgorithmsviamodularcomputation844.5Aneectiv