WEBVTT

00:00:00.000 --> 00:00:04.220
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

00:00:04.220 --> 00:00:08.238
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.

00:00:08.238 --> 00:00:12.256
Trong phần này chúng ta sẽ tiếp tục tiến đến

00:00:12.256 --> 00:00:15.866
thế kỉ 17 và 18 để nói về

00:00:15.866 --> 00:00:19.986
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

00:00:19.986 --> 00:00:24.257
những gì đã trình bày ở phần trước. Như mọi khi thì tôi kí hiệu N

00:00:24.257 --> 00:00:28.427
là một giá trị nguyên dương có n bit.

00:00:28.427 --> 00:00:32.445
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

00:00:32.445 --> 00:00:36.761
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

00:00:36.761 --> 00:00:41.370
tới N-1 và ta có thể sử dụng phép cộng và nhân modulo N.

00:00:41.370 --> 00:00:46.186
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

00:00:46.186 --> 00:00:51.243
rằng X là khả nghịch khi và chỉ khi X

00:00:51.243 --> 00:00:55.879
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

00:00:55.879 --> 00:01:00.635
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

00:01:00.635 --> 00:01:05.572
thuật toán Euclidean mở rộng để tìm nghịch đảo của một phần tử trong ZN.

00:01:05.572 --> 00:01:10.388
thời gian chạy của thuật toán này chỉ xấp xỉ bình phương của n.

00:01:10.388 --> 00:01:16.107
n số bit của số N.

00:01:16.107 --> 00:01:21.037
Bây giờ chúng ta sẽ đi từ thời Hi Lạp tới thế kỷ 17

00:01:21.037 --> 00:01:26.276
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.

00:01:26.276 --> 00:01:31.206
Giả sử tôi đưa cho các bạn số nguyên tố p. Lúc đó bất cứ

00:01:31.206 --> 00:01:36.260
phần tử X nào thuộc tập ZP*,

00:01:36.260 --> 00:01:41.130
nếu tôi tính X^(p-1) thì tôi sẽ được một phần tử thuộc ZP.

00:01:41.130 --> 00:01:46.061
Một ví dụ như sau: P=5, nếu tôi lấy 3 mũ P - 1

00:01:46.061 --> 00:01:50.645
3 mũ 4, kết quả là 81

00:01:50.645 --> 00:01:55.286
và cũng bằng 1 theo modulo 5. phù hợp với định lý của Fermat

00:01:55.286 --> 00:01:59.521
Một điều rất lý thú là Fermat không chứng minh định lý này

00:01:59.521 --> 00:02:04.337
mà phải 100 năm sau mới có người chứng minh nó

00:02:04.337 --> 00:02:09.122
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

00:02:09.122 --> 00:02:14.154
Bây giờ ta sẽ xem thử một ứng dụng của định lý Fermat.

00:02:14.154 --> 00:02:19.441
nhắc lại, p là một số nguyên tố

00:02:19.441 --> 00:02:24.664
Ta biết được gì? Ta biết X ^ (p-1) = 1.

00:02:24.664 --> 00:02:29.573
ta có thể viết, X nhân X mũ p trừ 2.

00:02:29.573 --> 00:02:34.087
kết quả vẫn là một.

00:02:34.087 --> 00:02:39.310
điều này chứng tỏ, X mũ p trừ 2 là nghịch đảo của X

00:02:39.310 --> 00:02:44.042
đâ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ố

00:02:44.042 --> 00:02:48.835
đơn giản chỉ cần lấy X mũ p trừ 2, ta sẽ được nghịch đảo của X

00:02:48.835 --> 00:02:53.508
đây là một cách tốt để tìm nghịch đảo với modulo một số nguyên tố

00:02:53.508 --> 00:02:58.301
nhưng nó có hai nhược điểm so với thuật toán của Euclid.

00:02:58.301 --> 00:03:02.528
Đầ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ố

00:03:02.528 --> 00:03:07.017
thứ hai, thuật toán này ít hiệu quả hơn

00:03:07.017 --> 00:03:10.911
khi ta nói về thuật toán tính lũy thừa theo modulo ở phần cuối của video

00:03:10.911 --> 00:03:15.345
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

00:03:15.345 --> 00:03:19.792
hay cách khác là log của P lập phương

00:03:19.792 --> 00:03:24.266
thuật toán của Euclid thì lại có thể tính

00:03:24.266 --> 00:03:30.343
nghịch đảo trong thời gian tỉ lệ với bình phương chiều dài của p

00:03:30.343 --> 00:03:36.512
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.

00:03:36.512 --> 00:03:41.473
Số nguyên tố rất quan trọng

