1
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

2
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.

3
00:00:08,238 --> 00:00:12,256
Trong phần này chúng ta sẽ tiếp tục tiến đến

4
00:00:12,256 --> 00:00:15,866
thế kỉ 17 và 18 để nói về

5
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

6
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

7
00:00:24,257 --> 00:00:28,427
là một giá trị nguyên dương có n bit.

8
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

9
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

10
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.

11
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

12
00:00:46,186 --> 00:00:51,243
rằng X là khả nghịch khi và chỉ khi X

13
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

14
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

15
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.

16
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.

17
00:01:10,388 --> 00:01:16,107
n số bit của số N.

18
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

19
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.

20
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ứ

21
00:01:31,206 --> 00:01:36,260
phần tử X nào thuộc tập ZP*,

22
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.

23
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

24
00:01:46,061 --> 00:01:50,645
3 mũ 4, kết quả là 81

25
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

26
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

27
00:01:59,521 --> 00:02:04,337
mà phải 100 năm sau mới có người chứng minh nó

28
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

29
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.

30
00:02:14,154 --> 00:02:19,441
nhắc lại, p là một số nguyên tố

31
00:02:19,441 --> 00:02:24,664
Ta biết được gì? Ta biết X ^ (p-1) = 1.

32
00:02:24,664 --> 00:02:29,573
ta có thể viết, X nhân X mũ p trừ 2.

33
00:02:29,573 --> 00:02:34,087
kết quả vẫn là một.

34
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

35
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ố

36
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

37
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ố

38
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.

39
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ố

40
00:03:02,528 --> 00:03:07,017
thứ hai, thuật toán này ít hiệu quả hơn

41
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

42
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

43
00:03:15,345 --> 00:03:19,792
hay cách khác là log của P lập phương

44
00:03:19,792 --> 00:03:24,266
thuật toán của Euclid thì lại có thể tính

45
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

46
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.

47
00:03:36,512 --> 00:03:41,473
Số nguyên tố rất quan trọng

48
00:03:41,473 --> 00:03:47,506
ta sẽ sử dụng nó trong vài tuần tới.

49
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

50
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.

51
00:03:57,226 --> 00:04:02,006
Số ta đang tìm lớn của 2 mũ 1024.

52
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ố

53
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?

54
00:04:12,124 --> 00:04:17,153
Ta sẽ kiểm tra

55
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

56
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ố

57
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

58
00:04:33,003 --> 00:04:37,284
Ta cứ làm lại, làm lại

59
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.

60
00:04:41,782 --> 00:04:46,009
khi đó ta dừng thuật toán và xuất kết quả

61
00:04:46,009 --> 00:04:51,573
Tuy khá là khó để chứng minh

62
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ố.

63
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ỏ.

64
00:05:01,398 --> 00:05:06,191
khoảng cở 2 mũ -60 cho một số dài 1024 bit

65
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ố

66
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ị ;)

67
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ố

68
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ố.

69
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.

70
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*

71
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.

72
00:05:40,230 --> 00:05:45,233
tập các số nguyên tố ở đây,

73
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ử,

74
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

75
00:05:55,653 --> 00:06:00,626
Tuy nhiên vì ta chọn một cách ngẫu nhiên

76
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

77
00:06:05,349 --> 00:06:10,260
xác suất mà ta chọn phải FP là rất nhỏ

78
00:06:10,260 --> 00:06:15,082
nhỏ tới mức có thể bỏ qua được (negligible)

79
00:06:15,082 --> 00:06:20,591
có thể chứng được mình tập FB là cực nhỏ.

80
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

81
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ố

82
00:06:28,960 --> 00:06:32,654
ta có những thuật toán tốt hơn nhiều

83
00:06:32,654 --> 00:06:36,349
thậm chí ta có những thuật toán rất hiệu quả

84
00:06:36,349 --> 00:06:40,498
để kiểm tra một số có phải là số nguyên tố

85
00:06:40,498 --> 00:06:44,597
một cách chắc chắn

86
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ố

87
00:06:48,595 --> 00:06:53,076
Điểm đáng chú ý cuối cùng ở đây

88
00:06:53,076 --> 00:06:57,468
là, cần bao nhiều vòng lặp để

89
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

90
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

91
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.

92
00:07:09,833 --> 00:07:14,771
Giờ thì ta đã hiểu được định lý Fermat

93
00:07:14,771 --> 00:07:19,314
tiếp theo ta sẽ nói về cấu trúc của ZP*

94
00:07:19,314 --> 00:07:23,915
Ta tiến thêm 100 năm nữa

95
00:07:23,915 --> 00:07:28,576
vào thế kỉ 18, để gặp gỡ Euler.

96
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).

97
00:07:33,118 --> 00:07:38,014
Nhóm vòng, nghĩa là sao?

98
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

99
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

100
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

101
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

102
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ì

103
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

104
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

105
00:08:11,825 --> 00:08:16,590
vì vậy chỉ cần dừng lại ở mũ p - 2

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

107
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*

108
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*.

109
00:08:31,239 --> 00:08:35,997
G gọi là phần tử sinh. G sinh ra ZP*

110
00:08:35,997 --> 00:08:40,696
Xét một ví dụ, P = 7

111
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,

112
00:08:45,575 --> 00:08:50,130
3 mũ 5. 3 mũ 6 = 1 modulo 7, theo định lý Fermat.

113
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

114
00:08:54,917 --> 00:08:59,644
Tôi đã tính những lũy thừa này.

115
00:08:59,644 --> 00:09:04,431
Bạn thấy đấy, tất cả phần từ trong Z7* đều ở đây

