01数学背景.pdf

2 22011 11 1信息安全技术信息安全技术 万涛万涛 数论知识数论知识数论知识数论知识 除数 因子 的概念 除数 因子 的概念 除数 因子 的概念 除数 因子 的概念 设设设设a a b b为两个任意整数 为两个任意整数 为两个任意整数 为两个任意整数 Z Z为全体整数构成的集合 若为全体整数构成的集合 若为全体整数构成的集合 若为全体整数构成的集合 若b b 0 0 且使得且使得且使得且使得a a mbmb 称 称 称 称b b整除整除整除整除a a 记为 记为 记为 记为b b a a 还称 还称 还称 还称b b为为为为a a的除数的除数的除数的除数 因子因子因子因子 注注注注 若若若若a a mbmb r r且且且且0 r b 0 r 1p 1被称为素数是指被称为素数是指被称为素数是指被称为素数是指p p的因子仅有的因子仅有的因子仅有的因子仅有1 1 1 1 p p p p 算术基本定理 算术基本定理 算术基本定理 算术基本定理 任何正整数任何正整数任何正整数任何正整数a a 1 1都可以写成唯一的表达式都可以写成唯一的表达式都可以写成唯一的表达式都可以写成唯一的表达式 a a P P 1 1 1 1 P P2 2 2 2 P P t t t t 这里这里这里这里P P 1 1 P P 2 2 P P 3 3 P P t t 是素数 是素数 是素数 是素数 其中其中其中其中 i i 0 0 例 例 例 例 305613305613 1111 7 7 3 3 3 3 4 4 数学背景数学背景数学背景数学背景 4 42011 11 1信息安全技术信息安全技术 万涛万涛 最大公约数 最大公约数 最大公约数 最大公约数 若若若若a b a b k k Z Z 如果如果如果如果k k a a k k b b 称称称称k k是是是是a a和和和和b b的公约数 的公约数 的公约数 的公约数 正整数正整数正整数正整数c c称为称为称为称为a a和和和和b b的最大公约数 如果它满足的最大公约数 如果它满足的最大公约数 如果它满足的最大公约数 如果它满足 c c是是是是a a和和和和b b的公约数 的公约数 的公约数 的公约数 对对对对a a和和和和b b的任何一个公约数的任何一个公约数的任何一个公约数的任何一个公约数k k有有有有 k k c c 注 注 注 注 1 1 等价的定义形式是 等价的定义形式是 等价的定义形式是 等价的定义形式是 gcdgcd a b a b max kmax k k k a a k k b b 2 2 若 若 若 若gcdgcd a b a b 1 1 称称称称a a与与与与b b是互素的 是互素的 是互素的 是互素的 例 例 例 例 gcdgcd 323 221 17 323 221 17 数学背景数学背景数学背景数学背景 5 52011 11 1信息安全技术信息安全技术 万涛万涛 最小公倍数 最小公倍数 最小公倍数 最小公倍数 若若若若a b a b k k Z Z 如果如果如果如果a a k k b b k k 称称称称k k是是是是a a和和和和b b的公倍数的公倍数的公倍数的公倍数 正整数正整数正整数正整数d d称为称为称为称为a a和和和和b b的最小公倍数 如果它满足的最小公倍数 如果它满足的最小公倍数 如果它满足的最小公倍数 如果它满足 d d是是是是a a和和和和b b的公倍数 的公倍数 的公倍数 的公倍数 对对对对a a和和和和b b的任何一个公倍数的任何一个公倍数的任何一个公倍数的任何一个公倍数k k有有有有d d k k 等价的定义形式是 等价的定义形式是 等价的定义形式是 等价的定义形式是 lcm a b lcm a b min min k k a a k k b b k k 例 例 例 例 lcm 56 34 952lcm 56 34 952 数学背景数学背景数学背景数学背景 6 62011 11 1信息安全技术信息安全技术 万涛万涛 欧拉函数 欧拉函数 欧拉函数 欧拉函数 设设设设n 1n 1若若若若 n n 表示比表示比表示比表示比n n小而与小而与小而与小而与n n互素的正整数的个数 互素的正整数的个数 互素的正整数的个数 互素的正整数的个数 则则则则 n n 为欧拉函数 为欧拉函数 为欧拉函数 为欧拉函数 以以以以n n 2424为例 比为例 比为例 比为例 比2424小而与小而与小而与小而与24 24 互素的正整数为 互素的正整数为 互素的正整数为 互素的正整数为 1 1 5 5 7 7 1111 1313 1717 1919 2323 因此 我们有 因此 我们有 因此 我们有 因此 我们有 24 24 8 8 性质 性质 性质 性质 1 1 若 若 若 若p p为素数 则为素数 则为素数 则为素数 则 p p p p 1 1 2 2 若若若若p p为素数 则为素数 则为素数 则为素数 则 p p k k p pk k 1 1 p p 1 1 3 3 若若若若mm与与与与n n互素 则互素 则互素 则互素 则 m n m n m m n n 4 4 若若若若n n P P 1 1 1 1 P P2 2 2 2 P P t t t t 则则则则 n n 1 1 1 1 1 1 21t PPP n 数学背景数学背景数学背景数学背景 7 72011 11 1信息安全技术信息安全技术 万涛万涛 带余除法 带余除法 带余除法 带余除法 a a Z Z 0 0 可找出两个唯一确定的整数可找出两个唯一确定的整数可找出两个唯一确定的整数可找出两个唯一确定的整数q q和和和和r r 使 使 使 使 a a qmqm r 0 r 0 r mr ba b a b qa b q 1 1 r r 1 1 b rb r 1 1 q q 2 2 r r 2 2 r r 1 1 r r 2 2 q q 3 3 r r 3 3 r r n n 2 2 r rn n 1 1 q qn n r r n n r r n n 1 1 r r n n q qn 1 n 1 r rn 1 n 1 r r n 1n 1 0 0 于是于是于是于是gcdgcd a b a b r r n n 数学背景数学背景数学背景数学背景 9 92011 11 1信息安全技术信息安全技术 万涛万涛 例 例 例 例 求求求求gcdgcd 15471547 560 560 解 解 解 解 1547 2 560 4271547 2 560 427 560 1 427 133560 1 427 133 427 3 133 28427 3 133 28 133 4 28 21133 4 28 21 28 1 21 728 1 21 7 21 3 7 021 3 7 0 于是于是于是于是 gcdgcd 15471547 560 560 7 7 数学背景数学背景数学背景数学背景 10102011 11 1信息安全技术信息安全技术 万涛万涛 同余 同余 同余 同余 设设设设a a b b Z Z 若 若 若 若mm a a b b 则称整数则称整数则称整数则称整数a a和和和和b b模正整数模正整数模正整数模正整数mm同余同余同余同余 并写并写并写并写a a b b mod m mod m mm称为同余式的模 称为同余式的模 称为同余式的模 称为同余式的模 性质 性质 性质 性质 1 1 自反性 对任意整数 自反性 对任意整数 自反性 对任意整数 自反性 对任意整数a a有有有有a a a a mod m mod m 2 2 对称性 如果对称性 如果对称性 如果对称性 如果a a b b mod m mod m 则则则则b b a a mod m mod m 3 3 传递性 如果传递性 如果传递性 如果传递性 如果a a b mod m b mod m b b c c mod m mod m 则则则则a a c c mod m mod m 4 4 a mod a mod m m b b mod m mod m a a b b mod m mod m a mod m b mod m a mod m b mod m a b mod m a b mod m 例 通过同余式演算证明例 通过同余式演算证明例 通过同余式演算证明例 通过同余式演算证明5 560 60 1 1是是是是5656的倍数 的倍数 的倍数 的倍数 解 解 解 解 5 5 3 3 125 125 13 13 mod56 mod56 于是有于是有于是有于是有5 5 6 6 169 169 1 1 mod56 mod56 对同余式的两边同时升到对同余式的两边同时升到对同余式的两边同时升到对同余式的两边同时升到1010次幂 即有次幂 即有次幂 即有次幂 即有5656 5 560 60 1 1 数学背景数学背景数学背景数学背景 11112011 11 1信息安全技术信息安全技术 万涛万涛 全体整数集合全体整数集合全体整数集合全体整数集合Z Z可按模可按模可按模可按模m m 1 m m 1 分成一些两两不交的等价类 分成一些两两不交的等价类 分成一些两两不交的等价类 分成一些两两不交的等价类 整数模整数模整数模整数模mm同余类共有同余类共有同余类共有同余类共有mm个 它们分别为个 它们分别为个 它们分别为个 它们分别为 mk 0 mk 1 mk 2 mk 0 mk 1 mk 2 mk m mk m 1 1 k k Z Z 每个类选这类中的最小非负整数作为其代表元 每个类选这类中的最小非负整数作为其代表元 每个类选这类中的最小非负整数作为其代表元 每个类选这类中的最小非负整数作为其代表元 于是称于是称于是称于是称 0 1 2 0 1 2 mm 1 1 为标准完全剩余系 为标准完全剩余系 为标准完全剩余系 为标准完全剩余系 Z Z模模模模1212的标准剩余系为 的标准剩余系为 的标准剩余系为 的标准剩余系为 0 1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6 7 8 9 10 11 定理定理定理定理1 1 设设设设a a为整数 若存在整数为整数 若存在整数为整数 若存在整数为整数 若存在整数a a 使 使 使 使a aa a 1 mod m 1 mod m 则称则称则称则称a a 为为为为a a对模对模对模对模mm的数论倒数 的数论倒数 的数论倒数 的数论倒数 例 设例 设例 设例 设mm 5 5 a a 7 7 则则则则a a 3 3 定理定理定理定理2 2 若若若若 a m 1a m 1 则对模 则对模 则对模 则对模mm 整数 整数 整数 整数a a有数论倒数有数论倒数有数论倒数有数论倒数a a 数学背景数学背景数学背景数学背景 12122011 11 1信息安全技术信息安全技术 万涛万涛 FormatFormat定理 定理 定理 定理 如果如果如果如果p p是素数 是素数 是素数 是素数 a a是正整数 是正整数 是正整数 是正整数 a a不是不是不是不是p p 的倍数 则的倍数 则的倍数 则的倍数 则a ap p 1 1 1 mod p 1 mod p 证明 证明 证明 证明 Z Z p p Z Z p p p 1 p 1 易见 易见 易见 易见 Z Z p p 1 2 3 1 2 3 p p 1 1 且由 且由 且由 且由 a p a p 1 1知知知 知 a Za Z p p a 2a 3a a 2a 3a p p 1 a Z1 a Z p p 原因是原因是原因是原因是a Za Z p p 内的元素内的元素内的元素内的元素 两两不同 他们刚好为两两不同 他们刚好为两两不同 他们刚好为两两不同 他们刚好为1 1 2 2 3 3 p p 1 1 的一个排列 的一个排列 的一个排列 的一个排列 所以所以所以所以 a 2a 3a a 2a 3a p p 1 a1 a 1 2 3 1 2 3 p p 1 mod p 1 mod p 由由由由 p p 1 1 p p 1 1 所以所以所以 所以 a a p p 1 1 1 mod p 1 mod p 易见 对易见 对易见 对易见 对 a a p p 1 1 有 有 有 有a a p p a a mod p mod p 例 例 例 例 4 4 6 6 mod 7 4096 mod 7 1 mod 7 4096 mod 7 1 4 47 7 mod 7 16384 mod 7 4 mod 7 16384 mod 7 4 数学背景数学背景数学背景数学背景 13132011 11 1信息安全技术信息安全技术 万涛万涛 EuclidEuclid定理 定理 定理 定理 若若若若 a a m 1m 1 则则则则a a m m 1 mod m 1 mod m 证明 设小于证明 设小于证明 设小于证明 设小于mm且与且与且与且与mm互素的正整数为互素的正整数为互素的正整数为互素的正整数为r r 1 1 r r 2 2 r r 3 3 r r m m 1 1 他们是模他们是模他们是模他们是模mm两两互不同余的 对每一个定数两两互不同余的 对每一个定数两两互不同余的 对每一个定数两两互不同余的 对每一个定数i i来说 由于来说 由于来说 由于来说 由于 a a和和和和r r i i 都与都与都与都与mm互素 所以互素 所以互素 所以互素 所以 arar i i m 1 m 1 所以所以所以所以arar i i 同余于同余于同余于同余于 1 1 中的某个中的某个中的某个中的某个r r i i 即即即即 arar i i r r i i mod mod m m 1 1 i i m m 并且当并且当并且当并且当i i j j时 有时 有时 有时 有arar i i arar j j mod m mod m 于是 于是 于是 于是 为为为 为 的置换的置换的置换的置换 所以有所以有所以有所以有 由由由由 r r i i m 1 m 1 所以所以所以所以 a a m m 1 mod m 1 mod m 21 m rrr 21 m rrr mod 21 21 21 mrrrrrrrrra mmm m 1 21 mrrr m 数学背景数学背景数学背景数学背景 14142011 11 1信息安全技术信息安全技术 万涛万涛 同余式解 同余式解 同余式解 同余式解 设设设设f xf x a a n n x xn n a an n 1 1 x x n n 1 1 a a 0 0 为整系数多项式 为整系数多项式 为整系数多项式 为整系数多项式 mm为正整数 若存在整数为正整数 若存在整数为正整数 若存在整数为正整数 若存在整数x x使同余式使同余式使同余式使同余式f x f x 0 mod m 0 mod m 成立 成立 成立 成立 则称整数则称整数则称整数则称整数x x为同余式的解 为同余式的解 为同余式的解 为同余式的解 若若若若f x f x 为一次方程 则称其为一次同余式为一次方程 则称其为一次同余式为一次方程 则称其为一次同余式为一次方程 则称其为一次同余式 ax ax b mod m b mod m 定理定理定理定理3 3 若若若若 a a m 1m 1 则同余式 则同余式 则同余式 则同余式ax ax b mod m b mod m 恰有一个解 恰有一个解 恰有一个解 恰有一个解 定理定理定理定理4 4 一次同余式一次同余式一次同余式一次同余式ax ax b mod m b mod m a a 0 0 mod m mod m 有解的有解的有解的有解的 充要条件是充要条件是充要条件是充要条件是 a a m m b b 若有解 解的个数为若有解 解的个数为若有解 解的个数为若有解 解的个数为d a m d a m 例 例 例 例 解同余式解同余式解同余式解同余式6x 6x 15 mod 33 15 mod 33 解 解 解 解 2 2x x 5 mod 11 5 mod 11 x 5 6 mod 11 8 mod 11 x 5 6 mod 11 8 mod 11 又又又又x 19x 19 30 mod 11 30 mod 11 亦为解亦为解亦为解亦为解 数学背景数学背景数学背景数学背景 15152011 11 1信息安全技术信息安全技术 万涛万涛 中国剩余定理 中国剩余定理 中国剩余定理 中国剩余定理 例子 孙子算经 今有物不知其数 三三数之余二 五五数例子 孙子算经 今有物不知其数 三三数之余二 五五数例子 孙子算经 今有物不知其数 三三数之余二 五五数 例子 孙子算经 今有物不知其数 三三数之余二 五五数 之余三 七七数之余二 问物几何 之余三 七七数之余二 问物几何 之余三 七七数之余二 问物几何 之余三 七七数之余二 问物几何 答曰 二十三 答曰 二十三 答曰 二十三 答曰 二十三 2323 2 70 3 21 2 15 2 70 3 21 2 15 mod 105 mod 105 口诀 三人同行七十稀 五树梅花廿一枝 口诀 三人同行七十稀 五树梅花廿一枝 口诀 三人同行七十稀 五树梅花廿一枝 口诀 三人同行七十稀 五树梅花廿一枝 七子团圆月正半 除百零五便得知 七子团圆月正半 除百零五便得知 七子团圆月正半 除百零五便得知 七子团圆月正半 除百零五便得知 问 问 问 问 7070 2121 1515如何得到的 如何得到的 如何得到的 如何得到的 原问题为求解同余方程组原问题为求解同余方程组原问题为求解同余方程组原问题为求解同余方程组 7 mod 2 5 mod 3 3 mod 2 x x x 数学背景数学背景数学背景数学背景 16162011 11 1信息安全技术信息安全技术 万涛万涛 注意 若注意 若注意 若注意 若x x 0 0 为上述同余方程组的解 为上述同余方程组的解 为上述同余方程组的解 为上述同余方程组的解 则则则则x x 0 0 x x 0 0 105 k 105 k k k Z Z 也为上述同余方程组的解 也为上述同余方程组的解 也为上述同余方程组的解 也为上述同余方程组的解 解题口诀提示我们先解下面三个特殊的同余方程组解题口诀提示我们先解下面三个特殊的同余方程组解题口诀提示我们先解下面三个特殊的同余方程组解题口诀提示我们先解下面三个特殊的同余方程组 1 1 2 2 3 3 的特殊解的特殊解的特殊解 的特殊解 以方程以方程以方程以方程 1 1 为对象 相当于解一个同余方程为对象 相当于解一个同余方程为对象 相当于解一个同余方程为对象 相当于解一个同余方程 3535y y 1 mod 3 1 mod 3 理由是从理由是从理由是从理由是从 1 1 的模数及条件知 的模数及条件知 的模数及条件知 的模数及条件知 x x应是应是应是应是3535的倍数 于是的倍数 于是的倍数 于是的倍数 于是 1 mod3 0 mod5 0 mod7 x x x 0 mod3 1 mod5 0 mod7 x x x 0 mod3 0 mod5 1 mod7 x x x 1 0 0 0 1 0 0 0 1 数学背景数学背景数学背景数学背景 17172011 11 1信息安全技术信息安全技术 万涛万涛 可以假设可以假设可以假设可以假设x x 35y35y 3535y y 1 mod 3 1 mod 3 相当于相当于相当于相当于2 2y y 1 mod 3 1 mod 3 解出解出解出解出y y 2 mod 3 2 mod 3 于是 于是 于是 于是x x 35 2 35 2 70 mod 105 70 mod 105 类似地得到类似地得到类似地得到类似地得到 2 2 3 3 方程的模方程的模方程的模方程的模105105的解的解的解的解2121 1515 于是有于是有于是有于是有 得得得得 70 0 0 1 21 0 1 0 15 1 0 0 105 mod 2315 221 370 2 1 0 0 2 0 1 0 3 0 0 1 2 2 3 2 数学背景数学背景数学背景数学背景 18182011 11 1信息安全技术信息安全技术 万涛万涛 中国剩余定理 中国剩余定理 中国剩余定理 中国剩余定理 设设设设mm 1 1 m m 2 2 mm r r 两两互素 并记两两互素 并记两两互素 并记两两互素 并记N mN m 1 1 mm2 2 m m r r 则同余方程组则同余方程组则同余方程组则同余方程组 在模在模在模在模N N同余的意义下有唯一解 同余的意义下有唯一解 同余的意义下有唯一解 同余的意义下有唯一解 m mod bx m mod bx m mod bx rr 22 11 数学背景数学背景数学背景数学背景 19192011 11 1信息安全技术信息安全技术 万涛万涛 平方剩余 平方剩余 平方剩余 平方剩余 设设设设a a Z Zm m 如果存在如果存在如果存在如果存在x x Z Zm m 使得使得使得使得x x 2 2 a mod m a mod m 有解 有解 有解 有解 则称则称则称则称a a为模为模为模为模mm的平方剩余的平方剩余的平方剩余的平方剩余 否则称 否则称 否则称 否则称a a为模为模为模为模mm的的的的非平方剩余 非平方剩余 非平方剩余 非平方剩余 例如 例如 例如 例如 x x 2 2 a mod 7 a mod 7 当当当当a a 1