00:03:41.473 --> 00:03:47.506
ta sẽ sử dụng nó trong vài tuần tới.

00:03:47.506 --> 00:03:52.155
tôi sẽ trình bày một ứng dụng của định lý Fermat

00:03:52.155 --> 00:03:57.226
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.

00:03:57.226 --> 00:04:02.006
Số ta đang tìm lớn của 2 mũ 1024.

00:04:02.006 --> 00:04:06.724
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ố

00:04:06.724 --> 00:04:11.938
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?

00:04:12.124 --> 00:04:17.153
Ta sẽ kiểm tra

00:04:17.153 --> 00:04:22.367
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

00:04:22.367 --> 00:04:27.271
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ố

00:04:27.271 --> 00:04:33.003
nếu vậy, ta sẽ trở lại bước 1 với một số nguyên tố khác

00:04:33.003 --> 00:04:37.284
Ta cứ làm lại, làm lại

00:04:37.284 --> 00:04:41.782
cho tới khi nào ta được một số thỏa điều kiện này.

00:04:41.782 --> 00:04:46.009
khi đó ta dừng thuật toán và xuất kết quả

00:04:46.009 --> 00:04:51.573
Tuy khá là khó để chứng minh

00:04:51.573 --> 00:04:56.305
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ố.

00:04:56.305 --> 00:05:01.398
xác suất mà p không là số nguyên tố là cực kì nhỏ.

00:05:01.398 --> 00:05:06.191
khoảng cở 2 mũ -60 cho một số dài 1024 bit

00:05:06.191 --> 00:05:10.744
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ố

00:05:10.744 --> 00:05:15.716
giảm xuống 0 rất là nhanh. Đây là một thuật toán thú vị ;)

00:05:15.716 --> 00:05:20.455
Ta nhận ra là không thể đảm bảo kết quả là nguyên tố

00:05:20.455 --> 00:05:25.021
những gì ta biết là nó rất, rất có thể là nguyên tố.

00:05:25.021 --> 00:05:29.587
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.

00:05:29.587 --> 00:05:34.298
Xác suất không may nắm nhỏ đến mức *có thể bỏ qua*

00:05:34.298 --> 00:05:40.230
nếu bạn nhìn vào tập tất cả các số có 1024 bit.

00:05:40.230 --> 00:05:45.233
tập các số nguyên tố ở đây,

00:05:45.233 --> 00:05:50.805
và sau đó một tập nhỏ các hợp số mà qua được phép thử,

00:05:50.805 --> 00:05:55.653
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

00:05:55.653 --> 00:06:00.626
Tuy nhiên vì ta chọn một cách ngẫu nhiên

00:06:00.626 --> 00:06:05.349
một cái ở đây, ở đâu, ở đâu, và cứ như thế, ta chọn những số nguyên ngẫu nhiên

00:06:05.349 --> 00:06:10.260
xác suất mà ta chọn phải FP là rất nhỏ

00:06:10.260 --> 00:06:15.082
nhỏ tới mức có thể bỏ qua được (negligible)

00:06:15.082 --> 00:06:20.591
có thể chứng được mình tập FB là cực nhỏ.

00:06:20.591 --> 00:06:25.266
chọn ngẫu nhiên một số thì rất khó mà trúng phải FP

00:06:25.266 --> 00:06:28.960
Thật ra đây không phải là thuật toán tốt nhất để sinh ra số nguyên tố

00:06:28.960 --> 00:06:32.654
ta có những thuật toán tốt hơn nhiều

00:06:32.654 --> 00:06:36.349
thậm chí ta có những thuật toán rất hiệu quả

00:06:36.349 --> 00:06:40.498
để kiểm tra một số có phải là số nguyên tố

00:06:40.498 --> 00:06:44.597
một cách chắc chắn

00:06:44.597 --> 00:06:48.595
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ố

00:06:48.595 --> 00:06:53.076
Điểm đáng chú ý cuối cùng ở đây

00:06:53.076 --> 00:06:57.468
là, cần bao nhiều vòng lặp để

00:06:57.468 --> 00:07:01.536
tìm ra một số nguyên tố. Một kết quả cổ điển

00:07:01.536 --> 00:07:05.820
được gọi là định lý số nguyên tố, nói ràng, sau vài trăm vòng lặp

00:07:05.820 --> 00:07:09.833
ta sẽ tìm được một số nguyên tố với xác suất cao.

00:07:09.833 --> 00:07:14.771
Giờ thì ta đã hiểu được định lý Fermat

00:07:14.771 --> 00:07:19.314
tiếp theo ta sẽ nói về cấu trúc của ZP*

