练习题 信安数学.ppt

1 已知a 66 b 75 求正整数x y 使ax by a b 成立 欧几里德除法75 66 93 66 75 66 7 66 8 75 766 9 7 33 66 9 79 3 3所以 66 75 3x 8 y 7 2 计算5模11的逆元 欧几里德除法 缩系11 5 2 11 11 5 2所以 5 2 1 mod11 所以模11时 5和2 5和 2互为逆元 3 解方程567x 21 mod1225 步骤 其实是化简x的系数 第一步 方程最简化 看是否有解第二步 简化以后x系数的逆元 化简x的系数 解 1 求 567 1225 1225 567 2 917 1225 567 2 25 567 4 1225 25 567 54567 91 6 217 91 567 91 6 4 91 25 567 491 21 4 77 91 21 421 7 3所以 567 1225 7 因为7 21 所以有解 有7个解 567 54 7 mod1225 3 解方程567x 21 mod1225 567 54 7 mod1225 2 化简方程81x 3 mod175 567 54 7 mod1225 所以 81 54 1 mod175 所以 81 54 3 3 mod175 所以x 54 3 162 13 mod175 3 所有解x 13 175t mod1225 t 0 1 5 6 4 15的完系和缩系 完系 0到14缩系 完系中与模互质的 即与3 5互质1 2 4 7 8 11 13 14全为奇的缩系 1 17 19 7 23 11 13 29剩余类分解 1 mod5 可分解为1 6 11 mod15 5 计算15的欧拉函数 15 3 5 2 4 8 6 化简 115x15 278x3 12 mod12 x 20 系数 指数 底数化简系数 115x15 278x3 12 mod12 7x15 2x3 0 mod12 指数 12 3 4 2 2 47x15 2x3 mod12 7x3 2x3 9x3 mod12 底数 9x3 mod12 9 203 9 83 0 mod12 7 已知a 5 b 42 n 455 求abmodn x 542 mod455 455 5 7 13x 542 mod5 x 542 mod7 x 542 mod13 x 0 mod5 x 50 1 mod7 x 56 1 mod13 x 0 1 5 13 3 1 5 7 3 300 155 mod455 13 找出模13的所有原根 有多少个 并据此求出1 12每个数的阶 每个元素可能的阶为 13 12的因子从2开始 22 4 23 8 24 3 26 1 mod13 所以2为其中一个原根 原根共 12 4 3 4个分别为2 25 6 27 11 211 7 mod13 13 找出模13的所有原根 有多少个 并据此求出1 12每个数的阶 可能的阶有1 2 3 4 6 12阶1的数有1个 1阶2的数有 2 1个 1 12 mod13 阶3的数有 3 2个 24 3 28 9 mod13 阶4的数有 4 2个 23 8 29 5 mod13 阶6的数有 6 2个 22 4 210 10 mod13 阶12的数有4个 2 6 7 11 14 1841是强伪素数吗 通过miller robin素性测试的就是强伪素数1841 1 1840 16 5 232115 mod1841 891 8912 mod1841 4104102 mod1841 5695692 mod1841 255 2552 mod1841 590非 1 所以没通过 如果是 1则通过所以1841是合数 不是强伪素数另 安全参数 重复测试的次数 16 Z 是群吗 其中 定义为a b a b 4 1 封闭性 a b a b 4 整数运算后仍为整数 所以封闭 2 结合性 a b c a b 4 c a b 4 c 4 a b c 所以结合性满足 3 单位元 任意a Z 若e为单位元 则a e a e 4 a 所以4为单位元 4 逆元 任意a b Z a b a b 4 4 则b 8 a 所以逆元为8 a所以 Z 构成群 17 Z12 12 的各子群 子群是与原来的群运算相同 集合为子集合子群具有同样的单位元 Z12 12 的单位元为0 集合为0 11的整数子群 1 Z12 12 2 A1 12 A1 0 2 4 8 10 3 A2 12 A2 0 3 6 9 4 A3 12 A3 0 4 8 5 A4 12 A4 0 6 6 A5 12 A5 0 18 群的阶与元素的阶 如Z12的的每个元素的阶 所有生成元和所有子群 Z12 12 不是群 因为2等没逆元 Z12 12 单位元0元素 0 阶 1 元素 2 10 阶 6元素 3 9 阶 4 元素 4 8 阶 3元素 6 阶 2 元素 1 5 7 11 阶 12生成元 1 5 7 11子群 略 19 置换 理解含义 会计算 20 多项式环上的运算 如Z2上的多项式环中 1 f x x2 x 1 可约吗 可能因式 x x 1f x x x 1 1 所以不可约 2 加法 f x x2 x 1 g x x3 1 f x g x f x g x x3 x2 x 2 x3 x2 x 20 多项式环上的运算 如Z2上的多项式环中 3 除法 f x x4 x 1 g x x 1 f x g x x3 x2 xx 1x4 0 x3 0 x2 x 1x4 x3x3 0 x2x3 x2x2 xx2 x1f x g x x3 x2 x 余1 20 多项式环上的运算 如Z2上的多项式环中 4 求两个多项式的最大公约数f x x4 x 1 g x x 1的最大公约数1欧几里的除法 21 构造一个八元域 因为8 23 所以可以通过GF 2 扩成GF 23 需要GF 2 上的3次不可约多项式x x3 x 1 x3 1 x x3 x x x 1均 x3 x 1 x3 x 1 x2 x 1 x 1 x 所以x3 x 1 x3 x 1取为x3 x 1 叫做生成元或生成多项式生成的域为 0 1 x x 1 x2 x2 1 x2 x x2 x 1 域上的加法为 a b a b modx3 x 1 域上的乘法为 a b a b modx3 x 1 23 CRC计算 生成多项式为f x x4 x 1 传送的信息为10110100110 请给出接收方收