解同余式组模负数问题_百度知道
解同余式组模负数问题
我一直疑惑这个负数问题是因为有的题目最后在求同余式的公根时，如果取的模是负数或者是正数那最后答案完全不一样啊？?？比如解一道同余式组x≡3（mod11）①x≡-2（mod13）②x≡5（mod17）③、这样一个同余式组，其中前几个步骤我省略掉，最后一个步骤是z≡-97∕143≡-2(mod7）,即z=-2+7u⑦,最后将⑦式代入⑥式，得x=102+143(-2+7u)=-184+1001u故x≡-184（mod1001）为所求的同余式组的根。我始终不能理解如果z≡-97∕143≡-2(mod7），如果取的模不是负数-2而是5，那么最后的结果就不是x≡-184（mod1001），在计算的过程中如果我取的是正数，结果是不一样的，难道也是对的吗
我有更好的答案
按默认排序
没用！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
一：解同余式组x≡3（mod11）①x≡-2（mod13）②x≡5（mod7）③此题答案为x==-184==817 mod 1001等价于x==3 mod 11x==-2 mod 7*13 二：解同余式组x≡3（mod11）①x≡-2（mod13）②x≡5（mod17）③我用我的方法算一下：x==3//2*6 @11-2//-2*4 @135//-6*-4 @17==3 @111/4==-12/4=-3 @ 135//24==5//7==15//21==15//4==32/4=8 @17注：或5//7==25//35==25//1==25==8 @17==3*13-3*11=6 @ 1438 @17==6*17+8*143 mod 2431==1246 mod 2431结合心算，以上过程简化为：x==x==3//2*6 @11-2//-2*4 @135//-6*-4 @17==3 @11-3 @ 135//7==25//35==8 @17==6 @ 1438 @17==1246 mod 2431
其他类似问题
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁南北朝数学
南北朝数学&
第四节 南北朝数学
一、祖冲之父子的数学工作
　　1．祖冲之父子生平
　　祖冲之(429---500)，河北人，后迁居江南，生活于南朝的宋、齐之间．父亲祖朔之曾在刘宋朝中为官．祖冲之自幼好学，尤喜历、算．青年时曾任南徐州(今镇江)从事史，后来回建康(今南京)任公府参军．他的行政事务虽多，仍利用工余时间进行大量科学研究．他对前代历法进行仔细的分析比较，对八尺高标杆的日影长度坚持观测达十年之久，在此基础上于大明六年(462)完成《大明历》，书中首次应用了岁差理论，是当时中国最先进的历法．但他把该历呈送朝廷后，由于保守势力的阻挠，未能及时推行．大明八年(464)后，祖冲之出任娄县(今江苏昆山)令，刘宋末年再度被调回建康，任谒者仆射(一种司礼节的官)．齐灭宋后又在齐为官，晚年升到长水校尉，享受四品奉禄．曾造指南车、千里船、水碓磨、刻漏等，远近驰名．数学方面，他曾给《九章算术》作注，并与其子祖共同完成数学史上的名著---《缀术》(已佚)．
　　祖曾在梁朝先后担任员外郎、材官将军等职．他多次向朝廷建议修改历法，采用他父亲的《大明历》，经太史令实测天象、考验新旧历法后，政府终于在天监九年(510)采用了《大明历》．天监十三年(514)，祖奉命在淮河上指挥修筑浮山堰，因被洪水冲毁而获罪入狱．他出狱后不久，在南朝边境被北魏军队俘获，软禁于元延明家，在那里遇到北魏天文学家信都芳，两人常在一起讨论天文和数学．梁普通七年(526)，祖南还．他除了和父亲共同完成《缀术》外，还自著《天文录》、《权衡记》等，已失传．
　　2．祖冲之的圆周率
　　继刘徽之后，祖冲之为求得更精确的圆周率而作了艰苦卓绝的努力．据《隋书》记载，他已算得
3．1415926＜π＜3.1415927．
　　祖率和密率，都是当时世界上的最好结果．祖率已精确到七位小数，保持世界纪录近千年．至于密率，堪称数学史上的奇迹．它的特点是既都是准确的．比密率更接近π的分数，其分母比113大得多．可以证明，
　　祖冲之是怎样求圆周率的？这个问题至今还是个谜．因为他的数学著作《缀术》已失传，《隋书》中则只有结论而无求法．据一些史料推测，他可能继承了刘徽的割圆术，通过增加圆内接正多边形的边数来求得更精确的圆周率值．实际上，只要用割圆术求得圆内接正24576(即3×213)边形面积，就可以得到祖率．祖冲之用不足近似值和过剩近似值两数来限定π，这种思想可能也受到刘徽的影响．
　　3．祖原理与球体积公式
　　刘徽开辟了通向球体积公式的正确道路但没有达到目标．祖冲之父子在这条路上继续前进，终于完成了刘徽的未竟之业．祖冲之与戴法兴辩论时曾说：“至若立圆旧误，张衡述而弗改……此则算氏之剧疵也．”可见他对球体积问题进行过深入研究．至于他是否解决了这一问题，不见记载．但根据唐代李淳风注《九章算术》“开立圆术”时引用的资料来看，祖确实解决了这一问题．他很可能是在父亲工作的基础上取得突破的．
　　祖在研究球体积时继承了刘徽的思想，抓住关键性的牟合方盖的体积计算．但他吸取了刘徽的教训，不再直接求方盖体积，而是首先研究立方体内除去牟合方盖的部分．他利用了图形的对称性，着重研究这
面面积为R2－h2(图4．23(1))，因为内外棋截面和等于R2，所以高h处的外棋截面为h2(图4．23(2))．再作一个底边和高都是R，且有一条棱垂直于底面的倒立四棱锥，则梭锥在高h处的截面也是h2(图4．23(3))．祖研究了各体积的关系，提出“幂势既同，则积不容异”的原理．其中“幂”是面积，“势”是关系，“积”是体积．这句话的意思是：在两立体中作与底平行的截面，若截面积处处相同，则两立体体积相等．这一原理可称为“祖原理”，是刘徽原理的特例．西方称此为“卡瓦列里原理”，因为它曾被17世纪的意大利数学家卡瓦列里(B．Cavalieri，1598---1647)重新发现．
　　根据祖原理，很容易得到外棋与倒立四棱锥体积相等的结论，而
　　这便是正确的球体积公式．自《九章算术》以来，历经四个多世纪，这一问题终于得到圆满解决．在祖之前，阿基米德曾用平衡法求得球体积公式，两人的工作是各具特色、殊途同归的．
二、《孙子算经》
　　《孙子算经》三卷，作者名字不详，约成书于公元400年前后．该书是古代一部普及性的数学著作，也是现存古算书中最早的详细介绍筹算法并有算草的书．卷上用诗歌形式介绍了算筹摆法：“凡算之法，先识其位．一从(纵)十横，百立千僵；千十相望，万百相当．满六以上，五在上方；六不积算，五不单张．”然后具体介绍筹算乘除法的步骤．卷中则举例说明如何用算筹进行分数运算和开平方．这些记载，都是研究古代筹算的极好材料．
　　《孙子算经》卷下第26题为数学史上有名的“物不知数”问题：“今有物，不知其数．三、三数之剩二，五、五数之剩三，七、七数之剩二．问物几何？答曰二十三．”此题相当于现在的同余式组，设N为所求之数，则有
　　N≡2(mod 3)≡3(mod
5)≡2(mod7)．
　　书中给出解法如下：“三、三数之剩二，置一百四十；五、五数之剩三，置六十三；七、七数之剩二，置三十，并之得二百三十三．以二百一十减之，即得．”若以现代符号表示，则为
　　N＝70×2＋21×3＋15×2－2×105=23，
　　这便得到原题的解．式中70由2×(5×7)得来，21由3×7得来，15由3×5得来，而105由3×5×7(即三模连乘积)得来．接着，书中又给出更一般的解法：“凡三、三数之剩一则置七十，五、五数之剩一则置二十一，七、七数之剩一则置十五．一百六以上，以一百五减之，即得．”这相当于解同余式组
　　N≡r1(mod3)≡r2(mod5)≡r3(mod7)，
　　其解为
　　N＝70r1＋21r2+15r3-105P．
　　式中P要选择这样的正整数，它使N成为小于105的正数．
　　“物不知数”问题可推广为下述定理：
　　设p1，P2，…，pn互素，m=p1?p2?…?pn，如果能找到一组
　　这一定理的明确表述是德国数学家高斯(C．F．Gauss，1777---1855)于1801年首次给出的，他当时并不知道《孙子算经》中的“物不知数”问题．后来，西方数学史家发现该问题的解法符合高斯的定理，遂称之为“中国剩余定理”．而在中国国内，一般叫“孙子定理”．
三、《张丘建算经》
　　《张丘建算经》成书于5世纪，比《孙子算经》稍晚．作者张丘建，河北清河人．该书共三卷92题，包括测量、纺织、交换、纳税、冶炼、土木工程、利息等各方面的计算问题．
　　等差级数是书中一项重要内容．例如卷上第22题，大意为某女子善于织布，一天比一天织得快，而每天增加的数量都一样．已知第一日织5尺，30日共织930尺，求每日比前一日多织多少？这是一个已知等差级数首项、项数和前n项和，求公差的问题．设a1为首项，n为项数，S为前n项和，d为公差，则张丘建的解法相当于
　　在其他算题中，张丘建还给出公式
　　容易验证，这些等差级数公式都是正确的．
　　《张丘建算经》的最后一题是闻名于世的“百鸡问题”；“今有鸡翁一，直(值)钱五；鸡母一，直钱三；鸡雏三，直钱一．凡百钱，买鸡百只，问鸡翁、母、雏各几何？”书中给出三组解：(1)鸡翁4，鸡母18，鸡雏78；(2)鸡翁8，鸡母11，鸡雏81；(3)鸡翁12，鸡母4，鸡雏84．至于解法，则只提到：“鸡翁每增四，鸡母每减七，鸡雏每益(增加)三，即得．”
　　这是一个不定方程问题．设鸡翁、鸡母、鸡雏的只数分别为x，y，z，则可列出方程组
　　(2)×3-1，得
　　14x ＋8y＝200，
　　即 7x＋4y＝100．(3)
　　显然，x＝0，y＝25是(3)的一组解．根据定理“若x＝x0，y=y0是整系数方程ax＋by＝c的一组整数解，则对任何整数t，x＝x0＋bt，y＝y0-at也是ax+by=c的解”，得
　　x＝4t，y＝25－7t，
　　代入(1)，得
　　z=100－4t－(25－7t)＝75＋3t．
　　当t＝1，2，3时，便得到《张丘建算经》中的三组解．实际上，符合题意的也只有这三组解．t每增1时，x便增4，y便减7，z便增3，这与张丘建对解法的提示是一致的．数论基础_文档下载_文档资料库
当前位置： >>
数论知识1什么是数论人们在对整数进行运算的应用和研究中，逐步熟悉了整数的特性。比如，整数可分为两大类―奇数和偶数等。利用整数的一些基本性质，可以进一步探索许多有趣和复杂的数 学规律，正是这些特性的魅力，吸引了古往今来许多的数学 家不断地研究和探索。 数论这门学科最初是从研究整数开始的，所以叫做整数 论。后来整数论又进一步发展，就叫做数论了。确切的说， 数论就是一门研究整数性质的学科。2数论的发展简况数论形成了一门独立的学科后，随着数学其他分支的发展，研 究数论的方法也在不断发展。如果按照研究方法来说，可以分 成初等数论、解析数论、代数数论和几何数论四个部分。 初等数论是数论中不求助于其他数学学科的帮助，只依靠初等 的方法来研究整数性质的分支。比如中国古代有名的“中国剩 余定理”，就是初等数论中很重要的内容。 解析数论是使用数学分析作为工具来解决数论问题的分支。数 学分析是以函数作为研究对象的、在极限概念的基础上建立起 来的数学学科。解析数论是解决数论中艰深问题的强有力的工 具。我国数学家陈景润在解决“哥德巴赫猜想”问题中也使用 的是解析数论的方法。3代数数论是把整数的概念推广到代数整数的一个分支。数 学家把整数概念推广到一般代数数域上去，相应地也建立 了素整数、可除性等概念。几何数论是由德国数学家、物理学家闵可夫斯基等人开创 和奠基的。几何数论研究的基本对象是“空间格网”。什 么是空间格网呢？在给定的直角坐标系上，坐标全是整数 的点，叫做整点；全部整点构成的组就叫做空间格网。由 于几何数论涉及的问题比较复杂，必须具有相当的数学基 础才能深入研究。 解决“庞加莱猜想”所用的方法就属于 几何数论。4哥德巴赫猜想哥德巴赫（）是德国数学家；曾在英国牛津大学学习；原学法学，由于在欧洲各国访问期间结识了贝努利家族,所以对数学研究产生了兴趣；曾担任中学教师。1725年到俄国， 同年被选为彼得堡科学院院士；1725年~1740年担任彼得堡科 学院会议秘书；1742年移居莫斯科，并在俄国外交部任职。在日给欧拉的信中，哥德巴赫提出了一个命题。5随便取某一个奇数，比如77，可以把它写成三个素数之和： 77 = 53+17+7再任取一个奇数，比如461，461= 449+7+5 也是三个素数之和，461还可以写成257+199+5，仍然是三个 素数之和。这样，我发现：任何大于5的奇数都是三个素数之 和。6欧拉回信说，这个命题看来是正确的，但是他也给不出严 格的证明。同时欧拉又提出了另一个命题：任何一个大于2的偶 数都是两个素数之和。但是这个命题他也没能给予证明。 不难看出，哥德巴赫的命题是欧拉命题的推论。事实上，任何一个大于5的奇数都可以写成如下形式：2N+1=3+2(N-1)，其中2(N-1)≥4. 若欧拉的命题成立，则偶数2(N-1)可以写成两个素数之和，于是 奇数2N+1可以写成三个素数之和，从而，对于大于5的奇数， 哥德巴赫的猜想成立。现在通常把这两个命题统称为哥德巴赫猜想7二百多年来，尽管许许多多的数学家为解决这个猜想付出了艰辛的劳动，迄今为止它仍然是一个既没有得到正面证明也没有被推翻的命题。十九世纪数学家康托（）耐心地试验了1000以内所 有的偶数，奥培利又试验了的全部偶数，他们都肯 定了在所试验的范围内猜想是正确的。 后来甚至有人一直验算到三亿三千万这个数，都肯定了猜想是正确的。81900年，德国数学家希尔伯特（~1943）在巴黎国际 数学家大会上提出了几十个研究题目。其中第二十三个最重要 的问题供二十世纪的数学家来研究。第八问题为素数问题；在提到哥德巴赫猜想时，希尔伯特说这是以往遗留的最重要的问题之一。1921年，英国数学家哈代（）在哥本哈根召开的数 学会议上说过，哥德巴赫猜想的困难程度可以和任何没有解决的数学问题相比。9近一百年来，哥德巴赫猜想吸引着世界上许多著名的数学 家，并在证明上取得了很大的进展。 苏联人什尼列尔曼()第一个取得了成果，他指出任何整数都可以用一些素数的和来表示，而加数的个数不超过800000。 1937年，苏联数学家维诺格拉夫（）取得了进一步 的成果，他证明了任何一个相当大的奇数都可以用三个素数的 和来表示。关于大偶数可表示为s个素数之积与t个素数之积的和的&s+ t&问题的研究进展情况如下：101920年，挪威的布龙证明了&9+9&； 1924年，德国的拉特马赫证明了&7+7&； 1932年，英国的埃斯特曼证明了&6+6&； 1937年，意大利的蕾西先后证明了&5+7&、&4+9&、&3+15& 和&2+366&； 1938年，苏联的布赫夕太勃证明了&5+5&，1940年他又证 明了&4+4&；1948年，匈牙利的兰恩尼证明了&1+C&，其中C很大；1956年，中国的王元（1930~ ）证明了“3+4”；1957年，他 又先后证明了“3+3”和“2+3”；111962年，中国的潘承洞（1934~ ）和苏联的巴尔巴恩证明了 “1+5”； 1962年，中国的王元证明了“1+4”；1963年，中国的潘承洞和苏 联的巴尔巴恩也证明了“1+4”； 1965年，苏联的布赫夕太勃和小维诺格拉夫及意大利的波波里 证明了D1+3‖； 1966后，中国的陈景润证明了&1+2&。最终将由哪个国家的哪位数学家攻克大偶数表为两个素数之和 （即&1+1&）的问题，现在还无法予测。12费马大定理17世纪的一位法国数学家，提出了一个数学难 题，使得后来的数学家一筹莫展，这个人就是费 马()。费马大定理，这个著名的猜想产生于1673年，费尔马在读丢蕃图《算术》时，在第二卷问题8的页边写下如下的注解： “分一立方数为两个立方数，分一个四次幂（或者一般地，任 何次幂）为两个同次幂，这是不可能的，我确实找到了一个极 妙的证明，但是页边太窄，写不下．”费尔马是否真有此问题 的一个完善的证明，也许将永远是个谜！13当n&2时，x n +y n = z n没有正整数解。在数学上这称为“费马大定理”。14? 费尔马对n=4的情况给出了一个证明? 欧拉给出了n=3的一个证明? 1825年，勒让德和狄利克雷独立地给出n=5的证明? 拉梅于1839年证明了n=7的情形 ?1908年，德国数学家佛尔夫斯克尔给哥廷根科学院留 下十万马克，作为第一个完全证明的奖金。 ? 1993年6月，牛顿研究所的著名数学家怀尔斯完成了 证明。 至此，这个历时357年的猜想被完美地解决了．15庞加莱猜想任何一个封闭的三维空间，只要它里面所有封闭曲线都可以收缩成一点，这个空间就一定是一个三维圆球――这就 是法国数学家庞加莱于1904年提出的猜想。 庞加莱猜想和黎曼假设、霍奇猜想、杨-米尔理论等一样， 被并列为七大数学世纪难题之一。2000年5月，美国的克莱数学研究所为每道题悬赏百万美元求解。16汉密尔顿在证明庞加莱猜想中有过杰出贡献。 俄罗斯数学家佩雷尔曼于2002年发表的两篇论文，为庞加莱猜想的 最终获证带来了曙光。获得2006年度素有数学界诺贝尔奖之称的菲 尔兹奖。 2006年，朱熹平和曹怀东运用汉密尔顿、佩雷尔曼的理论，第一次成 功处理了猜想中“奇异点”的难题，发表了300多页的论文，给出了庞加莱猜想的完全证明。17朱熹平教授和曹怀东教授在美国出版的《亚洲数学期刊》6月号以专刊的方式，刊载了长达300多页、题为《庞加莱猜想暨几何化猜想的完全证明：汉密 尔顿-佩雷尔曼理论的应用》的长篇论文。18素数分布费马数Fn = 22n+1, n = 0,1,2,…n = 0，1，2，3，4时，Fn是素数。 人们进而希望解决的问题是：是否存在着无限 多个费马素数。这也是一个至今未解决的难题。19整数的表示法带余除法: 设a, b是整数，b?0. 则a可唯一地表为a = bq+r其中q, r为整数并且0 ? r & |b|.20整数1987可以表示为：1?103 ? 9 ?102 ? 8 ?10 ? 7在计算机中，则常用以2为基，即二进制数。也可以用 其他整数作为基。定理 设m是大于1的正整数，则每一个正整数n可唯一表示：n ? ck mk ? ck ?1mk ?1 ? ?? c1m ? c021证明 用?x ?表示不大于x的最大整数。 设 n0 ? n, 令n1 ? ?n0 / m ?，则 n0 ? n1m ? c0 , 其中c0为余数 ? ? n j ?1 ? , j ? 1,2, ? , k ? 1 ?n ? 则有? j ? m ? ? ? ?n ? n ? 0 其中nk ?1 ? 0。于是有 n ? n1m ? c0 n1 ? n2 m ? c1 ? nk ?1 ? nk m ? ck ?1 nk ? nk ?1m ? ck ? ck22所以 n ? n1m ? c0 ? (n2 m ? c1 )m ? c0 ? (n3 m ? c2 )m 2 ? c1m ? c0 ?? ? ck m k ? ck ?1m k ?1 ? ? ? c2 m 2 ? c1m ? c0 下面证明表示法是唯一 的。 如若不然，设 n ? ck m k ? ck ?1m k ?1 ? ? ? c2 m 2 ? c1m ? c0 n ? d l m l ? d l ?1ml ?1 ? ? ? d 2 m 2 ? d1m ? d 0 由于 ck m k ? ? ? c1m ? c0 ? d l m l ? ? ? d1m ? d 023可得（ck m k ? ? ? c1m）－（d l m l ? ? ? d1m）＝d 0 ? c0 由于m整除左边，所以也应有 m | (d 0 ? c0 ) 而0 ? d 0 ? m, 0 ? c0 ? m, 所以必定有d 0 ? c0，从而上式变为 （c k mk ?1? ? ? c2 m）－（d l ml ?1? ? ? d 2 m）＝d1 ? c1由此又可得 m | (d1 ? c1 )，即d1 ? c1 依此类推，可知 k ? l , d i ? ci , i ? 0,1,2, ? , k 所以，n以m为基的表示法是唯一的 。24例如：n ? 389, m ? 5n0 ? n ? 389, n1 ? ?389/ 5? ? 77, c0 ? 4 n2 ? ?n1 / 5? ? ?77 / 5? ? 15, c1 ? 2 n3 ? ?n2 / 5? ? ?15 / 5? ? 3, c2 ? 0 n4 ? ?n3 / 5? ? ?3 / 5? ? 0, c3 ? 3 3 故 389 ? 3 ? 5 ? 2 ? 5 ? 425数的因数分解整除、素数、合数、因数、公因数 、倍数、 公倍数 互素 最大公因数 (greatest common divisor) gcd. 最小公倍数 (least common mutiple) lcm.26引理如果 r 是一正整数，那么gcd(r, 0)=r.定理1 若a = bq + r，则gcd {a, b} = ? gcd {b, r}注意：gcd {a, b} 又可以表示为(a, b)27证明： 设 d = ( a, b ), d’ = ( b, r )，则 d | (a - bq), 即d | r 所以 d 是 b 和 r 的公因数，即 d | d’。 类似地，由 d’ | ( bq + r) 得 d’ | a, 所以 d’ | d 所以 d = ? d’即gcd {a, b} = ? gcd {b, r}28定理2 每一双不全为0的整数，必有一个正的最大公因数证明：不失一般性，设 a 和 b 为正整数，且a & b。 令 a = b q + r, 0 ≤ r & b，由定理1可得： ( a, b ) = ( b, r ) 又令 b = r q1 + r1, 0 ≤ r1 & r，则：( a, b ) = ( b, r )＝ ( r, r1)依次类推，直到余数为0。这样存在一个整数k，使得 rk-2 = rk-1 qk + rk, rk ≠ 0rk-1 = rk qk+1(注意：rk+1 = 0 )对于这个序列有 r1 & r2 &… & rk & 0，且 ( a, b ) = ( b, r ) = ( r, r1) =…= (rk-1 , rk ) = rk所以 rk 是 gcd {a, b}。29上面定理的证明过程就是求解 gcd{a, b}的步骤。 例：求 gcd{726, 393}726＝1×393＋333393＝1×333＋60333＝5×60＋3360＝1×33+2733＝1×27+627 ＝ 4×6+3 6 ＝ 2 ×3+0 所以，gcd{726,393}=330定理3 若d = gcd{a, b}，则存在整数 p 和 q，使得d = pa + qb证明：由定理2的证明可得 rk = -qk rk-1 ＋rk-2 rk-1= -qk-1 rk-2 ＋rk-3……r1 = - q 1 r + b r = - qb + a 依次消去 r, r1 , r2 ,…, rk-1 ，可得 d = rk = pa + qb31例：gcd{726, 393}=33 = 27 - 4×6= 27 - 4×(33-27)= -4×33+5×27= -4×33+5×(60-33) = 5×60-9×33= 5×60-9×(333-5×60) = -9×333+50×60= -9×333+50×(393-333) = 50×393-59×333=50×393-59×(726-393) =-59×726+109×39332特别地如果 a 和 b 互素，存在整数p和q，有pa + qb = 133? 欧几里得算法计算两个数的最大公因子 gcd{n1 , n 2 } ，最容易的 方法是欧几里得算法。欧几里得在公元前300年所描述的算法是幸存到现在最古老的非凡算法。使用欧几里得算法求 gcd 的算法步骤：step 1 求 q 及 r，使 n1 ? qn2 ? r。 step 2 若 r ? 0，则：(n1 ? n2 )g ? n2 , 输出g , 结束；否则转 step 3。 step 3 n1 ? n2 , n2 ? r , 转step 1。34例如，要计算gcd{156,117} 156 ? 1?117 ? 39 117 ? 3 ? 39 ? 0 所以：gcd{156,117} ? 39in1156117n211739rg12390 3935算法关键：?a , gcd( a, b) ? ? ?gcd(b, a %b), lcm(a, b) ? (a * b) / gcd( a, b)当b ? 0 当b ? 036int gcd(int x, int y) { if (x&0) x= -x; if (y&0) y= -y; if (x+y==0) { printf(Derror!‖); return 0; } while (x&0) { g = x=y% y=g; } }该算法可扩展为求m个数的gcd int multiple_gcd(int m, int *x) { int g, if (m&1) return 0; g = x[0]; for(i=1;i&m;i++) { g=gcd (g,x[i]); if (g = =1) return 1; } }37定理4 若a|bc, (a, b)=1，那么a|c.推论 若素数p整除a1a2…an，则存在k, 1?k?n,使得p|ak. 定理 5 每一个正合数可表为若干个素数的积， 并且若不考虑素数在积中的顺序则此表示是唯 一的.c ? p1 p2 ? pna1 a2an38定理5证明：若 c 是合数，则存在 a 和 b，使得 c = a b； 若 a 和 b 是合数，可设 a = a1a2， b＝b1b2；从而c=a1a2b1b2; 继续以上步骤，直到不能再分解因子为止。这个过程可以在 有限步内完成，故有 c = p1 p2… pn 若这个分解不是唯一的，设 c = q1 q2… qm 那么 p1 p2… pn = q1 q2… qm 。 素数 p1| q1q2…qm，故存在 qi, p1|qi,因此p1= qi。不妨设p1=q1， 由p1≠0，则有 p2… pn = q2… qm 。继续该步骤，直到取尽 所有的pi为止。所以 n = m。 显然，若c有素数因子p1, p2,…, pn ，则有 c = p1a1p2a2…pnan同余类设m&1为整数，a, b为任意整数. 如果 a = b + k.m (k 为一个整数) 即：m|(a?b) 则称a和b模m同余，记为（称为同余式） a ? b mod m40定理1 模n同余关系满足：（1）自反性，即a ? a mod m（2）对称性，若a ? b mod m, 则 b ? a mod m（3）传递性，若a ? b mod m, b ? c mod m则： a ? c mod m41定理2 若a ? b mod m, c ? d mod m, 则： （1）a ± c ? b ± d mod m （2）ac ? bd mod m 证明： a ? b mod m, c ? d mod m, 所以 a = km + b, c = hm + da ±c = (k ±h)m + (b ±d )从而 a ±c = b ±d mod m同理可证： ac ? bd mod m42定义:设m&1为整数, a为任意整数. 如果存在整数b 使得 ab ?1 mod m 则称b为a 模m的逆元，记为 b ? a?1 mod m 定理 3 若(a, m) =1, 则a?1 mod m 存在.证明：因为(a, m) =1，则存在整数p, q，使得pa + qm = 1 即有 所以 pa ? 1 mod m a?1 ＝p43例：m = 35, u = 13, 求u-1因为 35 = 2×13+9 13 = 1×9 + 4 9 = 2×4 + 1 4 = 4×1 + 0 显然 1 = (35, 13) = 9- 2×4 = 9- 2×(13- 1×9) = 3×9-2 ×13 = 3×(35-2×13)-2×13 = 3×35-8×13 所以 u-1 =-8 mod 35 = 2744定理 4 模运算是可交换、可结合、可分配的。(a ? b) mod n ? (( a mod n) ? (b mod n)) mod n (a ? b) mod n ? (( a mod n) ? (b mod n)) mod n (a ? b) mod n ? (( a mod n) ? (b mod n)) mod n (a ? (b ? c)) mod n ? ((( a ? b) mod n) ? (( a ? c) mod n)) mod n45密码学中经常用到大数的模指数运算：a mod n将导致一系列乘法和除法运算，但可以加速运算方 法，以减少模乘法运算的次数。例如，要计算 8 modn，不要直接计算七次乘 a 法： (a ? a ? a ? a ? a ? a ? a ? a) modn 相反，可以进行三次乘 (模平方)运算： 法 ((a 2 modn) 2 modn) 2 modn 当模指数为奇数时 尽量把指数变为偶数的 , 形式, 这 时有可能出现两个指数 1的情况, 应把该两个数做一次 为 模乘法运算变为一个数然后再做模平方运算 , .46x例如，要计算：13 P ? 1520 mod2537 ? (?1 (mod2537) 2 ? (1520 ) 6 ?1520(mod2537)由于： 15202 ? 1730mod2537 ? P ? (20(mod2537) ? (120(mod2537) 由于： 17302 ? 1777mod2537 ? P ? (20(mod2537) ? (17772 ? ( )(mod2537) ? (1)(mod2537) ? ()(mod2537) 所以： ? ()(mod2537) ? 95 P47计算 x r mod n 的算法输出ca?x b?r c ?1= b=0??b (mod2)=0?=b?b/2 a ? a 2 (mod n)?b ? b ?1 c ? ac(mod n)48unsigned long qe2(unsigned long x, unsigned long r, unsigned long n) { unsigned long a, b, c=1; a = b = while (b) /* b非0，则继续处理*/ { if (b&1) /*表示指数为奇数*/ c=(c*a) %n; /*把两个指数为1的数相乘，变为一个数*/ b&&=1; /*指数除以2*/ a=(a*a) %n; } }main() { unsigned long a = 1520, b =13, n=2573, congruent=qe2 (a, b, n); printf (DResult is: %ld‖, congruent); }49欧拉函数用 Z n 来表示模n的整数集 {0,1,2, ? , n ? 1} 比如，Z 25 ? {0,1,2,?,24}欧拉函数?(n)表示在区间[1, n] 中与n互素的数目。 欧拉函数有以下性质： (1) 如果n是素数，则?(n) ? n ? 1 (2) 欧拉函数是一个积性函 数，也就是说，如果 gcd( m, n) ? 1， 则?(m n) ? ?(m)?(n) 比如，?(5) ? 4，?(6) ? 250定理1 (Euler) 若a与m互素，则 a?(m) ?1 mod m推论 (Fermat) 若p是素数,(a, p)=1, 则 ap?1 ?1 mod p 定理2 (Fermat) 若p是素数，则 a p ? a mod p故当p是素数，则 a?1?a p?2 mod p51欧拉函数的应用RSA加密算法的基本思想 1、产生公钥 选择两个大素数p和q，使n = p q? (n) ? ( p ? 1)(q ? 1)选择一个正数e，使其满足：将KP = (n, e)作为公钥公布。 2、私钥的产生 求出正数d 使其满足：(e, ? (n)) ? 1e ? d ? 1 mod? (n)将KS = (d, p, q)作为私钥保留。523、加密过程 将明文 M 作变换：C ? EKp (M ) ? M e modn从而得到密文C。4、解密过程 将密文C作变换： M ? DKs (C) ? C modnd从而得到明文M。53RSA使用举例假设用户B取两个素数p = 11，q = 13，计算n = p q = 143，? (n) ＝120 再选一个与 ? (n) = 120互素的数，例如e = 7，并计算d=103使其满足 e d =1 mod ? (n) ，则（143，7）就是用户B的公钥，（11，13，103）就是用户B的私钥。 假设用户A想发送明文M = 85给用户B，A首先从公开媒体得到B的公 钥（143，7），于是A作加密运算得到密文C=85 mod 143 =123，B收7到密文C=123后，利用自己知道的私钥d =103做解密运算得到明文M=123103mod 143=85。54威尔森定理定理 (Wilson) 若p是素数，则(p?1)!? ?1 mod p 反之，如果整数p满足上式， 则 p是素数.55线性同余式来自《孙子算经》的问题：“今有物不知其数, 三三数之剩二, 五五数之剩三, 七 七数之剩二, 问物几何?”如设 x 为其数，则有：? x ? 2 mod 3 ? ? ? x ? 3 mod 5 ? ? x ? 2 mod 7 ?一般地，称 ax ? b mod m 为线性同余式.56? 中国剩余定理（孙子定理）假设m1 , m2 ,?, mr 是两两互素的 个整数，a1 , a2 ,?, ar 是r个 r 任意整数，则 个同余方程组： r x ? a1 modm1 x ? a2 modm2 ? x ? ar modmr 模M ? m1m2 ? mr 有唯一解。其解为： x ? ? ai M i yi modMi ?1 r其中，M i ? M / mi , yi ? M i modmi ,1 ? i ? r57?1举例说明： x ? 1 mod 2, x ? 3 mod 5,x ? 2 mod 3 x ? 5 mod 7M ? 2 ? 3 ? 5 ? 7 ? 210 M 1 ? 105, M 2 ? 70, M 3 ? 42, M 4 ? 30 M 1 y1 ? 1 mod 2 ? y1 ? 1 M 2 y 2 ? 1 mod 3 ? y 2 ? 1 M 3 y 3 ? 1 mod 5 ? y 3 ? 3 M 4 y 4 ? 1 mod 7 ? y 4 ? 4 x ? 105 ? 1 ? 1 ? 70 ? 2 ? 1 ? 42 ? 3 ? 3 ? 30 ? 5 ? 4(mod 210) ? 173mod21058平方剩余考虑下列同余式 x ? 1, x ? 2, x ? 3, x ? 4 mod52 2 2 2不难发现 x ? 1, x ? 4满足x 2 ? 1 mod5 x ? 2, x ? 3满足x 2 ? 4 mod5 不存在整数满足 x ? 2 mod5或x ? 3 mod52 2定义1：x2 ≡ a mod p，其中a与p互素，且 p 是奇素 数。若问题有解，则称a是模p的平方剩余，否则称 为非平方剩余。59引理 若p是奇素数, p与a互素, 则 x2 ? a mod p 或无解, 或有两个模 p 不同余的解. 并且,如果1?x?&p是一解, 则 另一解为 p?x?.定理 1 若p是奇素数, 则1, 2, …, p?1正好有 (p?1)/2个是模p的平方剩余。 且12, 22, …, [(p?1)/2]2为其平方剩余。60比如上例中 x ? 1, x ? 2, x ? 3, x ? 4 mod52 2 2 2不难发现 x ? 1, x ? 4满足x ? 1 mod52x ? 2, x ? 3满足x ? 4 mod52即有( p ? 1) / 2 ? 2个平方剩余，分别是： 1 ＝ ， ＝4 1 22 261?a? 定义2：a 与 p互素，且 p 是奇素数。引进符号? ? ? p? ? ?称为勒让德(Legendre)符号：? a ? ? 1 若a是模p的平方剩余 ? ??? ? p? ? ? ?? 1 若a不是模p的平方剩余例：取p ? 7 12 ? 1 mod 7, 2 2 ? 4 mod 7, 32 ? 2 mod 7 4 2 ? 2 mod7, 52 ? 4 mod 7, 6 2 ? 1 mod 7 ?1? ?2? ?4? 所以 ? ? ＝ ? ? ＝ ? ? ＝1 ?7? ?7? ?7? ?3? ?5? ?6? ? ?＝? ?＝? ?＝?1 ?7? ?7? ?7?定理2( Euler)：令p是一奇素数，则 ?a? ( p ?1) / 2 ? ??a mod p ? p? ? ??a? 2 证明：若? ?＝ ，即x ? a mod p有解。 ? p? 1 ? ? 设解为x，利用Ferm at 定理有 a( p ?1) / 2? (x ) ?xp ?12 ( p ?1) / 2? 1 mod p63从而此时定理为真。?a? 若? ?＝ ? 1，即x 2 ? a mod p无解。对于每一个 ? p? ? ? 整数i : 1 ? i ? p ? 1, 总对应一个j，使得 ij ? a mod p 由于x 2 ? a mod p无解，故i ? j。因此1， ?，p ? 1 2， 可以分成( p ? 1) / 2对，每一对之积为 。因此 a ( p ? 1)!? a ( p ?1) / 2 mod p Wilson定理告诉我们 ( p ? 1)!? ?1 mod p ?a? 所以， ? ? ? a ( p ?1) / 2 mod p ? p? ? ? 例：p ? 23, a ? 5,511 ? ?1 mod23, 所以5不是模23 的平 方剩余。定理3：若p是一奇素数, a和b与p互素，则 ?a? ?b? (1) 若a ? b mod p, 则 ? ? ? ? ? ? p? ? p? ? ? ? ? ? a ?? b ? ? ab ? (2) ? ?? ? ? ? ? ? p ?? p ? ? p ? ? ?? ? ? ? ?a (3) ? ? p ?2? ? ?1 ? ?65证明： ?a? ( p ?1) / 2 (1) ? ? ? a mod p, ? p? ? ? ?b? ( p ?1) / 2 ? ??b mod p ? p? ? ??a? ?b? ? a ? b mod p, ? ? ? ? ? ? mod p ? p? ? p? ? ? ? ? 由于Legendre 符号只能为? 1， ?a? ?b? 故? ? ?? ? ? p? ? p? ? ? ? ?66证明： ?a? ?b? ( p ?1) / 2 (2) ? ? ? a mod p, ? ? ? b ( p ?1) / 2 mod p ? p? ? p? ? ? ? ? ? a ?? b ? ? ab ? ( p ?1) / 2 ( p ?1) / 2 ( p ?1) / 2 ? ?? ? ? a b ? (ab) ? ? ? mod p ? p ?? p ? ? p? ? ?? ? ? ? ? a ?? b ? ? ab ? 由于Legendre 符号只能为? 1，故? ?? ? ? ? ? ? p ?? p ? ? p ? ? ?? ? ? ? ? a2 ? ?a? (3) 因? ?＝ ? 1，故? ? ? 1 ? p? ? p? ? ? ? ?67代数知识? 群的概念定 义 1 给定一个集合 和该集合上的运算*，满足下列四条件 G 的代数系统 ? G, * ? 称为群： 1、封 闭 性 ：若a, b ? G, 则存在c ? G, 使a * b ? c(即G ? G ? G ) 2、结 合 律 ：若a, b, c ? G, 则恒有(a * b) * c ? a * (b * c) 3、存 在 单 位 元 素：存在e ? G, 对?a ? G, 恒有a * e ? e * a ? a e 4、存 在 逆 元 素 ：对?a ? G, 恒有b ? G使a * b ? b * a ? e，元素 b称为a 的逆元素，用 ?1表示，即b ? a ?1。 a 若?a, b ? G, 有a * b ? b * a, 则称 ? G, * ? 为阿 贝 尔 群 (交 换 群 或 加 法 群.)69例1 : G ? {1,?1}在乘法运算下构成群而且是阿贝尔群. , 封闭性：(1)(-1) ?(-1)(1) ? -1, (1)(1) ? 1, (-1)(-1) ? 1 结合律：显然成立. 单位元e ? 1. 逆元素：1 的逆元为 ,?1的逆元为? 1. 1例2 G＝{0,1, 2, …, n-1}，关于mod n 的加法是一个阿贝尔群。(a)封闭性: a∈G, b∈G, (a+b) mod n 只能在G中。(b) 结合律显然成立。(c) 单位元 e = 0。(d) a ∈ G, a-1 = n-a, a+a-1 = n ≡ 0 mod n例3 G＝{1, 2, …, p-1}，p是一素数，则mod p关于乘法构成阿贝尔群。(a)封闭性: a ∈ G, b ∈ G, ab＝ba mod p∈G。 (b)结合律显然成立。 (c)单位元 e = 1。 (d) a ∈ G, gcd (a, p) =1, 故存在整数 l 和 m 使 l a + m p=1, 故 la ≡ 1 mod p, l = a-1定 义 2 如果 | G | 是有限的，那么称群 G 为有限群。一个有限群 的元素个数称为 它的阶。73例1 剩余类集Z n 关于模 n 加法形成一个阶为 的 ： n 阿贝尔群， n 关于模n乘法不是一个 。然而， Z 群 当 n 为素数时，Z n 关于模n乘法形成一个阶为 n ? 1的阿贝尔群。 封闭性：a ? Z n ,b ? Z n ,ab ? ba ? Z n .* * * *结合律成立，而且ab ? ba modn. 单位元e ? 1. 逆元素：由于n为素数，则a n ?1 ? 1 modn ? a ?1 ? a n ? 2 modn.定 义 3 一个环(G,?,?)是由满足下列条件的G上的二元 运算“?”称为加法)和“?”称为乘法)构成： ( ( 1、(G,?)是一个阿贝尔群，单位元用0表示。 2、运算“?”是可结合的，若 , b, c ? G, 则有 a (a ? b) ? c ? a ? (b ? c) 3、有一个乘法单位1 1 ? 0，对?a ? G, 恒有 ， a ?1 ? 1? a ? a（对乘法存在单位元） 4、满足分配律：对 , b, c ? G, 有 a a ? (b ? c) ? (a ? b) ? (a ? c) (b ? c) ? a ? (b ? a ) ? (c ? a)75若环(G,?,?)还满足条件：对所有 , b ? G , 有 a a ? b ? b ? a, 则称环(G ,?,?)为交换环。 . 例 : 整数集Z关于普通的加法和乘法 运算构成一个 交换环. 例 : Z n 关于模n加法和乘法运算构成一 个交换环.定 义 4 满足下列条件之一的一 个交换环称为域：所有 的非零元素都有 乘法逆。例 : 整数环Z不是一个域，因为只有和 ? 1有乘法逆元。然而，有 1 理数集Q、 实数集R关于普通的加法和乘法 运算构成一个域 . 例 : Z n 关于模n加法和乘法是一个域用GF (n)表示)，当且仅当n是素数. (*?1 2 3 41 2 3 4 1 2 3 4 2 4 1 3 3 1 4 2 4 3 2 1?1 2 3 4 51 2 3 4 5 1 2 3 4 5 2 4 0 2 4 3 0 3 0 3 4 2 0 4 2 5 4 3 2 1Z5中每个非0元素都有逆元Z6中并非每个非0元素都有逆元77? 生成元（本原元）p是一个素数, 如果Z p中有一个元素 使得对每一个 ? b ? Z p 都有一个整数 使得b ? ? i m odp , 称?为Z p的一个生 i 成元( generator 或本原元( prim itive ) ). 例如, p ? 11, 则 2就是Z 11的生成元. 210 ? 1m od11 2 2 ? 4m od11 2 7 ? 7m od11 2 5 ? 10m od11 显然, 对Z 11而言,2,6,7,8是生成元.7821 ? 2m od11 2 4 ? 5m od11 2 3 ? 8m od112 8 ? 3m od11 2 9 ? 6m od11 2 6 ? 9m od11假设{q1 , q2 , ? , qn }是p ? 1的素因子集合 判断g为Z p , 生成元的步骤如下: g(p -1)/qmod pq ? {q1 , q2 , ? , qn }若对q的某个值, 上式结果为 , 则g不是生成元 若对 1 ; 任意q, 上式结果不为 , 则g是生成元。 1例如, p ? 11, p ? 1 ? 10的 素因子是 2 和 5 2(11-1)/5 ? 4m od11 3(11-1)/5 ? 9m od11 则3不是生成元。792(11-1)/2 ? 10m od11 3(11-1)/2 ? 1m od11没有一个结果为 则2是生成元。 1,椭圆曲线知识椭圆曲线密码学（ECC, Elliptic curve cryptography）是基于椭 圆曲线数学的一种公钥密码的方法。椭圆曲线在密码学中的使 用是在1985年由Neal Koblitz和Victor Miller分别独立提出的。ECC的主要优势是在某些情况下它比其他的方法使用更小的密 钥――比如RSA――提供相当的或更高等级的安全。ECC的另 一个优势是可以定义群之间的双线性映射，基于Weil对或是 Tate对；双线性映射已经在密码学中发现了大量的应用，例如基于身份的加密。不过一个缺点是加密和解密操作的实现比其他机制花费的时间长。81平行线平行线，永不相交。 所以“平行线，永不相交”只是假设。既然可以假设平行线永不相交，也可以假设平行线在很远很远的地方相交了。 即平行线相交于无穷远点P∞。平行线直线上出现P∞点，所带来好处是所有的直线都相交了，且只有一个交点。这就把直线的平行与相交统一了。为与无穷远 点相区别把原来平面上的点叫做平常点。以下是无穷远点的几个性质。? 直线L上的无穷远点只能有一个。 ? 平面上一组相互平行的直线有公共的无穷远点。 ? 平面上任何相交的两直线L1,L2有不同的无穷远点。 ? 平面上全体无穷远点构成一条无穷远直线。? 平面上全体无穷远点与全体平常点构成射影平面。射影平面坐标系射影平面坐标系是对普通平面直角坐标系(笛卡儿坐标系)的 扩展。我们知道普通平面直角坐标系没有为无穷远点设计坐 标，不能表示无穷远点。为了表示无穷远点，产生了射影平 面坐标系，当然射影平面坐标系同样能很好的表示旧有的平 常点。射影平面坐标系对普通平面直角坐标系上的点A的坐标（x, y）做如下改造： 令 x = X/Z , y = Y/Z (Z≠0) 则A点可以表示为(X:Y:Z)变成了有三个参量的坐标点，这就对 平面上的点建立了一个新的坐标体系。 例: 求点(1,2)在新的坐标体系下的坐标。 解：∵X/Z=1 ，Y/Z=2（Z≠0）∴X=Z，Y=2Z∴坐标为（Z:2Z:Z），Z≠0。 即(1:2:1) (2:4:2) (1.2:2.4:1.2)等形如(Z:2Z:Z), Z≠0的坐标，都是点(1,2)在新的坐标体系下的坐标。射影平面坐标系在射影平面坐标系的直线方程为： aX+bY+cZ=0 如何在新的坐标体系能够表示无穷远点么？假设两条平行直线 的方程是： aX+bY+c1Z =0； aX+bY+c2Z =0 (c1≠c2) 将二方程联立，求解得到： c2Z = c1Z= -( aX+bY ) ∵c1≠c2 ∴Z=0 aX+bY=0； 所以无穷远点就是这种形式(X:Y:0)表示。注意，平常点Z≠0，无穷远点Z=0，因此无穷远直线对应的方程是Z=0。射影平面坐标系例: 求平行线L1:X+2Y+3Z=0 与L2:X+2Y+Z=0 相交的无穷远点。 解：因为L1∥L2 所以有Z=0， X+2Y=0；所以坐标为(-2Y:Y:0)，Y≠0。即(-2:1:0) (-4:2:0) (-2.4:1.2:0)等形如(-2Y:Y:0),Y≠0的坐标都表示这个无穷远点。 看来这个新的坐标体系能够表示射影平面上所有的点，我们 就把这个能够表示射影平面上所有点的坐标体系叫做射影平面坐 标系。椭圆曲线的基本概念所谓椭圆曲线指的是维尔斯特(Weierstrass)方程。8889椭圆曲线的映射变换注意：无穷远点可理解为沿着 y 轴趋向无穷远。9091椭圆曲线判别式92椭圆曲线上的运算93实际上，点P+Q与点R关于x轴对称。由3.11式中只包含y2项 可知。提醒大家注意一点，以前提供的图像可能会给大家产 生一种错觉，即椭圆曲线是关于x轴对称的。事实上，椭圆 曲线并不一定关于x轴对称。95例：椭圆曲线E为： ? x ? a4 x ? a6 y2 3(1)过P ( x1 , y1 )和Q( x2 , y2 )的直线L设为( P ? Q)： y ? kx ? b y2 ? y1 其中 k ? , b ? y1 ? kx1 x2 ? x1 以此代入曲线E的方程得： (kx ? b) 2 ? x 3 ? a4 x ? a6 即 x ? (kx ? b) ? a4 x ? a6 ? 03 2由于x1 , x2是它的两个根，若 直线交曲线E于 PQ 点R＝( x3 , y3 ), 根据根与系数的关系 x1 ? x2 ? x3 ? k2所以 x3 ? k 2 ? x1 ? x2 , y3 ? kx3 ? b 若 P ? Q＝( x* , y * ) ? ( x3 ,? y3 ) ? ( x3 ,?(kx3 ? b)) 即 y2 ? y1 2 ? * ? x ? x3 ? ( x ? x ) ? x1 ? x2 ? 2 1 ? y2 ? y1 * ? y ? ? y1 ? ( )(x1 ? x3 ) ? x2 ? x1 ?(2) 当P＝Q时： F(x,y)? y 2 ? x 3 ? a4 x ? a6 Fx ( x, y ) ? ?3x ? a42Fy ( x, y ) ? 2 y k ? F ( x, y ) ? ? Fx ( x, y ) / Fy ( x, y )'? (3x 2 ? a4 ) /(2 y ) x3 ? k ? x1 ? x12y3 ? ? y1 ? k ( x1 ? x3 )点加法则详解：▲ 这里的+不是实数中普通的加法，而是从普通加法中抽象出 来的加法，他具备普通加法的一些性质，但具体的运算法则显 然与普通加法不同。 ▲根据这个法则，可以知道椭圆曲线无穷远点O∞与椭圆曲线上一点P的连线交于P’，过P’作y轴的平行线交于P，所以有 无穷远点 O∞+P = P 。这样，无穷远点 O∞的作用与普通加法中 零的作用相当（0+2=2），我们把无穷远点 O∞ 称为零元。同 时我们把P’称为P的负元 (简称，负P；记作，-P)。 （参见下图）99▲ 根据这个法则，可以得到如下结论：如果椭圆曲线上的三个点A、B、C，处于同一条直线上，那么他们的和等于零元，即 A+B+C = O∞100▲ k个相同的点P相加, 我们记作k P。如下图:P+P+P = 2P+P = 3P101102103椭圆曲线的阶定义：P是椭圆曲线E上的一点，若存在最小的正整数n，使得 nP = O，其中O是无穷远点，则称n是P点的阶。当然，不一定 都存在有限的n，但我们感兴趣的求椭圆曲线E上有限阶的点， 特别是定义在有限域上的椭圆曲线。例：已知曲线E的方程是：y 2 ? x 3 ? 1。曲线E在P＝(2,3) 的切线斜率为 dy 3x 2 |P ? |( 2,3) ? 2 dx 2y 曲线E在点P的切线方程为： y ? 3 ? 2( x ? 2) 所以 y ? 2 x ? 1 ，以y ? 2 x ? 1代入曲线方程得 (2 x ? 1) 2 ? x 3 ? 1, x 3 ? 4 x 2 ? 4 x ? 0, x( x ? 2) 2 ? 0 故切线y ? 2 x ? 1交曲线E于另一点(0,?1)或2 P ? (0,1). 下面求2 P ? 2 P点，方法和前面类似。 过 2 P点的切线方程为： ? 1 ? 0，即y ? 1 y以y ? 1代入椭圆曲线E的方程得x ? 0，即 切线y ? 1交E于(0,1)点，故： 4 P ? (0,?1) 过 4 P＝(0,?1)和2 P ? (0,1)引连线L：x ? 0。 L交E于另一点O，故6 P＝O密码学中的椭圆曲线前面学到的椭圆曲线是连续的，并不适合用于加密；所以，我 们必须把椭曲线变成离散的点。因此，我们要把椭圆曲线定义 在有限域上。 下面，我们给出一个有限域Fp，这个域只有有限个元素。Fp中只有p（p为素数）个元素0,1,2 ?? p-2,p-1；加法法则: a + b ≡ c (mod p) 乘法法则: a × b ≡ c (mod p) 除法法则: a / b ≡ c (mod p)；即 a×b-1 ≡ c (mod p)并不是所有的椭圆曲线都适合加密。但是， y2 = x3 + ax + b (1) 是一类可以用来加密的椭圆曲线，也是最为简单的一类。 下面我们就把y2 = x3 + ax + b 这条曲线定义在Fp上： 选择两个满足下列条件的小于p的非负整数a、b 4a3+27b2 ≠0 (mod p)则满足方程(1)的所有点(x, y)，再加上 无穷远点O∞ ，构成一条椭圆曲线。 其中 x, y属于0到p-1间的整数，将这条椭圆曲线记为Ep (a, b)。例子：F23上的一个椭圆曲线 令y2=x3+x+1是F23上的一个方程(a=b=1)，则该椭圆曲 线方程在F23上的解为(y2=x3+x+1的点)： (0,1)，(0,22)，(1,7)，(1,16)，(3,10)，(3,13)，(4,0)，(5,4)，(5,19)，(6,4)，(6,19)，(7,11)，(7,12)，(9,7)，(9,16)，(11,3)，(11,20)，(12,4)，(12,19)，(13,7)， (13,16)，(17,3)，(17,20)，(18,3)，(18,20)，(19,5)， (19,18)； O∞ 。 群E23(1,1)有28个点（包括无穷远点O∞ ）。109例: 已知E23(1,1)上两点P(3,10),Q(9,7), 求1)-P, 2)P+Q, 3) 2P。 解: 1) CP的值为(3,-10) 2) k=(7-10)/(9-3)=-1/2，2的乘法逆元为12 因为2*12≡1 (mod 23)k ≡ -1*12 (mod 23)故 k=11。x = k2-x1-x2 = 121-3-9 =109 ≡17 (mod 23); y = -y1+k(x1-x3) = 11(3-17)-10=89≡20 (mod 23) 故P+Q的坐标为(17,20) 3) k= (3x2+1)/(2y)=(3*32+1)/(2*10)=7*5-1 = 7*14 ≡ 6 (mod 23) x = k2-x1-x1 = 62-3-3=30≡7 (mod 23) y = k (x1-x3)-y1 = 6(3-7)-10 = -34 ≡ 12 (mod 23)故2P的坐标为(7,12)110椭圆曲线的离散对数问题
椭圆曲线上简单的加密/解密现在我们描述一个利用椭圆曲线进行加密通信的过程： 1、用户A选定一条椭圆曲线 Ep (a, b)，并取椭圆曲线上一点， 作为基点G。 2、用户A选择一个私有密钥k，并生成公开密钥 K = k G。 3、用户A将Ep ( a, b)和点K,G传给用户B。 4、用户B接到信息后 ，将待传输的明文编码到Ep (a, b)上一点 M（编码方法很多），并产生一个随机整数r（r & n）。 5、用户B计算点C1 = M + rK；C2 = rG。 6、用户B将C1、C2传给用户A。 7、用户A接到信息后，计算C1 - kC2，结果就是点M。因为 C1 - kc2 = M + rK - k(rG) = M + rK - r(kG) = M113椭圆曲线上简单的加密/解密在这个加密通信中，如果有一个偷窥者H ，他 只能看到Ep (a, b)、K、G、C1、C2 而通过K、G 求k 或通过C2、G求r 都是相对困难的。因此，H 无法得到A、B间传送的明文信息。114密码学中，描述一条Fp上的椭圆曲线，常用到六个参量： T = (p, a, b, G, n, h) 其中p 、a 、b 用来确定一条椭圆曲线，G为基点，n为点G的 阶，h 是椭圆曲线上所有点的个数m与n相除的整数部分。 参量值一般要求满足以下几个条件： 1、p 当然越大越安全，但越大，计算速度会变慢，200位左右 可以满足一般安全要求； 2、p≠n×h； 3、pt≠1 (mod n)，1≤t &20； 4、4a3+27b2≠0 (mod p)； 5、n 为素数； 6、h≤4。115