为合数. 可以判定 n 为合数 然后进行上述测试. 随机选择正整数 a∈{2,3,…, n-1}, 然后进行上述测试 可 ∈ 以证明该算法每次测试出错的概率至多为 1/2. 重复运行 k 次， 可以将出错概率降到至多 2-k. 2012-2-20
25
素数判定算法 素数判定算法
Miller and Rabin, WITNESS算法 WITNESS(a,n) 判定n 是否为素数，a是小于 n的整数 返回值： TRUE: n一定不是素数 FALSE: n可能是素数 应用： 随机选择a < n, 计算s次， 如果每次都返回FALSE， 则这时n是素数的概率为 (1 - 1/2s)
2012-2-20
21
素数判定
命题：如果 p是素数，则方程 命题 x2≡1(mod p) 只有两个解±1。
2012-2-20
22
素数判定命题的证明
证明 x2(mod n)≡1 ⇔ x2-1≡0(modn) ≡ ≡ ⇔ (x+1)(x-1)≡0(modn) ≡ ⇔ x+1≡0 或 x-1≡0 ≡ ≡ 域中没有零因子） （域中没有零因子） ⇔ x=-1 或 x=1 ±≠1的根为非平凡的 称x±≠ 的根为非平凡的 ±≠ 的根为非平凡的. 根据该命题，如果方程有非平凡的根， 为合数. 根据该命题，如果方程有非平凡的根，则n为合数 例 为合数 如: x2(mod 5) ≡ 1 ⇔ x=1 或 x=4 x2(mod 12) ≡1 ⇔ x=1 或 x=5 或 x=7 或 x=11 5和7是非平凡的根 是非平凡的根. 和 是非平凡的根
2012-2-20 6
n mБайду номын сангаас n m ∑ ai ∑ b j = ∑∑ ai b j i =1 j =1 i =1 j =1
交换环,含幺环,无零因子环
定义10.12: 设<R,+,*>是环，
如果<R,*>是可交换的，则称<R,+,*>是交 换环. 如果<R,*>含有幺元，则称<R,＋,*>是含幺 环. 无零因子环 ab=0 ⇒ a=0 或b=0
26
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
2012-2-20
子环
设<R,+,*>是一个环， S⊆R非空，若<S, +,*>构成环，称<S, +,*>是<R,+,*>的一个 子环。那么<R,*>中的单位元1必定也是 <S,*>中的单位元。x在R 中的逆元也是 在S 中的逆元。 <R,+,*>的子环也是代数系统<R,+,*>的子 代数
2012-2-20 27
群
(1) <Z,+>交换群， |0|=1 (2) <Z,*>半群 <Z,+,*>？
*对+有分配律 a*0=0*a=0 a* (-b)=(-a) *b=-(ab) (-a) * (-b)=a*b ……
2012-2-20 1
环与域
——具有两个二元运算的代数系统 <R,*>,<R,+> “*”，“＋”之间有联系 <R,+,*>
a
2i m
(mod n)
是否为 1 和 n-1,且它的后一项是否为 1. 且它的后一项是否为 如果其后项为 1，但本项不等于 1 和 n-1, 则它就是 ， 非平凡的根， 不是素数. 非平凡的根，从而知道 n 不是素数
2012-2-20 24
例如 n=561, n-1=560=24⋅ 35, 假设 a=7, 构造的序列为
2012-2-20
9
整环举例
<Z,+, *> 为整环 <2Z,+, *> 非整环，乘法没有单位元 <Zp,+, *> 为整环（p为素数） <P(S),⊕,∩>非整环，有零因子，A，∼A， ∼ A∩∼A＝φ
2012-2-20
10
整环的性质
性质1:整环<R,+,*>的无零因子条件等价于乘 法消去律，即对于c≠0和c*a=c*b必有a=b. 证明： ⇒ 若无零因子，并设c≠0和c*a=c*b 则有c*a－c*b＝c* (a-b)=0 ∴必有a-b=0即 a=b ⇐ 若消去律成立，设a≠0，a*b=0 则a*b＝a*0, 即b=0
2012-2-20
11
问题
p,q为不等的素数 ， 是否存在 阶的整 为不等的素数， 是否存在pq阶的整 为不等的素数 环？
阶的整环， 证：假设R为pq阶的整环， 假设 为 阶的整环 阶的Abel群. 则<R,+>为pq阶的 为 阶的 群 存在p阶元 阶元a， 阶元 阶元b. 存在 阶元 ，q阶元 为循环群， 所以 |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为零因子 矛盾 为零因子. 为零因子 矛盾.
2012-2-20 12
域
定义10.12:<R,+, *>为代数系统，若满 足： (1)<R,+>为阿贝尔群 (2)<R\{0},*>为阿贝尔群 (3)运算*对运算+可分配 则称<R,+, *>为域 <Q,+, *>域，但<Z,+, *>非域
2012-2-20 13
域举例
<Z,+, *>非域 <Q,+, *>域 <Zp,+, *>有限域（p为素数）
2012-2-20
4
多项式环
系数属于实数的所有x的多项式所组成的 集合记作R[x],R[x]对于多项式的加法， 乘法构成一个环(多项式环)
2012-2-20
5
环的性质
定理10.14:设<R,+, *>是一个环，则对任意的 a,b,c∈R,有 (1) a*0=0*a=0 (2) a* (-b)=(-a) *b=-(ab) (3) (-a) * (-b)=a*b (4) a* (b-c)=a*b-a*c (5) (b-c) *a=b*a-c*a (6)∀a1, a2,…… an, b1, b2,…… bm, n,m>1 其中，0为加法幺元，-a是a的加法逆元， 并将a+(-b)记为a-b
2012-2-20
2
环
定义10.11:设<R,+, *>是一个代数系统， 如果满足 (1) <R,+>为阿贝尔群 (2) <R, *>是半群 (3) *对＋是可分配的 则称<R,+, *>是环
2012-2-20
3
举例
数环Z,Q,R,C 关于普通数的加法与乘法 <Zn, ⊕, ⊗> ⊗ <Mn(R), +, ⋅> <P(B), ⊕, ∩> 符号说明：0, 1, -x, x-1, nx, xn, x-y, xy,-xy
2012-2-20
14
小结整环与域
加法
整环
封闭 可结合 有幺元 有逆元 可交换
乘法
整环
封闭 可结合 有幺元 可交换 无零因子
域与整环同
域比整环多
除零元外都有逆元
乘法对加法有分配性
2012-2-20
15
域和整环
性质2 :域一定是整环 (只需验证无零因子性，即乘法消去律，显 然) 每个非零元都有乘法逆元的整环称为域。
2012-2-20
16
有限整环必定是域
性质3:有限整环必定是域 (只需验证每个非零元都有乘法逆元，换 言之只需证A-{0}为群，∵有限半群只要 满足消去律即可为群，显然)
<Zp,+, *>有限域（p为素数）
2012-2-20 17
有限域
有限的整环都是域. 有限的整环都是域 有限域的特征
F为有限域，1在<F,+>中的阶为域 的特征 为有限域， 在 中的阶为域F的特征 为有限域 中的阶为域 的特征.
同态象
定义:<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,+, *>的一个同态象.
Zp的特征为p. 的特征为 为有限域， 使得|F|=pn, 设F为有限域，则存在素数 使得 为有限域 则存在素数p使得
2012-2-20
18
Fermat定理
Fermat定理 定理：如果p是素数，a是正整数， 定理 p不能整除a，那么，ap-1≡1(mod p) 考虑有限域(Zp,+,*)，| Zp* |=p-1