Trong bài trước chúng ta nói về đảo nghịch modulo và chúng ta nói rằng thuật toán của Euclid
sẽ cho chúng ta 1 cách hiệu quả để tìm ra nghịch đảo của một phần tử theo modulo N.
Trong phần này chúng ta sẽ tiếp tục tiến đến
thế kỉ 17 và 18 để nói về
Fermat và Euler (hâm mộ hai bác này quá ;). Trước khi làm việc đó thì tôi sẽ ôn lại cho các bạn một chút
những gì đã trình bày ở phần trước. Như mọi khi thì tôi kí hiệu N
là một giá trị nguyên dương có n bit.
Hay có thể nói N nằm giữa 2 mũ n và 2 mũ n+1. Ta cũng kí hiệu p
là một số nguyên tố nào đó. Bây giờ ta sẽ coi ZN như là một tập hợp số nguyên từ 0
tới N-1 và ta có thể sử dụng phép cộng và nhân modulo N.
Chúng ta cũng sử dụng ZN* là một tập các phần tử nghịch đảo của ZN và cũng đã chứng minh một bổ đề đơn giản
rằng X là khả nghịch khi và chỉ khi X
và N nguyên tố cùng nhau. Không chỉ có thế,ta cũng đã hoàn toàn hiểu được phần tử nào là khả nghịch
phần tử nào không.Ta cũng đã biết một thuật toán rất hiệu quả dựa trên
thuật toán Euclidean mở rộng để tìm nghịch đảo của một phần tử trong ZN.
thời gian chạy của thuật toán này chỉ xấp xỉ bình phương của n.
n số bit của số N.
Bây giờ chúng ta sẽ đi từ thời Hi Lạp tới thế kỷ 17
và nói về Ferma. Ferma là người đã tạo ra rất nhiều định lý quan trọng. Một trong số đó tôi muốn trình bày hôm nay sẽ như sau.
Giả sử tôi đưa cho các bạn số nguyên tố p. Lúc đó bất cứ
phần tử X nào thuộc tập ZP*,
nếu tôi tính X^(p-1) thì tôi sẽ được một phần tử thuộc ZP.
Một ví dụ như sau: P=5, nếu tôi lấy 3 mũ P - 1
3 mũ 4, kết quả là 81
và cũng bằng 1 theo modulo 5. phù hợp với định lý của Fermat
Một điều rất lý thú là Fermat không chứng minh định lý này
mà phải 100 năm sau mới có người chứng minh nó
hơn nữa anh ta lại chứng minh một định lý tổng quát hơn cả định lý gốc
Bây giờ ta sẽ xem thử một ứng dụng của định lý Fermat.
nhắc lại, p là một số nguyên tố
Ta biết được gì? Ta biết X ^ (p-1) = 1.
ta có thể viết, X nhân X mũ p trừ 2.
kết quả vẫn là một.
điều này chứng tỏ, X mũ p trừ 2 là nghịch đảo của X
đây lại là một thuật toán khác để tìm nghịch đảo của X khi modulo cho một số nguyên tố
đơn giản chỉ cần lấy X mũ p trừ 2, ta sẽ được nghịch đảo của X
đây là một cách tốt để tìm nghịch đảo với modulo một số nguyên tố
nhưng nó có hai nhược điểm so với thuật toán của Euclid.
Đầu tiên là nó chỉ hoạt động với modulo nguyên tố. Euclid thì khác, cũng làm việc với modulo là hợp số
thứ hai, thuật toán này ít hiệu quả hơn
khi ta nói về thuật toán tính lũy thừa theo modulo ở phần cuối của video
bạn sẽ thấy thời gian chạy của nó sẽ là lập phương chiều dài của p
hay cách khác là log của P lập phương
thuật toán của Euclid thì lại có thể tính
nghịch đảo trong thời gian tỉ lệ với bình phương chiều dài của p
thế là thuật toán mới này vừa ít tổng quát hơn và cũng kém hiệu quả hơn so với Euclid.
Số nguyên tố rất quan trọng
ta sẽ sử dụng nó trong vài tuần tới.
tôi sẽ trình bày một ứng dụng của định lý Fermat
Giả sử ta muốn tạo ra một số nguyên tố ngẫu nhiên rất lớn, khoảng một nghìn bit hoặc nhiều hơn.
Số ta đang tìm lớn của 2 mũ 1024.
có một thuật toán xác suất rất đơn giản để làm điều này. Ta cần chọn ngẫu nhiên một số
nguyên trong khoảng nào đó, sau đó kiểm tra xem số nguyên này có thỏa định lý của Fermet hay không?
Ta sẽ kiểm tra
sử dụng cơ số 2, ta kiểm tra xem 2 mũ p trừ 1 có bằng 1 trong Zp hay không
nếu kết quả là không, thì ta biết chắc rằng p không phải là số nguyên tố
nếu vậy, ta sẽ trở lại bước 1 với một số nguyên tố khác
Ta cứ làm lại, làm lại
cho tới khi nào ta được một số thỏa điều kiện này.
khi đó ta dừng thuật toán và xuất kết quả
Tuy khá là khó để chứng minh
nhưng nếu một số vượt qua được điều kiện trên thì *cực kì* có khả nănglà số nguyên tố.
xác suất mà p không là số nguyên tố là cực kì nhỏ.
khoảng cở 2 mũ -60 cho một số dài 1024 bit
khi số bit càng nhiều thì xác suất một số thỏa điều kiện mà lại không phải là số nguyên tố
giảm xuống 0 rất là nhanh. Đây là một thuật toán thú vị ;)
Ta nhận ra là không thể đảm bảo kết quả là nguyên tố
những gì ta biết là nó rất, rất có thể là nguyên tố.
nói khác đi, nếu nó không phải là số nguyên tố thì ta cực kì không may mắn.
Xác suất không may nắm nhỏ đến mức *có thể bỏ qua*
nếu bạn nhìn vào tập tất cả các số có 1024 bit.
tập các số nguyên tố ở đây,
và sau đó một tập nhỏ các hợp số mà qua được phép thử,
ta gọi chúng là FP. Có một phần rất nhỏ hợp số sẽ qua được điều kiện kiểm tra
Tuy nhiên vì ta chọn một cách ngẫu nhiên
một cái ở đây, ở đâu, ở đâu, và cứ như thế, ta chọn những số nguyên ngẫu nhiên
xác suất mà ta chọn phải FP là rất nhỏ
nhỏ tới mức có thể bỏ qua được (negligible)
có thể chứng được mình tập FB là cực nhỏ.
chọn ngẫu nhiên một số thì rất khó mà trúng phải FP
Thật ra đây không phải là thuật toán tốt nhất để sinh ra số nguyên tố
ta có những thuật toán tốt hơn nhiều
thậm chí ta có những thuật toán rất hiệu quả
để kiểm tra một số có phải là số nguyên tố
một cách chắc chắn
dù sao thì phép thử Fermat cũng là một phép thử rất đơn giản và dễ thực hiện để kiểm tra số nguyên tố
Điểm đáng chú ý cuối cùng ở đây
là, cần bao nhiều vòng lặp để
tìm ra một số nguyên tố. Một kết quả cổ điển
được gọi là định lý số nguyên tố, nói ràng, sau vài trăm vòng lặp
ta sẽ tìm được một số nguyên tố với xác suất cao.
Giờ thì ta đã hiểu được định lý Fermat
tiếp theo ta sẽ nói về cấu trúc của ZP*
Ta tiến thêm 100 năm nữa
vào thế kỉ 18, để gặp gỡ Euler.
Điều đầu tiên, Euler nhìn nhận ZP*, theo toán học hiện đại, là một nhóm vòng (cyclic group).
Nhóm vòng, nghĩa là sao?
nó có nghĩa là tồn tại phần tử nào G nào đó thuộc ZP*, sao cho nếu ta lấy G
và lấy mũ, G bình phương, G lập phương, v.v. Cứ tiếp tục như vậy
cho đến khi tới G mũ p trừ 2. Lưu ý là không ra khỏi G mũ p trừ 2
vì ta biết, theo định lý Fermat rằng, G mũ p - 1 bằng 1
vì vậy ta sẽ lập lặp một. Nếu ta tới G mũ p - 1. thì
G mũ p sẽ bằng G, G mũ p + 1 sẽ bằng G bình phương và cứ tiếp tục như vậy
Ta sẽ được sự lại nếu tiếp tục với mũ cao hơn
vì vậy chỉ cần dừng lại ở mũ p - 2
Euler đã chỉ ra rằng có một phần tử G như vậy,
nếu ta duyệt qua tất cả các mũ thì sẽ thấy nó sẽ phủ hết toàn bộ nhóm ZP*
Các lũy thừa của G cho ta tất cả phần tử thuộc ZP*.
G gọi là phần tử sinh. G sinh ra ZP*
Xét một ví dụ, P = 7
xem tất cả những lũy thừa của 3. 3 bình phương, 3 lập phương, 3 mũ 4,
3 mũ 5. 3 mũ 6 = 1 modulo 7, theo định lý Fermat.
không cần xem xét 3 mũ 6, vì ta biết nó sẽ là 1
Tôi đã tính những lũy thừa này.
Bạn thấy đấy, tất cả phần từ trong Z7* đều ở đây
ta có 2, 3, 4, 5, 6.
ta sẽ nói rằng 3 là phần tử sinh của Z7 *.
bây giờ tôi sẽ chỉ ra, không phải phần tử nào cũng là phần tử sinh. ví dụ, nếu ta xem xét tất cả lũy thừa của 2
nó không thể sinh ra toàn bộ nhóm. 2 mũ 0 được 1
2 mũ 1 được 2, 2 mũ 2 được 4, 3 mỹ 3 được 8, chính là 1 modulo 7.
Do đó ta đã lặp lại
2 mũ 4 sẽ là 2, 2 mũ 5 sẽ là 4, và cứ thế...
Nếu nhìn vào đây, thì ta chỉ thấy 1, 2, 4
ta không có được toàn một nhóm, dó đó 2 không là phần tử sinh của Z7 *
Đôi khi ta được cho một phần tử G của ZP*
nếu ta nhìn tất cả lũy thừa của G, kết quả sẽ là một nhóm được sinh ra bởi G
Tất cả đều là lũy thừa của G. Ta có được một nhóm multiplicative
không quan trọng về kĩ thuật. mấu chốt ở đây là
ta sẽ gọi tất cả những lũy thừa của G, là nhóm được sinh ra bởi G.
thực ra kí hiệu này không được thông dụng,
để kí hiệu nhóm sinh ra bởi G. Ta gọi bậc của G trong Zp* là
kích thước của nhóm được sinh ra bởi G.
bậc của G trong ZP* là kích thước của nhóm này. Cách khác để nghĩ về số này
nó là số nguyên A nhỏ nhất sao cho G mũ A bằng 1
cơ bản nó là số mũ nhỏ nhất của G kết quả là 1
Dễ thấy điều này nếu ta nhìn vào các lũy thừa của G
G, G bình phương, G lập phương và tiếp tục, ...
cho đến khi ta được 1. Và ta xem số mũ này là bậc của G
Điều này đơn giản bằng 1 theo định nghĩa
không cần phải xem xét của lũy thừa cao hơn. Ta chỉ cần dừng ở đây
kết quả là kích thước của tập
là bậc của G, số này chính là số mũ nhỏ nhất
mà G lũy thừa cho ra 1 trong Zp.
hơi khó hiểu một tí
nhưng sẽ dễ dàng với một vài ví dụ. Số nguyên tố của ta vẫn là 7
hãy xem xét bậc của các phần tử
bậc của 3 là nhiêu? Ta đang tìm kích thước của nhóm
được sinh ra bởi 3 theo modulo 7. ta nói rằng 3 sinh ra Z7 *
nó sinh ra mọi phần tử của Z7*. có 6 phần tử cả thẩy.
do đó ta nói 3 có bậc là 6. tương tự,
bậc của 2 modulo 7 là nhiêu? ta đã thấy đán án.
Tôi hỏi bạn, bậc của hai,
là bao nhiêu? Câu trả lời là 3, đơn giản vì nếu ta nhìn vào
tập các lũy thừa của 2, ta có 1, 2, 2 bình phương (2 mũ 3 = 1)
đây là toàn bộ lũy thừa của 2 (modulo 7)
có 3 phần tử, vậy bậc của 2 (modulo 7) là 3
tôi sẽ hỏi một câu khác
bậc của 1 (modulo 7) là nhiêu? Câu trả lời là 1. bởi vì nếu nhìn vào nhóm được sinh ra bởi 1
chỉ có một số, chính là số 1
tôi sẽ luôn được 1 với mọi lũy thừa.
do đó bậc của 1 (modulo 7) là 1
thật ra sẽ luôn là 1 với modulo bất kì số nguyên tố nào. Có một định lý quan trọng của Lagrange (thêm một siêu nhân)
thật ra
Định lý của Langrage về cơ bản chỉ ra rằng nếu bạn nhìn vào bậc của G (modulo p)
thì nó luôn được chia hết bởi p-1. Trong hai ví dụ, ta thấy
6 được chia hết bơi 7 - 1, 6 chia hết cho 6, tương tư
3 cũng chia hết bởi 7 - 1, tổng quát, bậc này
sẽ luôn là một thừa số của p - 1.
rất khó để có thể suy ra được định lý Fermat trược tiếp từ
định lý Lagrange.
Định lý Fermet theo một cách hiểu khác được suy ra từ định lý Lagrange
Lagrange, tìm ra nó vào thế kỉ 19
ta đã có một hình trình xuyên thời gian từ thời Hi Lạp cổ đại đến
cuối thế kỉ 19. Có nhiều hệ mã hóa
sử dụng nhiều kiến thức toán học của thế kỉ 19.
giờ thì ta đã rõ về cấp trúc của ZP*. tổng quát hóa điều này cho hợp số,
cấu trúc của ZN*. Ở đây ta sẽ thấy định lý của Euler
là một định lý tổng quát so với định lý Fermat.
Euler định nghĩa hàm sau. cho số nguyên N, phi
của N là hàm số, trả về kích thức tập ZN*
gọi là hàm Phi Euler ;)
ví dụ, ta có Z12* chứa bốn phần tử, 1, 5, 7, 11
do đó phi của 12 là 4
một câu đố, phi của p là nhiêu?
cơ bản thì đây là kích thước của Zp*.
chứa tất cả phần của của ZP trừ số 0
do đó phi của p là p - 1. có một trường hợp đặc biệt
tôi sẽ chỉ ra ở đây, ta sẽ dùng lại cho hệ mã RSA
nếu N là tích của hai số nguyên tố, thì phi của N chính là N - P - Q + 1
để tôi chỉ ra vì sao điều này lại đúng. Về cơ bản N là kích thước của ZN. giờ ta cần
loại bỏ tất cả những phần tử không nguyên tố cùng nhau với N.
làm sao để một phần tử không nguyên tố cùng nhau với n? nó phải chia hết bởi p hoặc là chia hết bởi q
có bao nhiêu phần tử từ 0 tới n - 1 được chia hết
bởi p, có chính xác q phần tử như vậy. Có bao nhiêu phần tử chia hết
bởi q, có p phần tử như vậy.
ta trừ p để lại ra những phần tử chia hết bởi q. trừ q để loại bỏ
những phần tử chia hết bỏi p. Lưu ý là ta đã loại bỏ phần tử 0 hai lần
vì nó được chia hết bởi cả p và q, do đó, ta cộng thêm một
kết quả là phi(N) = N - P - Q + 1
cách viết khác là (p-1)x(q-1)
ta sẽ quay lại vấn đề này khi nói về hệ mã RSA.
ở đây ta chỉ mới định nghĩa hàm phi Euler.
Euler đã có một chứng minh tuyệt vời rằng
với mọi phần tử X nào của ZN* . thì X mũ phi(N)
bằng 1 trong ZN. Đây là một tổng quát hóa của định lý Fermat
định lý Fermat chỉ áp dụng cho số nguyên tố
với số nguyên tố p, ta có phi(p) = p - 1. ta chỉ cần viết p - 1 ở đây
và ta lại có được định lý Fermat.
vẻ đẹp của định lý Euler là nó áp dụng cho cả hợp số
không chỉ riêng số nguyên tố. Hãy nhìn vào ví dụ, 5 mũ phi(12)
5 là một phần tử của Z12*. Nếu ta lấy 5 mũ 12, ta sẽ được
ta sẽ được 1, ta biết rằng, phi(12) = 4 do đó
5 mũ 4 là 625,
bằng 1 modulo 12
tuy đây chỉ là một ví dụ, nhưng không khó để có thể chứng minh
định lý Euler. sự thật là
định lý Euler lại là một trường hợp đặc biệt của định lý Lagrange
okay, ta đã biết đây là một trường hợp tổng quát của định lý Fermat và
thực tế thì, định lý Euler là cơ sở cho hệ mã RSA
Tôi sẽ dừng ở đây, ta sẽ tiếp tục với những phương trình bậc hai
ở phần tiếp theo.