密码学数学基础第三讲 同余式2).pdfVIP

第三讲 同余式 （2） 教师：李艳俊 联系方式 本讲内容 一 d-1(mod n)的解法 二 一次同余式求解 三 线性方程组求解 一、d-1(mod n)的解法 一次同余式 ax bmodn 首先考虑b=1的情形，即 ax 1modn 1 x是Zn 中与a互逆的值，记为 x a modn 乘法逆元的定义及性质 1) 逆元：设a是模n的剩余类环Z 中的一个元素，即a∈Z , n n 如果存在x∈Z 使得ax≡1 (mod n), 那么我们就说a是可逆的， n 称x为a的模n的乘法逆元，简称逆元。 例1：1模26的逆元还是1。 例2：9是3模26的逆元。 2) 逆元是相互的，x是a的逆元，则a也是x的逆元。 例： 9是3模26的逆元，则3也是9模26的逆元。 3) 模n的剩余类环Z 中的任意元素a是可逆的充要条件是a n 与n互素，即 (a,n)=1 。 例3 ：Z26 中的可逆元有1、3、5、7、9、11、15、17、 19、21、23、25 。 –1 4) 如果a是可逆的,则其逆元是唯一的,记为a 。 5) Zn 中共有Φ(n)个可逆元。 练习：试求Z18中的可逆元个数。 Z 中元素逆元的求法： n 回忆 辗转相除法： 设a =n,a =d，辗转做带余除法得 0 1 a =q a +a ，i=1,,k i-1 i i i+1 其中k使0=a a a 。 k+1 k 1 方法1 推导出求递推矩阵： 0 1  a ai i1 ai1 ai   1 qi  不难看出 0 1 0 1 0 1 u        i              a a a a a a  n d i i1 i1 i   i2 i1      1 qi 1 qi11 qi v i  于是，可设a un+vd，i=1, ,k 。