116
00:09:04,431 --> 00:09:09,313
ta có 2, 3, 4, 5, 6.

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

118
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

119
00:09:19,886 --> 00:09:24,914
nó không thể sinh ra toàn bộ nhóm. 2 mũ 0 được 1

120
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.

121
00:09:29,650 --> 00:09:34,455
Do đó ta đã lặp lại

122
00:09:34,455 --> 00:09:39,766
2 mũ 4 sẽ là 2, 2 mũ 5 sẽ là 4, và cứ thế...

123
00:09:39,766 --> 00:09:44,697
Nếu nhìn vào đây, thì ta chỉ thấy 1, 2, 4

124
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 *

125
00:09:49,981 --> 00:09:55,831
Đôi khi ta được cho một phần tử G của ZP*

126
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

127
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

128
00:10:06,947 --> 00:10:12,798
không quan trọng về kĩ thuật. mấu chốt ở đây là

129
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.

130
00:10:18,397 --> 00:10:23,570
thực ra kí hiệu này không được thông dụng,

131
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à

132
00:10:30,010 --> 00:10:35,663
kích thước của nhóm được sinh ra bởi G.

133
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

134
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

135
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

136
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

137
00:10:58,566 --> 00:11:04,024
G, G bình phương, G lập phương và tiếp tục, ...

138
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

139
00:11:09,887 --> 00:11:15,420
Điều này đơn giản bằng 1 theo định nghĩa

140
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

141
00:11:22,000 --> 00:11:27,631
kết quả là kích thước của tập

142
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

143
00:11:33,263 --> 00:11:38,931
mà G lũy thừa cho ra 1 trong Zp.

144
00:11:38,931 --> 00:11:43,455
hơi khó hiểu một tí

145
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

146
00:11:48,100 --> 00:11:52,986
hãy xem xét bậc của các phần tử

147
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

148
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 *

149
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.

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

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

152
00:12:17,421 --> 00:12:22,084
Tôi hỏi bạn, bậc của hai,

153
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

154
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)

155
00:12:33,618 --> 00:12:39,077
đây là toàn bộ lũy thừa của 2 (modulo 7)

156
00:12:39,077 --> 00:12:44,211
có 3 phần tử, vậy bậc của 2 (modulo 7) là 3

157
00:12:44,211 --> 00:12:49,215
tôi sẽ hỏi một câu khác

158
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

159
00:12:54,499 --> 00:12:58,633
chỉ có một số, chính là số 1

160
00:12:58,633 --> 00:13:02,608
tôi sẽ luôn được 1 với mọi lũy thừa.

161
00:13:02,608 --> 00:13:07,060
do đó bậc của 1 (modulo 7) là 1

162
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)

163
00:13:12,518 --> 00:13:17,137
thật ra

164
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)

165
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

166
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ư

167
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

168
00:13:37,026 --> 00:13:41,333
sẽ luôn là một thừa số của p - 1.

169
00:13:41,333 --> 00:13:45,177
rất khó để có thể suy ra được định lý Fermat trược tiếp từ

170
00:13:45,177 --> 00:13:49,179
định lý Lagrange.

171
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

172
00:13:54,580 --> 00:13:59,375
Lagrange, tìm ra nó vào thế kỉ 19

173
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

174
00:14:04,053 --> 00:14:09,376
cuối thế kỉ 19. Có nhiều hệ mã hóa

175
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.

176
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ố,

177
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

178
00:14:23,471 --> 00:14:28,044
là một định lý tổng quát so với định lý Fermat.

179
00:14:28,044 --> 00:14:32,978
Euler định nghĩa hàm sau. cho số nguyên N, phi

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

181
00:14:37,190 --> 00:14:42,686
gọi là hàm Phi Euler ;)

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

183
00:14:48,521 --> 00:14:53,881
do đó phi của 12 là 4

184
00:14:53,881 --> 00:14:59,310
một câu đố, phi của p là nhiêu?

185
00:14:59,310 --> 00:15:06,266
cơ bản thì đây là kích thước của Zp*.

186
00:15:06,266 --> 00:15:12,335
chứa tất cả phần của của ZP trừ số 0

187
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

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

189
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

190
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

191
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.

192
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

193
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

194
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

195
00:15:51,757 --> 00:15:55,973
bởi q, có p phần tử như vậy.

196
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ỏ

197
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

198
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

199
00:16:12,020 --> 00:16:18,264
kết quả là phi(N) = N - P - Q + 1

200
00:16:18,264 --> 00:16:24,599
cách viết khác là (p-1)x(q-1)

201
00:16:24,599 --> 00:16:30,275
ta sẽ quay lại vấn đề này khi nói về hệ mã RSA.

202
00:16:30,275 --> 00:16:35,690
ở đây ta chỉ mới định nghĩa hàm phi Euler.

203
00:16:35,690 --> 00:16:41,104
Euler đã có một chứng minh tuyệt vời rằng

204
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)

205
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

206
00:16:50,678 --> 00:16:55,239
định lý Fermat chỉ áp dụng cho số nguyên tố

207
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

208
00:16:59,913 --> 00:17:04,494
và ta lại có được định lý Fermat.

209
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ố

210
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)

211
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

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

213
00:17:27,155 --> 00:17:32,037
5 mũ 4 là 625,

214
00:17:32,037 --> 00:17:36,227
bằng 1 modulo 12

215
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

216
00:17:40,468 --> 00:17:44,555
định lý Euler. sự thật là

217
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

218
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à

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

220
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

221
00:18:03,922 --> 00:18:04,740
ở phần tiếp theo.