Máy tính Hàm Phi Euler

Chào mừng bạn đến với Máy tính hàm phi Euler, một công cụ lý thuyết số toàn diện giúp tính toán φ(n) (hàm phi của Euler) với phân tích thừa số nguyên tố từng bước, trực quan hóa lưới số nguyên tố cùng nhau tương tác và phân tích chuyên sâu. Cho dù bạn đang học đại số trừu tượng, chuẩn bị cho các cuộc thi toán, làm việc về mã hóa RSA hay khám phá số học modulo, máy tính này cung cấp khả năng tính toán chuyên nghiệp cùng nội dung giáo dục phong phú.

Hàm phi Euler là gì?

Hàm phi Euler φ(n), còn được gọi là hàm Euler, đếm số lượng các số nguyên dương từ 1 đến n là nguyên tố cùng nhau với n. Hai số được gọi là nguyên tố cùng nhau khi ước chung lớn nhất (ƯCLN) của chúng bằng 1.

Ví dụ, φ(12) = 4 vì chính xác có bốn số — 1, 5, 7 và 11 — là nguyên tố cùng nhau với 12 trong số các số nguyên từ 1 đến 12.

Công thức tích

Cách hiệu quả nhất để tính φ(n) là sử dụng phân tích thừa số nguyên tố của n. Nếu \(n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}\), thì:

Điều này có nghĩa là chúng ta nhân n với \((1 - 1/p)\) cho mỗi thừa số nguyên tố khác nhau p của n. Các số mũ không quan trọng — chỉ các số nguyên tố khác biệt mới quan trọng.

Các tính chất chính

Định lý Euler

Định lý Euler là kết quả quan trọng khiến hàm phi trở nên thiết yếu trong mật mã học:

Đây là sự tổng quát hóa của định lý nhỏ Fermat (trường hợp đặc biệt khi n là số nguyên tố). Nó tạo thành nền tảng toán học của mã hóa RSA.

Cách sử dụng máy tính này

1. Nhập một số nguyên dương: Nhập bất kỳ giá trị nào từ 1 đến 1.000.000 vào ô nhập liệu.
2. Sử dụng ví dụ nhanh: Nhấp vào các nút ví dụ để thử các giá trị kinh điển như số nguyên tố, hợp số hoặc số bán nguyên tố kiểu RSA.
3. Xem kết quả của bạn: Máy tính hiển thị φ(n), phân tích thừa số nguyên tố, tỷ lệ số nguyên tố cùng nhau và các tính chất được phát hiện.
4. Khám phá lưới số nguyên tố cùng nhau: Đối với n ≤ 400, hãy xem những số nào là nguyên tố cùng nhau với n trong một lưới hình ảnh có hoạt ảnh.
5. Nghiên cứu biểu đồ xu hướng: Xem φ(k) thay đổi như thế nào cho k = 1 đến min(n, 100).

Kết nối mã hóa RSA

Trong mật mã học RSA, hàm phi Euler đóng vai trò trung tâm:

1. Chọn hai số nguyên tố lớn p và q. Tính n = p × q.
2. Tính φ(n) = (p−1)(q−1).
3. Chọn số mũ công khai e sao cho gcd(e, φ(n)) = 1.
4. Tính số mũ riêng d sao cho e × d ≡ 1 (mod φ(n)).

Bảo mật của RSA dựa trên sự khó khăn của việc tính φ(n) mà không biết phân tích thừa số của n. Nếu một kẻ tấn công có thể tính φ(n) một cách hiệu quả, họ có thể phá vỡ RSA.

Các giá trị phổ biến của φ(n)

Câu hỏi thường gặp

Hàm phi Euler là gì?

Hàm phi Euler φ(n), còn gọi là hàm Euler, đếm số lượng các số nguyên dương từ 1 đến n là số nguyên tố cùng nhau (coprime) với n. Hai số được gọi là nguyên tố cùng nhau khi ước chung lớn nhất (ƯCLN) của chúng là 1. Ví dụ, φ(12) = 4 vì chỉ có 1, 5, 7 và 11 là nguyên tố cùng nhau với 12.

Làm thế nào để tính hàm phi Euler?

Để tính φ(n): (1) Tìm các thừa số nguyên tố của n. (2) Áp dụng công thức tích: φ(n) = n × ∏(1 − 1/p) cho mỗi thừa số nguyên tố p khác nhau của n. Ví dụ, φ(12) = 12 × (1−1/2) × (1−1/3) = 12 × 1/2 × 2/3 = 4. Đối với số nguyên tố p, φ(p) = p−1. Đối với lũy thừa số nguyên tố p^k, φ(p^k) = p^k − p^(k−1).

Tại sao hàm phi Euler quan trọng trong mã hóa RSA?

Trong mã hóa RSA, modulo n = p × q là tích của hai số nguyên tố lớn. Hàm phi φ(n) = (p−1)(q−1) được sử dụng để tính khóa riêng: số mũ giải mã d phải thỏa mãn e × d ≡ 1 (mod φ(n)), trong đó e là số mũ mã hóa công khai. Nếu không biết φ(n) — điều này đòi hỏi phải phân tích thừa số n — việc tính d là không khả thi về mặt tính toán.

Định lý Euler là gì và nó liên quan thế nào đến hàm phi?

Định lý Euler phát biểu rằng nếu a và n là số nguyên tố cùng nhau, thì a^φ(n) ≡ 1 (mod n). Đây là một sự tổng quát hóa của định lý nhỏ Fermat (áp dụng khi n là số nguyên tố). Nó là nền tảng trong số học modulo và mật mã học, cung cấp cơ sở toán học cho mã hóa RSA và lũy thừa modulo hiệu quả.

Các tính chất chính của hàm phi Euler là gì?

Các tính chất chính bao gồm: (1) φ(1) = 1. (2) Đối với số nguyên tố p: φ(p) = p−1. (3) Đối với lũy thừa số nguyên tố p^k: φ(p^k) = p^(k−1)(p−1). (4) Tính chất nhân: nếu gcd(m,n) = 1, thì φ(m×n) = φ(m)×φ(n). (5) Tổng các ước số: Σ φ(d) = n cho tất cả các ước d của n. (6) φ(n) luôn là số chẵn cho n > 2.

Hai số nguyên tố cùng nhau nghĩa là gì?

Hai số nguyên a và b là nguyên tố cùng nhau (còn gọi là tương đối nguyên tố) nếu ước chung lớn nhất của chúng là 1, nghĩa là chúng không có thừa số nguyên tố chung. Ví dụ, 8 và 15 là nguyên tố cùng nhau vì gcd(8,15) = 1, mặc dù cả hai đều không phải là số nguyên tố. Hàm phi φ(n) đếm chính xác có bao nhiêu số nguyên từ 1 đến n nguyên tố cùng nhau với n.

Tài nguyên bổ sung

• Hàm phi Euler - Wikipedia (Tiếng Anh)
• Hệ thống mật mã RSA - Wikipedia (Tiếng Anh)
• Định lý Euler - Wikipedia (Tiếng Anh)