密码学子论·第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