Fermat và Euler (18 min)

Nói về những định lý có vai trò quan trọng trong số học

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.