密码学子论·第4 ALIA OCEAN/A 数论基础 李卫海
密码学导论˙第4章 数论基础 李卫海
本章日录 第一节有限域计算 第四节单向函数和单向陷门函数 ·群、环、域 ·单向函数、单向陷门函数 ·模运算、有限域、多项式计算 ·离散对数 ·欧几里德算法、扩展欧几里德算法 第五节有限域方程 第二节素数相关问题 ·中国剩余问题: ax mod n=b ·素数、素因子分解 二次剩余问题、求解x2modp=a ·费马定理、欧拉函数、欧拉定理、求逆元 ·素性测试: WITNESS测试算法、 Miller 第六节秘密分享技术 Rabin测试算法 ·拉格朗日插值法 第三节本原元与指数方程 ·本原元、快速指数算法 密码学导论一中国科学技术大学
本章目录 密码学导论--中国科学技术大学 2 第一节 有限域计算 •群、环、域、 •模运算、有限域、多项式计算 •欧几里德算法、扩展欧几里德算法 第二节 素数相关问题 •素数、素因子分解 •费马定理、欧拉函数、欧拉定理、求逆元 •素性测试：WITNESS测试算法、Miller Rabin测试算法 第三节 本原元与指数方程 •本原元、快速指数算法 第四节 单向函数和单向陷门函数 • 单向函数、单向陷门函数 • 离散对数 第五节 有限域方程 • 中国剩余问题：ax mod n =b • 二次剩余问题、求解x 2 mod p=a 第六节 秘密分享技术 • 拉格朗日插值法
第一芳有限域计算 密码学导论一中国科学技术大学
第一节 有限域计算 密码学导论--中国科学技术大学 3
群、环和域 令群 Group 群G,记作{G,刂定义一个二元运算“·的集合,G中每 个序偶(a,b)通过运算生成G中元素(a·b),满足下列公 理 (A1)封闭性 Closure:如果a和b都属于G,则a·b也属 于G (A2)结合律 Associative:对G中的任意元素a,b,C ,都有a(bc)=(ab)c成立 (A3)单位元 Identity element:G中存在一个元素e, 对于G中任意元素a,都有ae=ea=a成立 (A4)逆元 Inverse element:对于G中任意元素a,G中 都存在一个元素a1,使得a·a1=a1a=e成立 密码学导论一中国科学技术大学
一、群、环和域 ❖群Group： 群G，记作{G, •}, 定义一个二元运算“•”的集合，G中每 一个序偶(a,b)通过运算生成G中元素(a•b)，满足下列公 理： ▪ (A1) 封闭性Closure：如果a和b都属于G，则a•b也属 于G ▪ (A2) 结合律Associative：对G中的任意元素a，b，c ，都有a•(b•c)=(a•b)•c成立 ▪ (A3) 单位元Identity element：G中存在一个元素e， 对于G中任意元素a，都有a•e=e•a=a成立 ▪ (A4) 逆元Inverse element：对于G中任意元素a, G中 都存在一个元素a -1，使得a•a-1=a-1•a=e成立 密码学导论--中国科学技术大学 4
☆有限群 Finite Group和无限群 nfinite Group 如果一个群的元素是有限的,则该群称为有限群,且群的阶等于 群中元素的个数;否则称为无限群 ☆交换群(阿贝尔群) Abelian Group 满足交换律的群 (A5)交换律 Commutative:对于G中任意的元素a,b,都有 ab=ba成立 ☆循环群 Cyclic Group;: 如果群中的每一个元素都是一个固定的元素a(a∈G)的幂ak(k为整 数),则称群G为循环群。 元素a生成了群G,或者说a是群G的生成元。 密码学导论一中国科学技术大学
❖ 有限群Finite Group和无限群Infinite Group： ▪ 如果一个群的元素是有限的，则该群称为有限群，且群的阶等于 群中元素的个数；否则称为无限群 ❖ 交换群（阿贝尔群）Abelian Group： ▪ 满足交换律的群 ▪ (A5) 交换律Commutative ：对于G中任意的元素a, b，都有 a•b=b•a成立 ❖ 循环群Cyclic Group: ▪ 如果群中的每一个元素都是一个固定的元素a(a∈G)的幂a k (k为整 数)，则称群G为循环群。 ▪ 元素a生成了群G，或者说a是群G的生成元。 密码学导论--中国科学技术大学 5
令减法: 当群中的运算符是加法时,其单位元是0 a的逆元是-a 减法定义为:a-b=a+(-b) 密码学导论一中国科学技术大学
❖ 减法： ▪ 当群中的运算符是加法时，其单位元是0 ▪ a的逆元是-a ▪ 减法定义为：a–b=a+(-b) 密码学导论--中国科学技术大学 6
环Rng 环R,记作R+,刈,定义二元运算加法“+”和乘法 ×"的集合,R中任意元素a,b,C满足下列公理: (A1-A5),R关于加法是交换群,单位元是0,a的逆元 是-a (M1)乘法封闭性:如果a和b都属于R,则ab也属于R (M2)乘法结合律:如果a,b,C都属于R,则a(bc)=(ab)c (M3)分配律:如果a,b,C都属于R,则a(b+C)=ab+aC 或(a+b)C=ac+bc 密码学导论一中国科学技术大学
❖环Ring： 环R，记作{R,+,x}，定义二元运算加法“+”和乘法 “×”的集合， R中任意元素a,b,c满足下列公理： ▪ (A1-A5), R关于加法是交换群，单位元是0，a的逆元 是-a ▪ (M1) 乘法封闭性：如果a和b都属于R，则ab也属于R ▪ (M2) 乘法结合律：如果a,b,c都属于R，则a(bc)=(ab)c ▪ (M3) 分配律：如果a,b,c都属于R，则a(b+c)=ab+ac 或(a+b)c =ac+bc 密码学导论--中国科学技术大学 7
☆交换环 Commutative Ring:满足下列条件的环 (M4)乘法交换律:对R中任意元素a,b,都有ab=ba成立 ☆整环 Integral Domain:满足下列条件的交换环 (M5)乘法单位元:在R中存在元素1,使得对于R中任意元素a, 都有a1=1a成立 (M6)无零因子:若元素a,b满足ab=0,则必有a=0或b=0 密码学导论一中国科学技术大学
❖ 交换环Commutative Ring ：满足下列条件的环 ▪ (M4) 乘法交换律：对R中任意元素a,b，都有ab=ba成立 ❖ 整环Integral Domain ：满足下列条件的交换环 ▪ (M5) 乘法单位元：在R中存在元素1，使得对于R中任意元素a， 都有 a1=1a成立 ▪ (M6) 无零因子：若元素a,b满足ab=0，则必有a=0或b=0 密码学导论--中国科学技术大学 8
域 Field 域F,记作{F+,x},定义为满足下列关系的整环 (M刀)乘法逆元 Multiplicative inverse:对F中每个元素 a(除0以外),存在元素a1满足a-=(a-)a=1 令除法 对F中任意元素a和任意非零元素b,定义为a/b=a(b-1) 密码学导论一中国科学技术大学
❖域Field： 域F，记作{F,+,×}，定义为满足下列关系的整环： ▪ (M7) 乘法逆元Multiplicative inverse: 对F中每个元素 a（除0以外），存在元素a -1满足aa-1=(a-1 )a=1 ❖ 除法： ▪ 对F中任意元素a和任意非零元素b，定义为a/b=a(b-1 ) 密码学导论--中国科学技术大学 9
约束关系 群:A1加法封闭;A2加法结台律;A3加法单位元;A4加法逆元 交换群:A5加法交换律 环:M1乘法封闭;M2乘法结合律;M3分配率 交换环:M4乘法交换律 整环:M5乘法单位元;M6无零因子 域:M7乘法逆元 密码学导论一中国科学技术大学
约束关系 群：A1加法封闭；A2加法结合律；A3加法单位元；A4加法逆元 交换群：A5加法交换律 环：M1乘法封闭；M2乘法结合律；M3分配率 交换环：M4乘法交换律 整环：M5乘法单位元；M6无零因子 域：M7乘法逆元 密码学导论--中国科学技术大学 10