2018/6/29
2
环
定义10.11:设<R,+, *>是一个代数系统， 如果满足 (1) <R,+>为阿贝尔群 (2) <R, *>是半群 (3) *对＋是可分配的 则称<R,+, *>是环
2018/6/29
3
举例
数环Z,Q,R,C 关于普通数的加法与乘法 <Zn, ⊕, ⊗> <Mn(R), +, ⋅> <P(B), ⊕, ∩>
2018/6/29
19
素数测试算法
令a=2, 检测an-11(mod n)? 如果回答“是”，输出“素数”；否则输出“合 数”. 分析： 时间 T(n)=O(log3n) 问题： 该算法只对a=2进行测试, 如果n为合数且输出 为“素数”，则称n为基2伪素数. 例如341满足 上述条件，但是341是合数.
F为有限域，1在<F,+>中的阶为域F的特征.
Zp的特征为p. 设F为有限域，则存在素数p使得|F|=pn,
2018/6/29
18
Fermat小定理
Fermat 小定理：如果 p 是素数， a 是正整 数，p不能整除a，那么，ap-1≡1(mod p)
考虑有限域(Zp,+,*)，| Zp* |=p-1
2018/6/29 20
素数测试的随机算法
改进方法：
随机选取2--n-2中的数，进行测试. 例如取a=3，则 3340(mod 341) 56，341不是素数.
新问题：
Fermat小定理的条件只是必要条件，满足条件的可能是合数. 对所有与n互素的正整数a，都满足上述条件的合数n称为 Carmichael 数，如561，1105，1729，2465等. Carmichael数 非常少，小于108的只有255个. 可以证明：如果n为合数，但不是Carmichael数，采用随机选 取2—n-2中的数进行测试，测试n为合数的概率至少为1/2. 但 是这个算法不能解决 Carmichael数的问题.
2018/6/29 23
Miller-Rabin算法
设 n 为奇素数，存在 q,m 使得 n-1=2qm, (q1). 序列
a (mod n), a
m
2m
(mod n), a
4m
(mod n), ... , a
2q m
(mod n)
的最后一项为 an-1(mod n), 且每一项是前面一项的平方 . 对于任意 i（i=0,1,…q-1）, 判断
2018/6/29
WITNESS(a,n) 判定n 是否为素数，a是小于 n的整数
返回值： TRUE: n一定不是素数 FALSE: n可能是素数 应用： 随机选择a < n, 计算s次， 如果每次都返回FALSE， 则这时n是素数的概率为
(1 - 1/2s)
26
子环
设<R,+,*>是一个环， SR非空，若<S, +,*>构成环，称<S, +,*>是<R,+,*>的一个 子环。那么<R,*>中的单位元1必定也是 <S,*>中的单位元。x在R 中的逆元也是 在S 中的逆元。 <R,+,*>的子环也是代数系统<R,+,*>的子 代数
如果<R,*>是可交换的，则称<R,+,*>是交 换环. 如果<R,*>含有幺元，则称<R,＋,*>是含幺 环. 无零因子环 ab=0 ⇒ a=0 或b=0
2018/6/29
7
实例
<P(S),⊕,∩> 作成环(且为含幺交换)
加法幺元为φ，乘法幺元为S，A的加法逆元 为A
数环, < Zp,,>பைடு நூலகம்为无零因子环当且仅当 p 为素数.
2018/6/29
12
域
定义10.12:<R,+, *>为代数系统，若满 足： (1)<R,+>为阿贝尔群 (2)<R\{0},*>为阿贝尔群 (3)运算*对运算+可分配 则称<R,+, *>为域 <Q,+, *>域，但<Z,+, *>非域
13
2018/6/29
域举例
<Z,+, *>非域 <Q,+, *>域 <Zp,+, *>有限域（p为素数）
a
2i m
(modn)
是否为 1 和 n-1,且它的后一项是否为 1. 如果其后项为 1，但本项不等于 1 和 n-1, 则它就是 非平凡的根，从而知道 n 不是素数.
2018/6/29 24
例如 n=561, n-1=560=24 35, 假设 a=7, 构造的序列为
7 35 (mod 561) 241, 7 7 7 7
2018/6/29
11
问题
p,q为不等的素数，是否存在pq阶的整环？
证：假设R为pq阶的整环， 则<R,+>为pq阶的Abel群. 存在p阶元a，q阶元b. 所以 |a+b|=pq, <R,+>为循环群， 令c=a+b为生成元. R={0,c,2c, …, (pq-1)c} 取x=pc, y=qc, 则 xy=(pc)(qc) = pqc2 =0 x,y为零因子. 矛盾.
2018/6/29
21
素数判定
命题：如果
p是素数，则方程 x2≡1(mod p) 只有两个解±1。
2018/6/29
22
素数判定命题的证明
证明 x2(mod n)1 x2-10(modn) (x+1)(x-1)0(modn) x+10 或 x-10 （域中没有零因子） x=-1 或 x=1 称x1的根为非平凡的. 根据该命题，如果方程有非平凡的根，则 n为合数 . 例 如: x2(mod 5) 1 x=1 或 x=4 x2(mod 12) 1 x=1 或 x=5 或 x=7 或 x=11 5和7是非平凡的根.
2018/6/29
14
小结整环与域
加法
乘法
整环
整环
封闭 可结合 有幺元 有逆元 可交换
封闭 可结合 有幺元 可交换 无零因子 除零元外都有逆元
域与整环同
域比整环多
乘法对加法有分配性
2018/6/29
15
域和整环
性质2 :域一定是整环 (只需验证无零因子性，即乘法消去律，显 然)
2018/6/29
8
整环
定义10.12:无零因子的含幺交换环称为整环。
整环满足：
1. <R,+>为阿贝尔群
2. <R,*>是可交换含乘法单位元，且无零因子 3.运算*对运算＋可分配
2018/6/29
9
整环举例
<Z,+, *> 为整环 <2Z,+, *> 非整环，乘法没有单位元 <Zp,+, *> 为整环（p为素数） <P(S),⊕,∩>非整环，有零因子，A，A， A∩A＝φ
每个非零元都有乘法逆元的整环称为域。
2018/6/29
16
有限整环必定是域
性质3:有限整环必定是域
(只需验证每个非零元都有乘法逆元，换 言之只需证A-{0}为群，∵有限半群只要 满足消去律即可为群，显然)
<Zp,+, *>有限域（p为素数）
17
2018/6/29
有限域
有限的整环都是域. 有限域的特征
可以判定 n 为合数. 随机选择正整数 a{2,3,…, n-1}, 然后进行上述测试. 可 以证明该算法每次测试出错的概率至多为 1/2. 重复运行 k 次，
-k 可以将出错概率降到至多 2 . 2018/6/29
25
素数判定算法
Miller and Rabin, WITNESS算法
1. 令bkbk-1…b0 为(n-1)的二进制表示， 2. d 1 3. for i k downto 0 4. do x d 5. d (d d) mod n 6. if d = 1 and x 1 and x n-1 7. then return TRUE 8. if bi = 1 9. then d (d a) mod n 10. if d 1 11. then return TRUE 12. return FALSE
27
2018/6/29
同态象
定义:<R1,+, *>，<R2,+, *>为两个代数 系统，如果存在一个从R1到R2的映射f， s.t.对于任给的a,b∈ R1 ，有 (1)f(a+b)=f(a)+f(b) (2)f(a*b)=f(a) *f(b) 则称f为由< R1,+, *>到< R2,+, *>的一 个同态映射，并称<f(R1),+, *>为< R1,+, *>的一个同态象.