00:07:19.314 --> 00:07:23.915
Ta tiến thêm 100 năm nữa

00:07:23.915 --> 00:07:28.576
vào thế kỉ 18, để gặp gỡ Euler.

00:07:28.576 --> 00:07:33.118
Đ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).

00:07:33.118 --> 00:07:38.014
Nhóm vòng, nghĩa là sao?

00:07:38.014 --> 00:07:42.734
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

00:07:42.734 --> 00:07:47.681
và lấy mũ, G bình phương, G lập phương, v.v. Cứ tiếp tục như vậy

00:07:47.681 --> 00:07:52.590
cho đến khi tới G mũ p trừ 2. Lưu ý là không ra khỏi G mũ p trừ 2

00:07:52.590 --> 00:07:57.296
vì ta biết, theo định lý Fermat rằng, G mũ p - 1 bằng 1

00:07:57.296 --> 00:08:02.178
vì vậy ta sẽ lập lặp một. Nếu ta tới G mũ p - 1. thì

00:08:02.178 --> 00:08:06.825
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

00:08:06.825 --> 00:08:11.825
Ta sẽ được sự lại nếu tiếp tục với mũ cao hơn

00:08:11.825 --> 00:08:16.590
vì vậy chỉ cần dừng lại ở mũ p - 2

00:08:16.590 --> 00:08:21.413
Euler đã chỉ ra rằng có một phần tử G như vậy,

00:08:21.413 --> 00:08:26.300
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*

00:08:26.300 --> 00:08:31.239
Các lũy thừa của G cho ta tất cả phần tử thuộc ZP*.

00:08:31.239 --> 00:08:35.997
G gọi là phần tử sinh. G sinh ra ZP*

00:08:35.997 --> 00:08:40.696
Xét một ví dụ, P = 7

00:08:40.696 --> 00:08:45.575
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,

00:08:45.575 --> 00:08:50.130
3 mũ 5. 3 mũ 6 = 1 modulo 7, theo định lý Fermat.

00:08:50.130 --> 00:08:54.917
không cần xem xét 3 mũ 6, vì ta biết nó sẽ là 1

00:08:54.917 --> 00:08:59.644
Tôi đã tính những lũy thừa này.

00:08:59.644 --> 00:09:04.431
Bạn thấy đấy, tất cả phần từ trong Z7* đều ở đây

00:09:04.431 --> 00:09:09.313
ta có 2, 3, 4, 5, 6.

00:09:09.313 --> 00:09:14.599
ta sẽ nói rằng 3 là phần tử sinh của Z7 *.

00:09:14.599 --> 00:09:19.886
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

00:09:19.886 --> 00:09:24.914
nó không thể sinh ra toàn bộ nhóm. 2 mũ 0 được 1

00:09:24.914 --> 00:09:29.650
2 mũ 1 được 2, 2 mũ 2 được 4, 3 mỹ 3 được 8, chính là 1 modulo 7.

00:09:29.650 --> 00:09:34.455
Do đó ta đã lặp lại

00:09:34.455 --> 00:09:39.766
2 mũ 4 sẽ là 2, 2 mũ 5 sẽ là 4, và cứ thế...

00:09:39.766 --> 00:09:44.697
Nếu nhìn vào đây, thì ta chỉ thấy 1, 2, 4

00:09:44.697 --> 00:09:49.981
ta không có được toàn một nhóm, dó đó 2 không là phần tử sinh của Z7 *

00:09:49.981 --> 00:09:55.831
Đôi khi ta được cho một phần tử G của ZP*

00:09:55.831 --> 00:10:01.901
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

00:10:01.901 --> 00:10:06.947
Tất cả đều là lũy thừa của G. Ta có được một nhóm multiplicative

00:10:06.947 --> 00:10:12.798
không quan trọng về kĩ thuật. mấu chốt ở đây là

00:10:12.798 --> 00:10:18.397
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.

00:10:18.397 --> 00:10:23.570
thực ra kí hiệu này không được thông dụng,

00:10:23.570 --> 00:10:30.010
để kí hiệu nhóm sinh ra bởi G. Ta gọi bậc của G trong Zp* là

00:10:30.010 --> 00:10:35.663
kích thước của nhóm được sinh ra bởi G.

00:10:35.663 --> 00:10:40.626
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

00:10:40.626 --> 00:10:46.280
nó là số nguyên A nhỏ nhất sao cho G mũ A bằng 1

00:10:47.380 --> 00:10:52.838
cơ bản nó là số mũ nhỏ nhất của G kết quả là 1

