《【2017年整理】第四章 (7) 同余式、一次同余式、孙子定理》由会员分享，可在线阅读，更多相关《【2017年整理】第四章 (7) 同余式、一次同余式、孙子定理（49页珍藏版）》请在金锄头文库上搜索。
1、第 四章 同余式 -基本概念、一次同余式、孙子定理,0 , 1 , 2 , , - 1.),(,mma a ammam 定 义 是 定 义 在 正 整 数 上 的 函 数 它 在正 整 数 上 值 等 于 序 列 中 与 互 质 的 数 的个 数定 义 如 果 一 个 模 的 剩 余 类 里 面 的 数 与 互 质 就 把它 叫 做在 与 模 互 质 的 全 部 剩 余 类 中 从 每 一 类 各 任 取 一 数所 作 成 的 数 的 集 合 叫 做一 个 模 互 质 的 剩 余 类模 的 一 个 简拉 函 数化 剩 余 系欧复习 1( ) ,( ) .mmmmm m mmm定 理 模 的 剩
2、 余 类 与 模 互 质 的 充 分 必 要 条 件是 此 类 中 有 一 数 与 互 质 . 因 此 与 模 互 质 的 剩 余 类的 个 数 是 模 的 每 一 简 化 剩 余 系 是 由 与 互 质的 个 模 不 同 余 的 整数 组 成 的1 2 ( )1 2 ( )2 , , , ( ), , ,mma a a m mm a a a m定 理 若 是 与 互 质 的 整 数 ,并 且 两两 对 模 不 同 余 , 则 是 模 的 一 个简 化 剩 余系 . 1 2 1 21 2 2 1 1 2 1 23 ( , ) 1 ,.4 , ,a m x ma x mm m x xm m m
3、x m x m m定 理 若 通 过 模 的 简 化 剩 余 系 , 则通 过 模 的 简 化 剩 余 系定 理 若 是 两 个 互 质 的 正 整 数 , 分 别通 过 模 的 简 化 剩 余 系 则 +通 过 模的 简 化剩 余 系 .12121 2 1 21212( ) ( ) ( ) .5 1 1 1( ) ( 1 ) ( 1 ) ( 1 ) .kkkmmm m m ma p p paap p p 推 论 若 , 是 两 个 互 质 的 正 整 数 , 则定 理 设 , 则(1 2 ( )1 2 ( )1 ( ) 1 2 ( )()1 ) 2 )( 1 (, , , 33 , , ,
4、,) ( ,1 ( u l e r() 1 , ) 1 ,mmmmmmmmE m a mar r r ma r a r a r ma r a r r r r ma r r r rmrm证 设 是 模 的 简 化 剩 余 系 , 则 由定 理 也 是 模 的 简 化 剩 余 系 , 故( ) ( m o d )即 ) 定 理 设 是 大 于 的 整 数 ,( 则1 ( m o( m od )d .)1 2 ( ) 1 2 ( )(), ) ( , ) ( , ) 1 , , ) 1 .1mmmr m r m r m r r r mam 但 ( 因 此 (由 性 质 己 , 即 得 1 ( m o
5、 d ) . 4 欧拉定理 .费马定理及应用1, ) 1 , 1 3 5( F e,( m or m ad ) .t, ) 1 ,)ppppapapa a ppa p p aa a pa a p.证 若 ( 由 定 理 及 定 理推 论 定 理 若 是 素 数 则即 得1 ( m o d )因 而 若 ( 则故 (m( m oodd).)121 2 + 1 + 1 + 20 . , (0 , 1 , , 9 ,0 ) 0 , 0 ,1 , 2 , , ; 0 , 1 , 2 , . ,0 . .,. , , ,nns i s k t is s s tssa a a as t a ai t ka
6、 a a a astaa 定 义 如 果 对 于 一 个 有 限 小 数 是之 中 的 一 个 数 码 并 且 从 任 何 一 位 以 后 不全 为 是 能 找 到 两 个 整 数 使 得我 们 就 称 它 为 循 环 小 数 并简 单 把 它 记 作对 于 循 环 小 数 而 言 具 有 上 述 性 质 的 及 是 不 只一 个 的 如 果 找 到 的 是 最 小 的 我 们 就 称+,; ; 0,.stats 为 循 环 节 称 为 循 环 节 的 长 度 若 最 小 的 , 那 小 数就 叫 做 纯 循 环 小 数 否 则 叫 混 循 环 小 数公钥密码体制9算法描述密钥产生 独立地选取
7、两大素数 p和 q(各 100 200位十进制数字 ) 计算 n=p q， 其欧拉函数值 (n)=(p 1)(q 1) 随机选一整数 e， 1e(n)， gcd(n), e)=1 在模 (n)下 ， 计算 e的有逆元 d=e -1 mod (n) 以 n， e为公钥 。 秘密钥为 d。 (p, q不再需要 ， 可以销毁 。 ) 加密将明文分组 ， 各组对应的十进制数小于 n c=me mod n 解密 m=cd mod n10解密正确性证明 cd mod n med mod n m1 mod(n) mod n mk(n)+1 mod n gcd(m,n) =1m(n)1 mod n欧拉定理mk
8、(n)1 mod nmk(n)+1m mod n gcd(m,n) 1m是 p的倍数或 q的倍数 ，设 m=cp， gcd(m,q)=1,m(q)1 mod q，mk(q)1 mod q，mk(q) (p)1 mod q mk(n)1 mod q，存在一整数 r，使 mk(n)1 rq两边同乘 m=cp, mk(n)+1m+rcpq=m+rcn,即 mk(n)+1m mod n11RSA算法实现 如何判定一个给定的大整数是素数？ 已知 d如何计算 e，使 e * d1 mod(n) ？ 如何计算 C M e mod n或 MC d mod n？12第四章基本内容同余式的概念一次同余式概念及求解
9、孙子定理：求解同余方程组高次同余式的解数及解法质数模的同余式 1 基本概念及一次同余式10( ) ( ) ,;,( ) 0 ( m o d ) ( 1 )0 ( m o d ) ,.1 2 , ( ) 0 ( m o d ) , ( ) 0 ( m o d ) .nninaf x f x a x a x aamf x ma m nf a mK a f a mm定 义 若 表 示 多 项 式 + +其 中 是 整 数 又 设 是 一 正 整 数 则. 若 则 叫 做 ( 1 ) 的次 数由 第 三 章 定 理 若 则 剩 余 类中 任 何叫 做 模 的 同 余 式整 数 都 能 使 成 立( )
10、 0 ( m o d ) ,( m o d ) ( ) 0 ( m o d ) .( ) 0 ( m o d )( ) 0 ( m o d ) .a f a mx a m f x mf x m mf x m定 义 若 是 使 成 立 的 一 个 整 数则 叫 做 的 一 这 就 是说 我 们 把 适 合 而 对 模 互 相 同 余 的一 切 数 算 作 的 一 个 解解1 2 1 2m o d 11( m o d ) . m o d, m o d , m o d11cmx c m c mc c m c m c mm同 余 式 解 的 定 义同 余 类 中 的 任 一 整 数 也 是 () 的
11、解 , 这 些 解 都 应 看 作是 相 同 的 , 把 它 们 的 全 体 算 作 是 () 式 的 一 个 解 , 并 把 这 个 解 记为 这 实 际 上 是 把 同 余 类 看 作 是 满 足 ( 1 ) 的一 个 解 .当 均 为 同 余 式 的 解 , 且 对 模 不 同 余 ( 即是 不 同 的 同 余 类 ) 时 才 看 成 是 () 的 不 同 的 解 . 我 们 把 所 有 对 模两 两 不 同 余 的 () 的 解 的 个 数 ( 即 满 足 ( 11.mm m mm() 的 解 数 我 们 只 要 在 模 的 一) 的 模 的组 完 全 剩 余 系 中 来解 模 的 同
12、同 余 类 的 个 数 )称 为 是 . 因 此. 显 然 ,余 式 模 的 同 余 式 的 解 数 至 多 为24 2 7 - 1 2 0 ( m o d 1 5 )6 , 36 , 3 ( m o d 1 5 ) , 2 .xxxx例 1 求 同 余 方 程 的 解 .解 取 模 15 的 绝 对 最 小 完 全 剩 余 系 : - 7 , - 6 , ,- 1 , 0 , 1 , 2 , , 7 , 直 接 计 算 知 是 解 . 所 以 , 这个 同 余 方 程 的 解 是 解 数 为 22574 2 7 - 7 0 ( m o d 1 5 )7 , 2 , 1 , 4 ( m o d
13、 1 5 ) , .4 2 7 - 9 0 ( m o d 1 5 )0 ( m o d 5 )5 ; 0 ( m o d 7 )xxxxxxxxxx 例 2 求 同 余 式 的 解 .解 同 样 直 接 计 算 知 - 7 , - 2 , - 1 , 4 是 解 . 所 以 , 它 的 解 是解 数 为 4例 3 求 同 余 式 的 解 .直 接 计 算 , 这 个 方 程 无 解 .例 4 由 F e r m a t - E u l e r 定 理 知 , 同 余 式 的解 数 为 同 余 式 的 解 数0 ( m o d7).pp x x p p一 般 地 , 对 素 数 , 同 余 方
14、 程 的 解 数 为为( m o d ) , 0 ( m o d ) ( 2 ),)( 2 ) ( 2 ) ( )( , ) .a x b m a ma m bmd a m定 理 一 次 同 余 式 有 解 的 充 要 条 件 是 (.若 有 解 , 则 的 解 数 对 模 来 说 是|1 0 10101-.2 ( 2 ) ( , ) .( , ) . ( 2 ) 12 , , 0 , 1 , 2 , .( m o d ) , 0 , 1 , , 1 .,a x m y ba m bd a mmx m t x m tdmx x k m m k dx k m 证 ( 2 ) 有 解 的 充 要
15、条 件 是 有 解 从 而由 第 二 章 1 定 理 即 知 有 解 充 要 条 件 是设 若 有 解 , 则 由 第 二 章 1 定 理 知适 合 () 式 的 一 切 整 数 可 以 表 成此 式 对 模 来 说 , 可 以 写 成但0 , 1 , , 1 .( 2 )k d md 是 对 模 两 两 不 同 余 的故 有 个 解 .- ( 4)( 2)a x m y bx由 定 理 的 证 明 可 以 看 出 , 适 合 ( 2 ) 式 的 整 数也 就 是 适 合 不 定 方 程 的 解 答 中 的 值 , 故 同 余 式 可 以 用 解 不 定 方 程( 4 ) 的 方 法 去 解 它 .1 1 11111111- / 2 / 2 ;- / 2 / 2 ; ( m o d )55 ) . ( 6)5a a m m a m b b
