Trong bài bác này tao tiếp tục coi mối liên hệ của ấn định lý nhỏ Fermat, ấn định lý Euler,à hàm phi Euler và tầm quan trọng của bọn chúng vô hạ tầng toán học tập ngành mật mã.
Nhà toán học tập người Pháp, Pierre de Fermat đang được cách tân và phát triển nhiều ấn định lý có tên bản thân vô bại sở hữu Định lý nhỏ Fermat về đặc thù của số thành phần.
Phát biểu ấn định lý Fermat nhỏ
Định lý nhỏ của Fermat (hay ấn định lý Fermat nhỏ) xác định rằng nếu như ${\displaystyle p}$ là một số trong những thành phần, thì với số vẹn toàn ${\displaystyle a}$ ngẫu nhiên, ${\displaystyle a^{p}-a}$ tiếp tục phân tách không còn mang lại ${\displaystyle p}$. phẳng phiu kí hiệu đồng dư tao có: $${\displaystyle a^{p}\equiv a{\pmod {p}}\,\!}$$
Ví dụ: với ${\displaystyle a=3,\;p=5\implies 3^{5}-3=240\equiv 0{\pmod {5}}}$.
Một cơ hội tuyên bố không giống của ấn định lý như sau: nếu như ${\displaystyle p}$ là số thành phần và ${\displaystyle a}$ là số vẹn toàn ko phân tách không còn mang lại ${\displaystyle p}$, thì ${\displaystyle a^{p-1}-1}$ tiếp tục phân tách không còn mang lại ${\displaystyle p}$. Nghĩa là: $${\displaystyle a^{p-1}\equiv 1{\pmod {p}}\,!}$$
Ví dụ: với ${\displaystyle a=4,p=5\implies 4^{5-1}-1=255\equiv 0{\pmod {5}}}$
Cũng sở hữu một cơ hội tuyên bố không giống là: Nếu ${\displaystyle p}$ là một số trong những thành phần và ${\displaystyle a}$ là số vẹn toàn ko phân tách không còn mang lại ${\displaystyle p}$, thì ${\displaystyle a^{p-1}-1}$ phân tách không còn mang lại ${\displaystyle p}$.
Định lý Fermat nhỏ là hạ tầng nhằm đánh giá tính thành phần theo đuổi phần trăm vô đánh giá Fermat và là 1 trong trong mỗi sản phẩm nền tảng của lý thuyết số.
Kiểm tra Fermat
Kiểm tra Fermat là 1 trong thuật toán phần trăm đánh giá một số trong những ngẫu nhiên là ăn ý số Hay những số thành phần.
Khái niệm
Định lý nhỏ Fermat tuyên bố rằng nếu như p là số thành phần và ${\displaystyle 1\leq a Nếu tao ham muốn đánh giá số n sở hữu là thành phần ko, tao lấy tình cờ những số a’ và đánh giá coi đẳng thức bên trên sở hữu đúng không nhỉ. Nếu nó ko chính với 1 độ quý hiếm a này bại thì n là ăn ý số. Nếu đẳng thức chính với khá nhiều độ quý hiếm của a, tao nói theo cách khác rằng n là số thành phần với phần trăm này bại, Hay những một số trong những fake thành phần (pseudoprime). Có thể phép tắc demo tiếp tục mang lại tao một sản phẩm sai. Thuật toán Fermat đánh giá số n sở hữu cần số thành phần hoặc kjong rất có thể viết lách như sau: Khi sử dụng thuật toán tính thời gian nhanh luỹ quá theo đuổi mođun, thời hạn thực hành của thuật toán là O(k × log3n), ở bại k là số đợt đánh giá với từng số a tình cờ, và n là độ quý hiếm tao ham muốn đánh giá. Fermat tuyên bố ấn định lý tuy nhiên ko minh chứng. Đã có tương đối nhiều minh chứng của ấn định lý. Tuy nhiên ấn định lý thông thường được minh chứng bằng phương pháp sử dụng hệ ngược của ấn định lý Euler. Bài chi tiết: https://en.wikipedia.org/wiki/Proofs_of_Fermat%27s_little_theorem Xét ${\displaystyle 2^{7-1} {\pmod {7}}}$, tao thấy 7 là số thành phần và ${\displaystyle GCD(2, 7)=1}$, theo đuổi ấn định lý nhỏ Fermat thì ${\displaystyle 2^{7-1} \equiv 1 {\pmod {7}}}$ . Kiểm tra lại tao sở hữu ${\displaystyle 2^{7-1} \equiv 2^{6} \equiv 64 \equiv 1 {\pmod {7}}}$ Tính nhanh Trong lý thuyết số, hàm số Euler của một số trong những vẹn toàn dương n được khái niệm là số những số vẹn toàn dương nhỏ rộng lớn hoặc bởi vì n thành phần bên nhau với n. Hàm Euler được ký hiệu bởi vì ${\displaystyle \phi (n)}$ hoặc ${\displaystyle \varphi (n)}$, vì thế hàm được gọi thực hiện hàm phi Euler. Chẳng hạn, ${\displaystyle \phi (9)=6}$ vì như thế sở hữu sáu số 1, 2, 4, 5, 7 và 8 là thành phần bên nhau với 9. Định lý Euler tuyên bố rằng, nếu như n là số vẹn toàn dương ngẫu nhiên và a thành phần bên nhau với n, tức GCD(a,n) = 1, thì ${\displaystyle a^{\phi (n)}\equiv 1\mod n}$. Như vậy suy đi ra kể từ Định lý Lagrange và từ các việc a nằm trong group nhân modulo ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ nếu như và chỉ nếu như a thành phần bên nhau với n. Định lý Euler: Với từng số vẹn toàn dương n thành phần bên nhau với a, tao có: ${\displaystyle a^{\phi (n)}\equiv 1\mod n}$ (*) Định lý nhỏ Fermat cho rằng nếu như p là một số trong những thành phần thì: ${\displaystyle a^{p}\equiv a{\pmod {p}} \Leftrightarrow (a^p – a)\ \vdots\ p}$. Nếu ${\displaystyle GCD(a,p)=1}$ thì ${\displaystyle (a^{p-1} – 1)\ \vdots\ p \Leftrightarrow a^{p-1} \equiv 1\pmod{p}}$ (**) Ta thấy ấn định lý Fermat nhỏ là 1 trong tình huống nhỏ của ấn định lý Euler với n = p. Từ (*) và (**) rất có thể thấy rằng: Nếu n là số thành phần thì ${\displaystyle \phi (n)=n-1}$ [TC1] Từ khái niệm hàm phi Euler tất cả chúng ta sở hữu ${\displaystyle \phi (1)=1}$, và ${\displaystyle \phi (n)=(p-1)p^{k-1}}$ với n là lũy quá bậc k của số thành phần p (${\displaystyle n=p^{k}}$) . Trong khi, ${\displaystyle \phi }$ là 1 trong hàm nhân tính; nếu như m và n là thành phần bên nhau thì ${\displaystyle \phi (m*n)=\phi (m)*\phi (n)}$ [TC2]. Từ đặc thù 1 tao thấy ${\displaystyle n=p^k}$ thì ${\displaystyle \phi(p^k)=p^k-p^{k-1}}$ [TC3] với p là số vẹn toàn tố Xem tăng cơ hội minh chứng những đặc thù trên: https://www.tvhoang.com/articles/2017/11/fermat-euler 1. Tính ${\displaystyle \phi(26)}$ Ta sở hữu ${\displaystyle \phi(26)=\phi(2*13)}$ tuy nhiên ${\displaystyle GCD(2, 13)=1}$ nên theo đuổi TC2 sở hữu ${\displaystyle \phi(2*13) = \phi(2)*\phi(13)}$ Lại thấy 2 và 13 đều là số thành phần nên theo đuổi TC1 ${\displaystyle \phi(2)*\phi(13)=(2-1)*(3-1)=1*12=12}$ Vậy ${\displaystyle \phi(26)=12}$ 2. Tính ${\displaystyle \phi(2^3)}$ Ta thấy 2 là số thành phần nên theo đuổi TC3 sở hữu ${\displaystyle \phi(2^3)=2^3-2^{3-1}=8-4=4}$ Vậy ${\displaystyle \phi(2^3)=4}$ 3. Tính ${\displaystyle 7^{4} mod 10 }$ Ta có${\displaystyle \phi(10)=\phi(2*5)= \phi (2)*\phi (5) (TC2) = (2-1)*(5-1) (TC1) = 4}$ với 2 và 5 là những số thành phần. ${\displaystyle 7^4 mod 10 = 7^{\phi(10)} mod 10 = 1 mod 10 }$ (Theo ấn định lý Euler) Vậy ${\displaystyle 7^4 \equiv 1{\pmod{10}}}$ Áp dụng ấn định lý Euler và hàm phi Euler với những đặc thù nhằm tính: Tài liệu tham ô khảo: Nam.Name.VNThuật toán đánh giá Fermat
Inputs: n: độ quý hiếm nhằm đánh giá tính vẹn toàn tố; k: thông số nhập cuộc vô quy trình kiểm tra
Output: ăn ý số nếu như n là ăn ý số, còn nếu như không thành phần xác suất
repeat k times:
lấy a tình cờ vô [1, n − 1]
if an − 1 mod n ≠ 1 then
return composite
return probably primeChứng minh
Ví dụ
Bài tập
Định lý Euler và Hàm phi Euler
Định nghĩa
Tính chất
Ví dụ
Bài tập