有限域 定义:F为域,鬥有限 实例:ZmP为素数 Z为整环,<Z{0,>有限半群, 无零元,适合消去律,<Z-{0},>构成Abel群 结论:有限的整环都是域 有限域的特征 F为有限域,1在<F,+>中的阶为域F的特征 的特征为p
6 定义：F 为域，|F|有限 实例：Zp, p 为素数 Zp 为整环，<Zp−{0},⋅>有限半群， 无零元，适合消去律，<Zp−{0},⋅>构成 Abel 群 结论：有限的整环都是域 有限域的特征 F 为有限域，1 在<F,+>中的阶为域 F 的特征. Zp的特征为 p. 有限域
有限域的性质 设F为有限域,则存在素数p使得F=p, 证明思想: A=<1>={0,1,…,p-1 Ax1={0,x,2x,…,(p-1x},xieF 若F=Ax1则结束;否则丑x2∈F-Ax,x2=0, Axi+Ax2=a1x+2x2 a1, 2EA 可以证明Ax1+Ax2中的元素两两不同, 因此|Ax1+x2|2, 照此处理,x+42+4p,直到穷尽所有的元素
7 设 F 为有限域，则存在素数 p 使得|F|=pn, 证明思想: A=<1>={ 0, 1, … , p−1 } Ax1 = { 0, x1, 2x1, …, (p−1)x1}，x1∈F* |Ax1| = p 若 F=Ax1 则结束；否则 ∃x2∈F−Ax1, x2≠0, Ax1+Ax2 ={ a1x1+a2x2 | a1,a2∈A} 可以证明 Ax1+Ax2 中的元素两两不同， 因此|Ax1+Ax2|=p2 , 照此处理，|Ax1+Ax2+Ax3|=p3, 直到穷尽所有的元素 有限域的性质
有限域应用—素数测试问题 Fermat小定理:如果n为素数,则对所有的正整数 a≠0(modm)有a=l(modn) 测试素数的算法: 令a=2,检测=1(modn)? 如果回答“是”,输出“素数”;否则输出“合数” 分析: 时间T(m)=0og3n) 问题: 该算法只对a=2进行测试,如果n为合数且输出为“素 数”,则称n为基2伪素数.例如341满足上述条件,但 是341是合数
8 Fermat 小定理：如果 n 为素数，则对所有的正整数 a ≠ 0(modn) 有 an−1≡1(mod n) 测试素数的算法： 令 a=2, 检测 an−1≡1(mod n)? 如果回答“是”，输出“素数”；否则输出“合数”. 分析： 时间 T(n)=O(log3n) 问题： 该算法只对 a=2 进行测试, 如果 n 为合数且输出为“素 数”，则称 n 为基 2 伪素数. 例如 341 满足上述条件，但 是 341 是合数. 有限域应用----素数测试问题