00:10:52.838 --> 00:10:58.566
Dễ thấy điều này nếu ta nhìn vào các lũy thừa của G

00:10:58.566 --> 00:11:04.024
G, G bình phương, G lập phương và tiếp tục, ...

00:11:04.024 --> 00:11:09.887
cho đến khi ta được 1. Và ta xem số mũ này là bậc của G

00:11:09.887 --> 00:11:15.420
Điều này đơn giản bằng 1 theo định nghĩa

00:11:16.080 --> 00:11:22.000
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

00:11:22.000 --> 00:11:27.631
kết quả là kích thước của tập

00:11:27.631 --> 00:11:33.263
là bậc của G, số này chính là số mũ nhỏ nhất

00:11:33.263 --> 00:11:38.931
mà G lũy thừa cho ra 1 trong Zp.

00:11:38.931 --> 00:11:43.455
hơi khó hiểu một tí

00:11:43.455 --> 00:11:48.100
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

00:11:48.100 --> 00:11:52.986
hãy xem xét bậc của các phần tử

00:11:52.986 --> 00:11:57.752
bậc của 3 là nhiêu? Ta đang tìm kích thước của nhóm

00:11:57.752 --> 00:12:02.759
được sinh ra bởi 3 theo modulo 7. ta nói rằng 3 sinh ra Z7 *

00:12:02.759 --> 00:12:07.705
nó sinh ra mọi phần tử của Z7*. có 6 phần tử cả thẩy.

00:12:07.705 --> 00:12:12.758
do đó ta nói 3 có bậc là 6. tương tự,

00:12:12.758 --> 00:12:17.421
bậc của 2 modulo 7 là nhiêu? ta đã thấy đán án.

00:12:17.421 --> 00:12:22.084
Tôi hỏi bạn, bậc của hai,

00:12:22.084 --> 00:12:28.549
là bao nhiêu? Câu trả lời là 3, đơn giản vì nếu ta nhìn vào

00:12:28.549 --> 00:12:33.618
tập các lũy thừa của 2, ta có 1, 2, 2 bình phương (2 mũ 3 = 1)

00:12:33.618 --> 00:12:39.077
đây là toàn bộ lũy thừa của 2 (modulo 7)

00:12:39.077 --> 00:12:44.211
có 3 phần tử, vậy bậc của 2 (modulo 7) là 3

00:12:44.211 --> 00:12:49.215
tôi sẽ hỏi một câu khác

00:12:49.215 --> 00:12:54.499
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

00:12:54.499 --> 00:12:58.633
chỉ có một số, chính là số 1

00:12:58.633 --> 00:13:02.608
tôi sẽ luôn được 1 với mọi lũy thừa.

00:13:02.608 --> 00:13:07.060
do đó bậc của 1 (modulo 7) là 1

00:13:07.060 --> 00:13:12.518
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)

00:13:12.518 --> 00:13:17.137
thật ra

00:13:17.137 --> 00:13:22.309
Đị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)

00:13:22.309 --> 00:13:27.112
thì nó luôn được chia hết bởi p-1. Trong hai ví dụ, ta thấy

00:13:27.297 --> 00:13:32.100
6 được chia hết bơi 7 - 1, 6 chia hết cho 6, tương tư

00:13:32.100 --> 00:13:37.026
3 cũng chia hết bởi 7 - 1, tổng quát, bậc này

00:13:37.026 --> 00:13:41.333
sẽ luôn là một thừa số của p - 1.

00:13:41.333 --> 00:13:45.177
rất khó để có thể suy ra được định lý Fermat trược tiếp từ

00:13:45.177 --> 00:13:49.179
định lý Lagrange.

00:13:49.179 --> 00:13:53.340
Định lý Fermet theo một cách hiểu khác được suy ra từ định lý Lagrange

00:13:54.580 --> 00:13:59.375
Lagrange, tìm ra nó vào thế kỉ 19

00:13:59.375 --> 00:14:04.053
ta đã có một hình trình xuyên thời gian từ thời Hi Lạp cổ đại đến

00:14:04.053 --> 00:14:09.376
cuối thế kỉ 19. Có nhiều hệ mã hóa

00:14:09.376 --> 00:14:14.024
sử dụng nhiều kiến thức toán học của thế kỉ 19.

00:14:14.024 --> 00:14:18.416
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ố,

00:14:18.416 --> 00:14:23.471
cấu trúc của ZN*. Ở đây ta sẽ thấy định lý của Euler

00:14:23.471 --> 00:14:28.044
là một định lý tổng quát so với định lý Fermat.

00:14:28.044 --> 00:14:32.978
Euler định nghĩa hàm sau. cho số nguyên N, phi

