ELEMENTARYNUMBERTHEORY：初等数论

《ELEMENTARYNUMBERTHEORY：初等数论》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ELEMENTARYNUMBERTHEORYApplicationtoCryptographyFebruary,2014Contents1ElementaryNumberTheory21.1GreatestCommonDivisor...................................41.2TheEuclideanAlgorithm...................................51.3LinearDiophantineEquation.....................

2、............81.4Primes..............................................121.5PrimeFactorization......................................151.6Congruences...........................................181.7LinearCongruences.......................................211.8TheEule

3、rPhi{Function....................................261.9SomeSpecialCongruences...................................281.10BasicCryptography......................................311.10.1CaesarCiphers.....................................311.10.2LinearCiphers..........

4、...........................321.10.3BlockCiphers......................................331.11Public-KeyCryptography...................................381.11.1TheRSAAlgorithm..................................381.11.2DigitalSignatures...............................

5、....431.11.3Die-HellmanKeyExchange.............................441.11.4TheKnapsackCryptosystem.............................4411ElementaryNumberTheoryZ=f:::::::::::4;3;2;1;0;1;2;3;4;::::::::::::::gNumberTheoryisthemathematicsoftheintegers.Itisasubsetofthein

6、tegers,theprimes,thosepositiveintegerswithnoproperpositivefactorsotherthan1,thatareparticularlyimportantincomputerscience.Animportantresultofnumbertheoryshowsthattheprimesarethemultiplicativebuildingblocksofthepositiveintegers.Thisresult,calledthefundamentalthe

7、oremofarithmetic,saysthateverypositiveintegercanbeuniquelywrittenasaproductofprimes.Interestintheprimenumbersdateback2,500yearsago,tothestudyofancientGreekmathemati-cians.Perhapstherstquestionaboutprimesthatcomestomindiswhetherthereareinnitelymany.TheancientG

8、reekmathematicianEuclidprovidedaproofthatthereareinnitelymanyprimes.Inter-estintheprimeswasrekindledinthe17thand18thcenturies,whenmathematicianssuchasPierredeFermatandLeonh