[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:04.22,Default,,0000,0000,0000,,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
Dialogue: 0,0:00:04.22,0:00:08.24,Default,,0000,0000,0000,,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.
Dialogue: 0,0:00:08.24,0:00:12.26,Default,,0000,0000,0000,,Trong phần này chúng ta sẽ tiếp tục tiến đến
Dialogue: 0,0:00:12.26,0:00:15.87,Default,,0000,0000,0000,,thế kỉ 17 và 18 để nói về
Dialogue: 0,0:00:15.87,0:00:19.99,Default,,0000,0000,0000,,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
Dialogue: 0,0:00:19.99,0:00:24.26,Default,,0000,0000,0000,,những gì đã trình bày ở phần trước. Như mọi khi thì tôi kí hiệu N
Dialogue: 0,0:00:24.26,0:00:28.43,Default,,0000,0000,0000,,là một giá trị nguyên dương có n bit.
Dialogue: 0,0:00:28.43,0:00:32.44,Default,,0000,0000,0000,,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
Dialogue: 0,0:00:32.44,0:00:36.76,Default,,0000,0000,0000,,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
Dialogue: 0,0:00:36.76,0:00:41.37,Default,,0000,0000,0000,,tới N-1 và ta có thể sử dụng phép cộng và nhân modulo N.
Dialogue: 0,0:00:41.37,0:00:46.19,Default,,0000,0000,0000,,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
Dialogue: 0,0:00:46.19,0:00:51.24,Default,,0000,0000,0000,,rằng X là khả nghịch khi và chỉ khi X
Dialogue: 0,0:00:51.24,0:00:55.88,Default,,0000,0000,0000,,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
Dialogue: 0,0:00:55.88,0:01:00.64,Default,,0000,0000,0000,,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
Dialogue: 0,0:01:00.64,0:01:05.57,Default,,0000,0000,0000,,thuật toán Euclidean mở rộng để tìm nghịch đảo của một phần tử trong ZN.
Dialogue: 0,0:01:05.57,0:01:10.39,Default,,0000,0000,0000,,thời gian chạy của thuật toán này chỉ xấp xỉ bình phương của n.
Dialogue: 0,0:01:10.39,0:01:16.11,Default,,0000,0000,0000,,n số bit của số N.
Dialogue: 0,0:01:16.11,0:01:21.04,Default,,0000,0000,0000,,Bây giờ chúng ta sẽ đi từ thời Hi Lạp tới thế kỷ 17
Dialogue: 0,0:01:21.04,0:01:26.28,Default,,0000,0000,0000,,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.
Dialogue: 0,0:01:26.28,0:01:31.21,Default,,0000,0000,0000,,Giả sử tôi đưa cho các bạn số nguyên tố p. Lúc đó bất cứ
Dialogue: 0,0:01:31.21,0:01:36.26,Default,,0000,0000,0000,,phần tử X nào thuộc tập ZP*,
Dialogue: 0,0:01:36.26,0:01:41.13,Default,,0000,0000,0000,,nếu tôi tính X^(p-1) thì tôi sẽ được một phần tử thuộc ZP.
Dialogue: 0,0:01:41.13,0:01:46.06,Default,,0000,0000,0000,,Một ví dụ như sau: P=5, nếu tôi lấy 3 mũ P - 1
Dialogue: 0,0:01:46.06,0:01:50.64,Default,,0000,0000,0000,,3 mũ 4, kết quả là 81
Dialogue: 0,0:01:50.64,0:01:55.29,Default,,0000,0000,0000,,và cũng bằng 1 theo modulo 5. phù hợp với định lý của Fermat
Dialogue: 0,0:01:55.29,0:01:59.52,Default,,0000,0000,0000,,Một điều rất lý thú là Fermat không chứng minh định lý này
Dialogue: 0,0:01:59.52,0:02:04.34,Default,,0000,0000,0000,,mà phải 100 năm sau mới có người chứng minh nó
Dialogue: 0,0:02:04.34,0:02:09.12,Default,,0000,0000,0000,,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
Dialogue: 0,0:02:09.12,0:02:14.15,Default,,0000,0000,0000,,Bây giờ ta sẽ xem thử một ứng dụng của định lý Fermat.
Dialogue: 0,0:02:14.15,0:02:19.44,Default,,0000,0000,0000,,nhắc lại, p là một số nguyên tố
Dialogue: 0,0:02:19.44,0:02:24.66,Default,,0000,0000,0000,,Ta biết được gì? Ta biết X ^ (p-1) = 1.
Dialogue: 0,0:02:24.66,0:02:29.57,Default,,0000,0000,0000,,ta có thể viết, X nhân X mũ p trừ 2.
Dialogue: 0,0:02:29.57,0:02:34.09,Default,,0000,0000,0000,,kết quả vẫn là một.
Dialogue: 0,0:02:34.09,0:02:39.31,Default,,0000,0000,0000,,điều này chứng tỏ, X mũ p trừ 2 là nghịch đảo của X
Dialogue: 0,0:02:39.31,0:02:44.04,Default,,0000,0000,0000,,đâ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ố
Dialogue: 0,0:02:44.04,0:02:48.84,Default,,0000,0000,0000,,đơn giản chỉ cần lấy X mũ p trừ 2, ta sẽ được nghịch đảo của X
Dialogue: 0,0:02:48.84,0:02:53.51,Default,,0000,0000,0000,,đây là một cách tốt để tìm nghịch đảo với modulo một số nguyên tố
Dialogue: 0,0:02:53.51,0:02:58.30,Default,,0000,0000,0000,,nhưng nó có hai nhược điểm so với thuật toán của Euclid.
Dialogue: 0,0:02:58.30,0:03:02.53,Default,,0000,0000,0000,,Đầ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ố
Dialogue: 0,0:03:02.53,0:03:07.02,Default,,0000,0000,0000,,thứ hai, thuật toán này ít hiệu quả hơn
Dialogue: 0,0:03:07.02,0:03:10.91,Default,,0000,0000,0000,,khi ta nói về thuật toán tính lũy thừa theo modulo ở phần cuối của video
Dialogue: 0,0:03:10.91,0:03:15.34,Default,,0000,0000,0000,,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
Dialogue: 0,0:03:15.34,0:03:19.79,Default,,0000,0000,0000,,hay cách khác là log của P lập phương
Dialogue: 0,0:03:19.79,0:03:24.27,Default,,0000,0000,0000,,thuật toán của Euclid thì lại có thể tính
Dialogue: 0,0:03:24.27,0:03:30.34,Default,,0000,0000,0000,,nghịch đảo trong thời gian tỉ lệ với bình phương chiều dài của p
Dialogue: 0,0:03:30.34,0:03:36.51,Default,,0000,0000,0000,,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.
Dialogue: 0,0:03:36.51,0:03:41.47,Default,,0000,0000,0000,,Số nguyên tố rất quan trọng
Dialogue: 0,0:03:41.47,0:03:47.51,Default,,0000,0000,0000,,ta sẽ sử dụng nó trong vài tuần tới.
Dialogue: 0,0:03:47.51,0:03:52.16,Default,,0000,0000,0000,,tôi sẽ trình bày một ứng dụng của định lý Fermat
Dialogue: 0,0:03:52.16,0:03:57.23,Default,,0000,0000,0000,,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.
Dialogue: 0,0:03:57.23,0:04:02.01,Default,,0000,0000,0000,,Số ta đang tìm lớn của 2 mũ 1024.
Dialogue: 0,0:04:02.01,0:04:06.72,Default,,0000,0000,0000,,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ố
Dialogue: 0,0:04:06.72,0:04:11.94,Default,,0000,0000,0000,,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?
Dialogue: 0,0:04:12.12,0:04:17.15,Default,,0000,0000,0000,,Ta sẽ kiểm tra
Dialogue: 0,0:04:17.15,0:04:22.37,Default,,0000,0000,0000,,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
Dialogue: 0,0:04:22.37,0:04:27.27,Default,,0000,0000,0000,,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ố
Dialogue: 0,0:04:27.27,0:04:33.00,Default,,0000,0000,0000,,nếu vậy, ta sẽ trở lại bước 1 với một số nguyên tố khác
Dialogue: 0,0:04:33.00,0:04:37.28,Default,,0000,0000,0000,,Ta cứ làm lại, làm lại
Dialogue: 0,0:04:37.28,0:04:41.78,Default,,0000,0000,0000,,cho tới khi nào ta được một số thỏa điều kiện này.
Dialogue: 0,0:04:41.78,0:04:46.01,Default,,0000,0000,0000,,khi đó ta dừng thuật toán và xuất kết quả
Dialogue: 0,0:04:46.01,0:04:51.57,Default,,0000,0000,0000,,Tuy khá là khó để chứng minh
Dialogue: 0,0:04:51.57,0:04:56.30,Default,,0000,0000,0000,,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ố.
Dialogue: 0,0:04:56.30,0:05:01.40,Default,,0000,0000,0000,,xác suất mà p không là số nguyên tố là cực kì nhỏ.
Dialogue: 0,0:05:01.40,0:05:06.19,Default,,0000,0000,0000,,khoảng cở 2 mũ -60 cho một số dài 1024 bit
Dialogue: 0,0:05:06.19,0:05:10.74,Default,,0000,0000,0000,,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ố
Dialogue: 0,0:05:10.74,0:05:15.72,Default,,0000,0000,0000,,giảm xuống 0 rất là nhanh. Đây là một thuật toán thú vị ;)
Dialogue: 0,0:05:15.72,0:05:20.46,Default,,0000,0000,0000,,Ta nhận ra là không thể đảm bảo kết quả là nguyên tố
Dialogue: 0,0:05:20.46,0:05:25.02,Default,,0000,0000,0000,,những gì ta biết là nó rất, rất có thể là nguyên tố.
Dialogue: 0,0:05:25.02,0:05:29.59,Default,,0000,0000,0000,,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.
Dialogue: 0,0:05:29.59,0:05:34.30,Default,,0000,0000,0000,,Xác suất không may nắm nhỏ đến mức *có thể bỏ qua*
Dialogue: 0,0:05:34.30,0:05:40.23,Default,,0000,0000,0000,,nếu bạn nhìn vào tập tất cả các số có 1024 bit.
Dialogue: 0,0:05:40.23,0:05:45.23,Default,,0000,0000,0000,,tập các số nguyên tố ở đây,
Dialogue: 0,0:05:45.23,0:05:50.80,Default,,0000,0000,0000,,và sau đó một tập nhỏ các hợp số mà qua được phép thử,
Dialogue: 0,0:05:50.80,0:05:55.65,Default,,0000,0000,0000,,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
Dialogue: 0,0:05:55.65,0:06:00.63,Default,,0000,0000,0000,,Tuy nhiên vì ta chọn một cách ngẫu nhiên
Dialogue: 0,0:06:00.63,0:06:05.35,Default,,0000,0000,0000,,một cái ở đây, ở đâu, ở đâu, và cứ như thế, ta chọn những số nguyên ngẫu nhiên
Dialogue: 0,0:06:05.35,0:06:10.26,Default,,0000,0000,0000,,xác suất mà ta chọn phải FP là rất nhỏ
Dialogue: 0,0:06:10.26,0:06:15.08,Default,,0000,0000,0000,,nhỏ tới mức có thể bỏ qua được (negligible)
Dialogue: 0,0:06:15.08,0:06:20.59,Default,,0000,0000,0000,,có thể chứng được mình tập FB là cực nhỏ.
Dialogue: 0,0:06:20.59,0:06:25.27,Default,,0000,0000,0000,,chọn ngẫu nhiên một số thì rất khó mà trúng phải FP
Dialogue: 0,0:06:25.27,0:06:28.96,Default,,0000,0000,0000,,Thật ra đây không phải là thuật toán tốt nhất để sinh ra số nguyên tố
Dialogue: 0,0:06:28.96,0:06:32.65,Default,,0000,0000,0000,,ta có những thuật toán tốt hơn nhiều
Dialogue: 0,0:06:32.65,0:06:36.35,Default,,0000,0000,0000,,thậm chí ta có những thuật toán rất hiệu quả
Dialogue: 0,0:06:36.35,0:06:40.50,Default,,0000,0000,0000,,để kiểm tra một số có phải là số nguyên tố
Dialogue: 0,0:06:40.50,0:06:44.60,Default,,0000,0000,0000,,một cách chắc chắn
Dialogue: 0,0:06:44.60,0:06:48.60,Default,,0000,0000,0000,,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ố
Dialogue: 0,0:06:48.60,0:06:53.08,Default,,0000,0000,0000,,Điểm đáng chú ý cuối cùng ở đây
Dialogue: 0,0:06:53.08,0:06:57.47,Default,,0000,0000,0000,,là, cần bao nhiều vòng lặp để
Dialogue: 0,0:06:57.47,0:07:01.54,Default,,0000,0000,0000,,tìm ra một số nguyên tố. Một kết quả cổ điển
Dialogue: 0,0:07:01.54,0:07:05.82,Default,,0000,0000,0000,,được gọi là định lý số nguyên tố, nói ràng, sau vài trăm vòng lặp
Dialogue: 0,0:07:05.82,0:07:09.83,Default,,0000,0000,0000,,ta sẽ tìm được một số nguyên tố với xác suất cao.
Dialogue: 0,0:07:09.83,0:07:14.77,Default,,0000,0000,0000,,Giờ thì ta đã hiểu được định lý Fermat
Dialogue: 0,0:07:14.77,0:07:19.31,Default,,0000,0000,0000,,tiếp theo ta sẽ nói về cấu trúc của ZP*
Dialogue: 0,0:07:19.31,0:07:23.92,Default,,0000,0000,0000,,Ta tiến thêm 100 năm nữa
Dialogue: 0,0:07:23.92,0:07:28.58,Default,,0000,0000,0000,,vào thế kỉ 18, để gặp gỡ Euler.
Dialogue: 0,0:07:28.58,0:07:33.12,Default,,0000,0000,0000,,Đ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).
Dialogue: 0,0:07:33.12,0:07:38.01,Default,,0000,0000,0000,,Nhóm vòng, nghĩa là sao?
Dialogue: 0,0:07:38.01,0:07:42.73,Default,,0000,0000,0000,,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
Dialogue: 0,0:07:42.73,0:07:47.68,Default,,0000,0000,0000,,và lấy mũ, G bình phương, G lập phương, v.v. Cứ tiếp tục như vậy
Dialogue: 0,0:07:47.68,0:07:52.59,Default,,0000,0000,0000,,cho đến khi tới G mũ p trừ 2. Lưu ý là không ra khỏi G mũ p trừ 2
Dialogue: 0,0:07:52.59,0:07:57.30,Default,,0000,0000,0000,,vì ta biết, theo định lý Fermat rằng, G mũ p - 1 bằng 1
Dialogue: 0,0:07:57.30,0:08:02.18,Default,,0000,0000,0000,,vì vậy ta sẽ lập lặp một. Nếu ta tới G mũ p - 1. thì
Dialogue: 0,0:08:02.18,0:08:06.82,Default,,0000,0000,0000,,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
Dialogue: 0,0:08:06.82,0:08:11.82,Default,,0000,0000,0000,,Ta sẽ được sự lại nếu tiếp tục với mũ cao hơn
Dialogue: 0,0:08:11.82,0:08:16.59,Default,,0000,0000,0000,,vì vậy chỉ cần dừng lại ở mũ p - 2
Dialogue: 0,0:08:16.59,0:08:21.41,Default,,0000,0000,0000,,Euler đã chỉ ra rằng có một phần tử G như vậy,
Dialogue: 0,0:08:21.41,0:08:26.30,Default,,0000,0000,0000,,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*
Dialogue: 0,0:08:26.30,0:08:31.24,Default,,0000,0000,0000,,Các lũy thừa của G cho ta tất cả phần tử thuộc ZP*.
Dialogue: 0,0:08:31.24,0:08:35.100,Default,,0000,0000,0000,,G gọi là phần tử sinh. G sinh ra ZP*
Dialogue: 0,0:08:35.100,0:08:40.70,Default,,0000,0000,0000,,Xét một ví dụ, P = 7
Dialogue: 0,0:08:40.70,0:08:45.58,Default,,0000,0000,0000,,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,
Dialogue: 0,0:08:45.58,0:08:50.13,Default,,0000,0000,0000,,3 mũ 5. 3 mũ 6 = 1 modulo 7, theo định lý Fermat.
Dialogue: 0,0:08:50.13,0:08:54.92,Default,,0000,0000,0000,,không cần xem xét 3 mũ 6, vì ta biết nó sẽ là 1
Dialogue: 0,0:08:54.92,0:08:59.64,Default,,0000,0000,0000,,Tôi đã tính những lũy thừa này.
Dialogue: 0,0:08:59.64,0:09:04.43,Default,,0000,0000,0000,,Bạn thấy đấy, tất cả phần từ trong Z7* đều ở đây
Dialogue: 0,0:09:04.43,0:09:09.31,Default,,0000,0000,0000,,ta có 2, 3, 4, 5, 6.
Dialogue: 0,0:09:09.31,0:09:14.60,Default,,0000,0000,0000,,ta sẽ nói rằng 3 là phần tử sinh của Z7 *.
Dialogue: 0,0:09:14.60,0:09:19.89,Default,,0000,0000,0000,,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
Dialogue: 0,0:09:19.89,0:09:24.91,Default,,0000,0000,0000,,nó không thể sinh ra toàn bộ nhóm. 2 mũ 0 được 1
Dialogue: 0,0:09:24.91,0:09:29.65,Default,,0000,0000,0000,,2 mũ 1 được 2, 2 mũ 2 được 4, 3 mỹ 3 được 8, chính là 1 modulo 7.
Dialogue: 0,0:09:29.65,0:09:34.46,Default,,0000,0000,0000,,Do đó ta đã lặp lại
Dialogue: 0,0:09:34.46,0:09:39.77,Default,,0000,0000,0000,,2 mũ 4 sẽ là 2, 2 mũ 5 sẽ là 4, và cứ thế...
Dialogue: 0,0:09:39.77,0:09:44.70,Default,,0000,0000,0000,,Nếu nhìn vào đây, thì ta chỉ thấy 1, 2, 4
Dialogue: 0,0:09:44.70,0:09:49.98,Default,,0000,0000,0000,,ta không có được toàn một nhóm, dó đó 2 không là phần tử sinh của Z7 *
Dialogue: 0,0:09:49.98,0:09:55.83,Default,,0000,0000,0000,,Đôi khi ta được cho một phần tử G của ZP*
Dialogue: 0,0:09:55.83,0:10:01.90,Default,,0000,0000,0000,,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
Dialogue: 0,0:10:01.90,0:10:06.95,Default,,0000,0000,0000,,Tất cả đều là lũy thừa của G. Ta có được một nhóm multiplicative
Dialogue: 0,0:10:06.95,0:10:12.80,Default,,0000,0000,0000,,không quan trọng về kĩ thuật. mấu chốt ở đây là
Dialogue: 0,0:10:12.80,0:10:18.40,Default,,0000,0000,0000,,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.
Dialogue: 0,0:10:18.40,0:10:23.57,Default,,0000,0000,0000,,thực ra kí hiệu này không được thông dụng,
Dialogue: 0,0:10:23.57,0:10:30.01,Default,,0000,0000,0000,,để kí hiệu nhóm sinh ra bởi G. Ta gọi bậc của G trong Zp* là
Dialogue: 0,0:10:30.01,0:10:35.66,Default,,0000,0000,0000,,kích thước của nhóm được sinh ra bởi G.
Dialogue: 0,0:10:35.66,0:10:40.63,Default,,0000,0000,0000,,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
Dialogue: 0,0:10:40.63,0:10:46.28,Default,,0000,0000,0000,,nó là số nguyên A nhỏ nhất sao cho G mũ A bằng 1
Dialogue: 0,0:10:47.38,0:10:52.84,Default,,0000,0000,0000,,cơ bản nó là số mũ nhỏ nhất của G kết quả là 1
Dialogue: 0,0:10:52.84,0:10:58.57,Default,,0000,0000,0000,,Dễ thấy điều này nếu ta nhìn vào các lũy thừa của G
Dialogue: 0,0:10:58.57,0:11:04.02,Default,,0000,0000,0000,,G, G bình phương, G lập phương và tiếp tục, ...
Dialogue: 0,0:11:04.02,0:11:09.89,Default,,0000,0000,0000,,cho đến khi ta được 1. Và ta xem số mũ này là bậc của G
Dialogue: 0,0:11:09.89,0:11:15.42,Default,,0000,0000,0000,,Điều này đơn giản bằng 1 theo định nghĩa
Dialogue: 0,0:11:16.08,0:11:22.00,Default,,0000,0000,0000,,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
Dialogue: 0,0:11:22.00,0:11:27.63,Default,,0000,0000,0000,,kết quả là kích thước của tập
Dialogue: 0,0:11:27.63,0:11:33.26,Default,,0000,0000,0000,,là bậc của G, số này chính là số mũ nhỏ nhất
Dialogue: 0,0:11:33.26,0:11:38.93,Default,,0000,0000,0000,,mà G lũy thừa cho ra 1 trong Zp.
Dialogue: 0,0:11:38.93,0:11:43.46,Default,,0000,0000,0000,,hơi khó hiểu một tí
Dialogue: 0,0:11:43.46,0:11:48.10,Default,,0000,0000,0000,,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
Dialogue: 0,0:11:48.10,0:11:52.99,Default,,0000,0000,0000,,hãy xem xét bậc của các phần tử
Dialogue: 0,0:11:52.99,0:11:57.75,Default,,0000,0000,0000,,bậc của 3 là nhiêu? Ta đang tìm kích thước của nhóm
Dialogue: 0,0:11:57.75,0:12:02.76,Default,,0000,0000,0000,,được sinh ra bởi 3 theo modulo 7. ta nói rằng 3 sinh ra Z7 *
Dialogue: 0,0:12:02.76,0:12:07.70,Default,,0000,0000,0000,,nó sinh ra mọi phần tử của Z7*. có 6 phần tử cả thẩy.
Dialogue: 0,0:12:07.70,0:12:12.76,Default,,0000,0000,0000,,do đó ta nói 3 có bậc là 6. tương tự,
Dialogue: 0,0:12:12.76,0:12:17.42,Default,,0000,0000,0000,,bậc của 2 modulo 7 là nhiêu? ta đã thấy đán án.
Dialogue: 0,0:12:17.42,0:12:22.08,Default,,0000,0000,0000,,Tôi hỏi bạn, bậc của hai,
Dialogue: 0,0:12:22.08,0:12:28.55,Default,,0000,0000,0000,,là bao nhiêu? Câu trả lời là 3, đơn giản vì nếu ta nhìn vào
Dialogue: 0,0:12:28.55,0:12:33.62,Default,,0000,0000,0000,,tập các lũy thừa của 2, ta có 1, 2, 2 bình phương (2 mũ 3 = 1)
Dialogue: 0,0:12:33.62,0:12:39.08,Default,,0000,0000,0000,,đây là toàn bộ lũy thừa của 2 (modulo 7)
Dialogue: 0,0:12:39.08,0:12:44.21,Default,,0000,0000,0000,,có 3 phần tử, vậy bậc của 2 (modulo 7) là 3
Dialogue: 0,0:12:44.21,0:12:49.22,Default,,0000,0000,0000,,tôi sẽ hỏi một câu khác
Dialogue: 0,0:12:49.22,0:12:54.50,Default,,0000,0000,0000,,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
Dialogue: 0,0:12:54.50,0:12:58.63,Default,,0000,0000,0000,,chỉ có một số, chính là số 1
Dialogue: 0,0:12:58.63,0:13:02.61,Default,,0000,0000,0000,,tôi sẽ luôn được 1 với mọi lũy thừa.
Dialogue: 0,0:13:02.61,0:13:07.06,Default,,0000,0000,0000,,do đó bậc của 1 (modulo 7) là 1
Dialogue: 0,0:13:07.06,0:13:12.52,Default,,0000,0000,0000,,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)
Dialogue: 0,0:13:12.52,0:13:17.14,Default,,0000,0000,0000,,thật ra
Dialogue: 0,0:13:17.14,0:13:22.31,Default,,0000,0000,0000,,Đị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)
Dialogue: 0,0:13:22.31,0:13:27.11,Default,,0000,0000,0000,,thì nó luôn được chia hết bởi p-1. Trong hai ví dụ, ta thấy
Dialogue: 0,0:13:27.30,0:13:32.10,Default,,0000,0000,0000,,6 được chia hết bơi 7 - 1, 6 chia hết cho 6, tương tư
Dialogue: 0,0:13:32.10,0:13:37.03,Default,,0000,0000,0000,,3 cũng chia hết bởi 7 - 1, tổng quát, bậc này
Dialogue: 0,0:13:37.03,0:13:41.33,Default,,0000,0000,0000,,sẽ luôn là một thừa số của p - 1.
Dialogue: 0,0:13:41.33,0:13:45.18,Default,,0000,0000,0000,,rất khó để có thể suy ra được định lý Fermat trược tiếp từ
Dialogue: 0,0:13:45.18,0:13:49.18,Default,,0000,0000,0000,,định lý Lagrange.
Dialogue: 0,0:13:49.18,0:13:53.34,Default,,0000,0000,0000,,Định lý Fermet theo một cách hiểu khác được suy ra từ định lý Lagrange
Dialogue: 0,0:13:54.58,0:13:59.38,Default,,0000,0000,0000,,Lagrange, tìm ra nó vào thế kỉ 19
Dialogue: 0,0:13:59.38,0:14:04.05,Default,,0000,0000,0000,,ta đã có một hình trình xuyên thời gian từ thời Hi Lạp cổ đại đến
Dialogue: 0,0:14:04.05,0:14:09.38,Default,,0000,0000,0000,,cuối thế kỉ 19. Có nhiều hệ mã hóa
Dialogue: 0,0:14:09.38,0:14:14.02,Default,,0000,0000,0000,,sử dụng nhiều kiến thức toán học của thế kỉ 19.
Dialogue: 0,0:14:14.02,0:14:18.42,Default,,0000,0000,0000,,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ố,
Dialogue: 0,0:14:18.42,0:14:23.47,Default,,0000,0000,0000,,cấu trúc của ZN*. Ở đây ta sẽ thấy định lý của Euler
Dialogue: 0,0:14:23.47,0:14:28.04,Default,,0000,0000,0000,,là một định lý tổng quát so với định lý Fermat.
Dialogue: 0,0:14:28.04,0:14:32.98,Default,,0000,0000,0000,,Euler định nghĩa hàm sau. cho số nguyên N, phi
Dialogue: 0,0:14:32.98,0:14:37.19,Default,,0000,0000,0000,,của N là hàm số, trả về kích thức tập ZN*
Dialogue: 0,0:14:37.19,0:14:42.69,Default,,0000,0000,0000,,gọi là hàm Phi Euler ;)
Dialogue: 0,0:14:42.69,0:14:48.52,Default,,0000,0000,0000,,ví dụ, ta có Z12* chứa bốn phần tử, 1, 5, 7, 11
Dialogue: 0,0:14:48.52,0:14:53.88,Default,,0000,0000,0000,,do đó phi của 12 là 4
Dialogue: 0,0:14:53.88,0:14:59.31,Default,,0000,0000,0000,,một câu đố, phi của p là nhiêu?
Dialogue: 0,0:14:59.31,0:15:06.27,Default,,0000,0000,0000,,cơ bản thì đây là kích thước của Zp*.
Dialogue: 0,0:15:06.27,0:15:12.34,Default,,0000,0000,0000,,chứa tất cả phần của của ZP trừ số 0
Dialogue: 0,0:15:12.34,0:15:18.53,Default,,0000,0000,0000,,do đó phi của p là p - 1. có một trường hợp đặc biệt
Dialogue: 0,0:15:18.53,0:15:23.28,Default,,0000,0000,0000,,tôi sẽ chỉ ra ở đây, ta sẽ dùng lại cho hệ mã RSA
Dialogue: 0,0:15:23.28,0:15:28.28,Default,,0000,0000,0000,,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
Dialogue: 0,0:15:28.28,0:15:33.04,Default,,0000,0000,0000,,để 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
Dialogue: 0,0:15:33.04,0:15:37.84,Default,,0000,0000,0000,,loại bỏ tất cả những phần tử không nguyên tố cùng nhau với N.
Dialogue: 0,0:15:37.84,0:15:42.63,Default,,0000,0000,0000,,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
Dialogue: 0,0:15:42.63,0:15:47.08,Default,,0000,0000,0000,,có bao nhiêu phần tử từ 0 tới n - 1 được chia hết
Dialogue: 0,0:15:47.08,0:15:51.76,Default,,0000,0000,0000,,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
Dialogue: 0,0:15:51.76,0:15:55.97,Default,,0000,0000,0000,,bởi q, có p phần tử như vậy.
Dialogue: 0,0:15:55.97,0:16:00.59,Default,,0000,0000,0000,,ta trừ p để lại ra những phần tử chia hết bởi q. trừ q để loại bỏ
Dialogue: 0,0:16:00.59,0:16:05.78,Default,,0000,0000,0000,,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
Dialogue: 0,0:16:05.78,0:16:12.02,Default,,0000,0000,0000,,vì nó được chia hết bởi cả p và q, do đó, ta cộng thêm một
Dialogue: 0,0:16:12.02,0:16:18.26,Default,,0000,0000,0000,,kết quả là phi(N) = N - P - Q + 1
Dialogue: 0,0:16:18.26,0:16:24.60,Default,,0000,0000,0000,,cách viết khác là (p-1)x(q-1)
Dialogue: 0,0:16:24.60,0:16:30.28,Default,,0000,0000,0000,,ta sẽ quay lại vấn đề này khi nói về hệ mã RSA.
Dialogue: 0,0:16:30.28,0:16:35.69,Default,,0000,0000,0000,,ở đây ta chỉ mới định nghĩa hàm phi Euler.
Dialogue: 0,0:16:35.69,0:16:41.10,Default,,0000,0000,0000,,Euler đã có một chứng minh tuyệt vời rằng
Dialogue: 0,0:16:41.10,0:16:46.06,Default,,0000,0000,0000,,với mọi phần tử X nào của ZN* . thì X mũ phi(N)
Dialogue: 0,0:16:46.06,0:16:50.68,Default,,0000,0000,0000,,bằng 1 trong ZN. Đây là một tổng quát hóa của định lý Fermat
Dialogue: 0,0:16:50.68,0:16:55.24,Default,,0000,0000,0000,,định lý Fermat chỉ áp dụng cho số nguyên tố
Dialogue: 0,0:16:55.24,0:16:59.91,Default,,0000,0000,0000,,với số nguyên tố p, ta có phi(p) = p - 1. ta chỉ cần viết p - 1 ở đây
Dialogue: 0,0:16:59.91,0:17:04.49,Default,,0000,0000,0000,,và ta lại có được định lý Fermat.
Dialogue: 0,0:17:04.49,0:17:08.89,Default,,0000,0000,0000,,vẻ đẹp của định lý Euler là nó áp dụng cho cả hợp số
Dialogue: 0,0:17:08.89,0:17:16.46,Default,,0000,0000,0000,,không chỉ riêng số nguyên tố. Hãy nhìn vào ví dụ, 5 mũ phi(12)
Dialogue: 0,0:17:16.46,0:17:21.74,Default,,0000,0000,0000,,5 là một phần tử của Z12*. Nếu ta lấy 5 mũ 12, ta sẽ được
Dialogue: 0,0:17:21.74,0:17:27.16,Default,,0000,0000,0000,,ta sẽ được 1, ta biết rằng, phi(12) = 4 do đó
Dialogue: 0,0:17:27.16,0:17:32.04,Default,,0000,0000,0000,,5 mũ 4 là 625,
Dialogue: 0,0:17:32.04,0:17:36.23,Default,,0000,0000,0000,,bằng 1 modulo 12
Dialogue: 0,0:17:36.23,0:17:40.47,Default,,0000,0000,0000,,tuy đây chỉ là một ví dụ, nhưng không khó để có thể chứng minh
Dialogue: 0,0:17:40.47,0:17:44.56,Default,,0000,0000,0000,,định lý Euler. sự thật là
Dialogue: 0,0:17:44.56,0:17:48.90,Default,,0000,0000,0000,,định lý Euler lại là một trường hợp đặc biệt của định lý Lagrange
Dialogue: 0,0:17:49.88,0:17:53.89,Default,,0000,0000,0000,,okay, ta đã biết đây là một trường hợp tổng quát của định lý Fermat và
Dialogue: 0,0:17:53.89,0:17:58.23,Default,,0000,0000,0000,,thực tế thì, định lý Euler là cơ sở cho hệ mã RSA
Dialogue: 0,0:17:58.23,0:18:03.92,Default,,0000,0000,0000,,Tôi sẽ dừng ở đây, ta sẽ tiếp tục với những phương trình bậc hai
Dialogue: 0,0:18:03.92,0:18:04.74,Default,,0000,0000,0000,,ở phần tiếp theo.