BÁO CÁO TIỂU LUẬN
Môn học: Mật mã và AN TOÀN DỮ LIỆU
Đề bài: TRÌNH BÀY NHÓM Zn, Zn*
H c viên: Nguy n Văn Uyọ ễ
Mã h c viên: 13025208ọ
Email:
Sđt: 01656253187
Gi ng viên h ng d n: PGS.TS. Tr nh Nh t Ti nả ướ ẫ ị ậ ế
Nội dung trình bày:
•
Khái niệm về nhóm Zn, Zn*
•
Ví dụ minh họa
•
Các bài toán về nhóm Zn, Zn*
•
Ứng dụng nhóm Zn, Zn*. Ví dụ
Khái niệm về nhóm Zn, Zn*
Khái niệm về nhóm Zn
•
Khái niệm: Cho n là một số nguyên dương.
Tập hợp các số nguyên không âm bé hơn n
được gọi là nhóm Zn
•
Kí hiệu Zn= {0,1,2,…,n-1}
•
Ví dụ:
•
Z7= {0,1,2,3,4,5,6}
•
Z26= {A, B,…,X, Y, Z} – Bảng chữ cái

nhân), pt trung lập e = 1.
•
Tổng quát (Zn * , phép nhân mod n ) không phải là nhóm
Cyclic.
•
Nhóm nhân Zn * là Cyclic chỉ khi n có dạng: 2, 4, pk, hay 2pk
với p là nguyên tố lẻ.
Hàm Euler
•
Cho số nguyên dương n, số lượng các số nguyên dương bé hơn n và nguyên tố
cùng nhau với n được ký hiệu (n) và gọi là hàm Euler.
•
Nhận xét: Nếu p là số nguyên tố, thì (p) = p-1
•
Ví dụ:
•
Tập các số nguyên không âm nhỏ hơn 7 là Z 7 = {0, 1, 2, 3, 4, 5, 6}.
•
Do 7 là số nguyên tố, nên Tập các số nguyên dương nhỏ hơn 7 và nguyên tố
cùng nhau với 7 là Z 7 * ={1, 2, 3, 4, 5, 6}. Khi đó /Z/ = (p) = p-1 = 7 - 1 = 6.
•
Định lý: về Hàm Euler. Nếu n là tích của hai số nguyên tố n = p.q, thì (n) = (p).
(q) = (p-1).(q-1).
•
(n) = |Z n * |
Một số kết quả đã được chứng minh
•
Định lý Lagrange: Nếu G là nhóm cấp n và α ∈ G, thì
Cấp của α là ước của n.
•

• xi+1= xi-1 – qxi;
• i=i+1;
•
end
• x:=xi – 1;
• if x>0 then return x
•
else return n+x
Ví dụ:
Tìm phần tử nghịch đảo của 213
trong Z466
Tức là phải giải phương trình 213
x ≡ 1 (mod 466), x sẽ là phần tử
nghịch đảo của 213. Tương đương
x= 213-1mod 466
Ví dụ:
Tìm phần tử nghịch đảo của 213
trong Z466
Tức là phải giải phương trình 213
x ≡ 1 (mod 466), x sẽ là phần tử
nghịch đảo của 213. Tương đương
x= 213-1mod 466
i gi xi q
0 466 0 \
1 213 1 2
2 40 -2 5
3 13 11 3
4 1 -35 13
5 0
Return n+x=466+xi-1 =466-