本章要点 素数是一种整数,在整除意义下,它只能被自身(正 负)和1整除。素数在数论和密码学里扮演重要角色。 在公钥密码里起重要作用的两个定理是费马定理和欧 拉定理。 丶许多密码算法的一个重要前提是能够选择一个大的素 数。开发有效算法判定一个随机整数是否为素数是密 码研究的重要课题。 离散对数是许多公钥算法的基础。离散对数和普通对 数类似,但是在模算术上进行运算。 0(0 ash mfy@ustc.edu.cn 现代密码学理论与实践 3/81
mfy@ustc.edu.cn 现代密码学理论与实践 3/81 素数是一种整数，在整除意义下，它只能被自身(正 负)和1整除。素数在数论和密码学里扮演重要角色。 在公钥密码里起重要作用的两个定理是费马定理和欧 拉定理。 许多密码算法的一个重要前提是能够选择一个大的素 数。开发有效算法判定一个随机整数是否为素数是密 码研究的重要课题。 离散对数是许多公钥算法的基础。离散对数和普通对 数类似，但是在模算术上进行运算
本章目录 8.1素数 8,2单向函数 8.3费马定理和欧拉定理 8.4素性测试 8.5计算乘法逆元素 8.6求解 ax mod n=b的问题 8,7中国余数定理 8.8离散对数问题 8.9二次剩余问题 8.10不经意传输 ash mfy@ustc.edu.cn 现代密码学理论与实践 4/81
mfy@ustc.edu.cn 现代密码学理论与实践 4/81 8.1 素数 8.2 单向函数 8.3 费马定理和欧拉定理 8.4 素性测试 8.5 计算乘法逆元素 8.6 求解ax mod n =b的问题 8.7 中国余数定理 8.8 离散对数问题 8.9 二次剩余问题 8.10 不经意传输
8.1素数 Prime Numbers 素数→合数→最大公因数 整数p>1是素数当且仅当它只有因子±1和±p,如 2,3,5,7是素数,而4,6,8,9,10不是素数 素数不能写作其他数的乘积形式 1是素数,但是通常没有什么用 素数是数论的核心 小于200的素数如下 23571113171923293137414347 53596167717379838997101103 107109113127131137139149151157 163167173179181191193197199 ash mfy@ustc.edu.cn 现代密码学理论与实践 5/81
mfy@ustc.edu.cn 现代密码学理论与实践 5/81 整数p>1是素数当且仅当它只有因子±1和±p，如 2,3,5,7是素数，而4,6,8,9,10不是素数 素数不能写作其他数的乘积形式 1是素数，但是通常没有什么用 素数是数论的核心 小于200的素数如下 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 素数→合数→最大公因数
小于2000的素数如下 Table 8.1 Primes under 2000 1!13122934好490sn1乃78「89 1010310710913127131313911511571s3167i3171a11193197199 292332392412512572632627112772311283129 30731313373137373493533673733793831389|39 04941942143433439443449457461463457479487491499 503552523541547557563156571577 6016m137196316414364763659 673677683691 70107197277331394375117577617673787797 0a1]321823a7829a93535783633m7183887 o7q999299379179596791|9983y1997 l0091013|101910211031103310g104910511o6110631o69l107|10g10931097 1101011231291111153116311n11311187119 1201121311217 212121123719159127 1279123311289112911297 1浏[1331班3013713313139 1414231421|14314组[1均311143 143914 1499 1111523151551548155513591515159[15831397 l61l160710916131619162116716371657166160166l1693|16s71699 17091721172 4133[1mT1339 l801a11a181186113671118731371791389 1聊919[9191199 ash mfy@ustc.edu.cn 现代密码学理论与实践 6/81
mfy@ustc.edu.cn 现代密码学理论与实践 6/81
合数的素因子分解 分解一个数η就是把它写成其他数的乘积形式,如 n=a×b×C 比起用乘的方法把几个因子乘起来生成合数,分解 合数通常要困难得多。 (算术基本定理)任何整数a>1,都可以唯一地分 解为a=p1ap2pat,其中,p1<p2<.<p是素 数,所有的a都是非负整数。如91=7×13; 3600=24×32x52:11011=7×112×13 素因子分解就是把一个合数写成若干素数的乘积形 式,如3600=24×32×52, a=∏P“其中每个20,对于某整数a, 其大多数指数a为0 D∈D 2021/1/27 现代密码学理论与实践-08 7/69
2021/1/27 现代密码学理论与实践-08 7/69 分解一个数n就是把它写成其他数的乘积形式，如 n=a×b×c 比起用乘的方法把几个因子乘起来生成合数，分解 合数通常要困难得多。 （算术基本定理）任何整数a>1, 都可以唯一地分 解为a= p1 a1p2 a2…pt at , 其中, p1<p2<…<pt 是素 数，所有的ai都是非负整数。如91=7x13; 3600=24x32x52; 11011=7x112x13 素因子分解就是把一个合数写成若干素数的乘积形 式，如3600=24x32x52 ， 其中每个ap≥0, 对于某一整数a， 其大多数指数ap为0. = p P ap a P