Máy tính số nguyên tố

Kiểm tra nguyên tố · Phân tích thừa số · Sinh số nguyên tố

Nhập số

HƯỚNG DẪN

Tìm hiểu thêm

Số nguyên tố là gì?

Số nguyên tố là một số tự nhiên lớn hơn 1, chỉ có hai ước dương là 1 và chính nó. Ví dụ: 2, 3, 5, 7, 11, 13... Ngoại trừ 2, mọi số nguyên tố đều là số lẻ. Số nguyên tố được gọi là "nguyên tử của các con số."

Sàng Eratosthenes

Đây là một thuật toán cổ do nhà toán học Hy Lạp Eratosthenes phát triển vào khoảng năm 240 TCN. Thuật toán này tìm tất cả số nguyên tố đến n một cách hiệu quả bằng cách lần lượt đánh dấu các bội số của từng số nguyên tố là hợp số.

Số nguyên tố sinh đôi

Số nguyên tố sinh đôi là các cặp số nguyên tố chênh nhau 2 đơn vị: (3,5), (5,7), (11,13), (17,19)... Việc có vô hạn số nguyên tố sinh đôi hay không vẫn là một bài toán chưa được giải.

Ứng dụng của số nguyên tố

• Mã hóa RSA: Bảo mật dựa trên độ khó khi phân tích các số lớn • Hàm băm: Bảng băm có kích thước nguyên tố giúp giảm va chạm • Sinh số ngẫu nhiên: Số nguyên tố trong các thuật toán PRNG • Tự nhiên: Chu kỳ sống của ve sầu dùng số nguyên tố

Định nghĩa và lịch sử của số nguyên tố

Số nguyên tố là một số tự nhiên lớn hơn 1, không có ước nào ngoài 1 và chính nó. Số nguyên tố nhỏ nhất là 2, cũng là số nguyên tố chẵn duy nhất. Dãy số: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... Nhà toán học Hy Lạp cổ đại Euclid đã chứng minh khoảng năm 300 TCN rằng tồn tại vô hạn số nguyên tố. Số nguyên tố được gọi là "nguyên tử của các con số" vì mọi số nguyên > 1 đều phân tích duy nhất thành các thừa số nguyên tố (Định lý cơ bản của số học). Ví dụ: 60 = 2² × 3 × 5, 360 = 2³ × 3² × 5.

Các thuật toán kiểm tra tính nguyên tố

Cách đơn giản nhất là thử tính chia hết cho mọi số từ 2 đến n-1, nhưng cách này rất kém hiệu quả. Một cải tiến là chỉ thử từ 2 đến √n, vì nếu n = a × b thì a ≤ √n hoặc b ≤ √n. Với 101: √101 ≈ 10.05, nên chỉ cần thử 2, 3, 5, 7. Kiểm tra xác suất Miller-Rabin xử lý rất hiệu quả các số cực lớn. AKS (2002) là thuật toán xác định đầu tiên chạy trong thời gian đa thức. Mật mã hiện đại dùng các số có hàng trăm chữ số, nên cần các phép kiểm tra hiệu quả.

Thuật toán Sàng Eratosthenes

Do nhà toán học Hy Lạp Eratosthenes phát triển vào khoảng năm 240 TCN. Quy trình: ① Liệt kê các số từ 2 đến n. ② Đánh dấu 2 là số nguyên tố, loại các bội số (4,6,8,10...). ③ Số chưa đánh dấu tiếp theo là 3, cũng là số nguyên tố, rồi loại các bội số của nó. ④ Tiếp tục với 5, 7, v.v. đến √n. ⑤ Các số còn lại là số nguyên tố. Với n=30: các số nguyên tố là 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Độ phức tạp thời gian: O(n log log n). Có thể tìm tất cả số nguyên tố dưới 1 triệu chỉ trong vài giây.

Nguyên lý phân tích thừa số nguyên tố

Phân tích thừa số nguyên tố biểu diễn một số dưới dạng tích của các số nguyên tố. Theo Định lý cơ bản của số học, mọi số nguyên > 1 đều có một phân tích duy nhất. Cách làm: ① Bắt đầu với số nguyên tố nhỏ nhất là 2. ② Chia liên tiếp cho 2 cho đến khi không còn chia hết. ③ Thử các số nguyên tố tiếp theo 3, 5, 7... ④ Tiếp tục cho đến khi thương bằng 1. Ví dụ 360: 360÷2=180, 180÷2=90, 90÷2=45, 45÷3=15, 15÷3=5, 5÷5=1. Kết quả: 360 = 2³×3²×5. Ứng dụng: tính GCD/LCM, rút gọn phân số, bảo mật RSA.

Số nguyên tố sinh đôi và giả thuyết Goldbach

Số nguyên tố sinh đôi chênh nhau 2 đơn vị: (3,5), (5,7), (11,13), (17,19), (29,31)... Giả thuyết số nguyên tố sinh đôi cho rằng tồn tại vô hạn cặp như vậy nhưng vẫn chưa được chứng minh. Năm 2013, Yitang Zhang chứng minh có vô hạn cặp số nguyên tố chênh nhau không quá 70 triệu, sau đó con số này được giảm xuống 246. Giả thuyết Goldbach (1742): mọi số chẵn > 2 đều là tổng của hai số nguyên tố. Ví dụ: 4=2+2, 6=3+3, 8=3+5, 10=5+5. Đã được kiểm chứng đến 4×10¹⁸ nhưng vẫn chưa được chứng minh.

Mã hóa RSA và các ứng dụng thực tế

Mã hóa RSA, nền tảng của bảo mật internet, dựa trên phép nhân dễ nhưng phân tích các số nguyên tố lớn lại rất khó. Tạo khóa: ① Chọn hai số nguyên tố lớn p, q (mỗi số 1024+ bit). ② Tính n = p×q (công khai). ③ Tính φ(n) = (p-1)(q-1). ④ Chọn số mũ công khai e nguyên tố cùng nhau với φ(n) (thường là 65537). ⑤ Tính số mũ bí mật d sao cho e×d ≡ 1 (mod φ(n)). Khóa công khai: (n,e), khóa bí mật: (n,d). Mã hóa: C = M^e mod n, Giải mã: M = C^d mod n. Nếu phân tích được n để tìm p,q thì mã hóa sẽ bị phá vỡ, nhưng việc phân tích một số có hàng trăm chữ số có thể mất hàng triệu năm. Ứng dụng khác: kích thước bảng băm nguyên tố giúp giảm va chạm, chu kỳ 13/17 năm của ve sầu tránh chồng lấn với chu kỳ săn mồi, nhịp điệu nguyên tố trong âm nhạc.

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

Tôi có thể kiểm tra trong phạm vi nào?

Công cụ này hỗ trợ kiểm tra tính nguyên tố và phân tích thừa số cho các số từ 1 đến 10,000,000, còn chức năng sinh số nguyên tố và tìm cặp nguyên tố sinh đôi hoạt động trong phạm vi 2–100,000.

Vì sao số nguyên tố được dùng trong mật mã?

Nhân hai số nguyên tố lớn thì dễ, nhưng phân tích tích của chúng trở lại thành hai số đó lại cực kỳ khó. Mã hóa RSA khai thác chính sự bất đối xứng này để bảo vệ liên lạc trên internet.