00:14:32.978 --> 00:14:37.190
của N là hàm số, trả về kích thức tập ZN*

00:14:37.190 --> 00:14:42.686
gọi là hàm Phi Euler ;)

00:14:42.686 --> 00:14:48.521
ví dụ, ta có Z12* chứa bốn phần tử, 1, 5, 7, 11

00:14:48.521 --> 00:14:53.881
do đó phi của 12 là 4

00:14:53.881 --> 00:14:59.310
một câu đố, phi của p là nhiêu?

00:14:59.310 --> 00:15:06.266
cơ bản thì đây là kích thước của Zp*.

00:15:06.266 --> 00:15:12.335
chứa tất cả phần của của ZP trừ số 0

00:15:12.335 --> 00:15:18.533
do đó phi của p là p - 1. có một trường hợp đặc biệt

00:15:18.533 --> 00:15:23.282
tôi sẽ chỉ ra ở đây, ta sẽ dùng lại cho hệ mã RSA

00:15:23.282 --> 00:15:28.277
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

00:15:28.277 --> 00:15:33.045
để 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

00:15:33.045 --> 00:15:37.838
loại bỏ tất cả những phần tử không nguyên tố cùng nhau với N.

00:15:37.838 --> 00:15:42.632
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

00:15:42.632 --> 00:15:47.079
có bao nhiêu phần tử từ 0 tới n - 1 được chia hết

00:15:47.079 --> 00:15:51.757
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

00:15:51.757 --> 00:15:55.973
bởi q, có p phần tử như vậy.

00:15:55.973 --> 00:16:00.593
ta trừ p để lại ra những phần tử chia hết bởi q. trừ q để loại bỏ

00:16:00.593 --> 00:16:05.776
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

00:16:05.776 --> 00:16:12.020
vì nó được chia hết bởi cả p và q, do đó, ta cộng thêm một

00:16:12.020 --> 00:16:18.264
kết quả là phi(N) = N - P - Q + 1

00:16:18.264 --> 00:16:24.599
cách viết khác là (p-1)x(q-1)

00:16:24.599 --> 00:16:30.275
ta sẽ quay lại vấn đề này khi nói về hệ mã RSA.

00:16:30.275 --> 00:16:35.690
ở đây ta chỉ mới định nghĩa hàm phi Euler.

00:16:35.690 --> 00:16:41.104
Euler đã có một chứng minh tuyệt vời rằng

00:16:41.104 --> 00:16:46.060
với mọi phần tử X nào của ZN* . thì X mũ phi(N)

00:16:46.060 --> 00:16:50.678
bằng 1 trong ZN. Đây là một tổng quát hóa của định lý Fermat

00:16:50.678 --> 00:16:55.239
định lý Fermat chỉ áp dụng cho số nguyên tố

00:16:55.239 --> 00:16:59.913
với số nguyên tố p, ta có phi(p) = p - 1. ta chỉ cần viết p - 1 ở đây

00:16:59.913 --> 00:17:04.494
và ta lại có được định lý Fermat.

00:17:04.494 --> 00:17:08.892
vẻ đẹp của định lý Euler là nó áp dụng cho cả hợp số

00:17:08.892 --> 00:17:16.462
không chỉ riêng số nguyên tố. Hãy nhìn vào ví dụ, 5 mũ phi(12)

00:17:16.462 --> 00:17:21.743
5 là một phần tử của Z12*. Nếu ta lấy 5 mũ 12, ta sẽ được

00:17:21.743 --> 00:17:27.155
ta sẽ được 1, ta biết rằng, phi(12) = 4 do đó

00:17:27.155 --> 00:17:32.037
5 mũ 4 là 625,

00:17:32.037 --> 00:17:36.227
bằng 1 modulo 12

00:17:36.227 --> 00:17:40.468
tuy đây chỉ là một ví dụ, nhưng không khó để có thể chứng minh

00:17:40.468 --> 00:17:44.555
định lý Euler. sự thật là

00:17:44.555 --> 00:17:48.900
định lý Euler lại là một trường hợp đặc biệt của định lý Lagrange

00:17:49.880 --> 00:17:53.888
okay, ta đã biết đây là một trường hợp tổng quát của định lý Fermat và

00:17:53.888 --> 00:17:58.230
thực tế thì, định lý Euler là cơ sở cho hệ mã RSA

00:17:58.230 --> 00:18:03.922
Tôi sẽ dừng ở đây, ta sẽ tiếp tục với những phương trình bậc hai

00:18:03.922 --> 00:18:04.740
ở phần tiếp theo.