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

Bài học chính

• Mọi số nguyên lớn hơn 1 đều có chính xác một hệ số nguyên tố - bất kể bạn thử số nguyên tố nào trước, bạn đều đạt được cùng một kết quả.
• Một số nguyên tố chỉ phân tích thành một số hạng: chính nó lũy thừa bậc nhất (7 = 7¹).
• Cho dù số thập phân của một phân số kết thúc hay lặp lại dấu vết trực tiếp trở lại hệ số nguyên tố - chỉ 2 giây và 5 giây trong mẫu số tạo ra số thập phân tận cùng.
• Việc phân tích hệ số nguyên tố trở nên khó hơn theo cấp số nhân đối với máy tính khi số lượng ngày càng lớn hơn, đây là cơ sở cho tính bảo mật của mã hóa RSA.

Phương pháp chia từng bước

Bắt đầu với số nguyên tố nhỏ nhất, 2. Nếu số đó chia đều, hãy chia và lặp lại với 2 — không chuyển sang số nguyên tố tiếp theo cho đến khi 2 không còn hoạt động. Khi nó dừng chia đều, hãy chuyển đến 3, rồi 5, rồi 7, v.v., luôn kiểm tra lại cùng một số nguyên tố trước khi tiến lên. Dừng khi thương số chạy đạt 1.

Ví dụ hoạt động: bao thanh toán 360

Kiểm tra câu trả lời: 2³ = 8, 3² = 9 và 8 × 9 × 5 = 360 - xác nhận hệ số hóa là chính xác.

Tại sao hệ số nguyên tố đảm bảo mã hóa

Đối với các số nhỏ, việc phân tích thành nhân tử gần như ngay lập tức - máy tính phân tích 91 thành 7 × 13 trong một phần của giây. Nhưng khi hai số nguyên tố liên quan dài hàng trăm chữ số, việc nhân chúng với nhau (để tạo khóa chung) vẫn mất một phần nghìn giây, trong khi việc phân tích sản phẩm đó ra (phá khóa) sẽ mất nhiều thời gian hơn tuổi của vũ trụ khi sử dụng máy tính cổ điển. RSA và các hệ thống mật mã tương tự xây dựng toàn bộ mô hình bảo mật của họ dựa trên khó khăn thực tế, một chiều này.

Những lỗi thường gặp cần tránh

• Dừng lại sau khi chia cho một số nguyên tố chỉ một lần - tiếp tục chia cho cùng một số nguyên tố cho đến khi nó không còn chia đều trước khi tiếp tục.
• Kiểm tra các ước số tổng hợp như 4 hoặc 6 - chỉ các ước nguyên tố mới thuộc về hệ số nguyên tố; các thừa số nguyên tố của riêng một hợp số đã được tìm thấy trước tiên.
• Quên thu gọn các số nguyên tố lặp lại thành số mũ - viết 2 × 2 × 2 × 3 × 3 dưới dạng 2³ × 3², chứ không phải dưới dạng năm số hạng lặp lại riêng biệt.
• Giả sử mọi số lớn đều khó phân tích - các số có thừa số nguyên tố nhỏ sẽ phân tích nhanh chóng bất kể kích thước; nó đặc biệt là tích của hai số nguyên tố lớn tương tự nhau chống lại việc phân tích thành thừa số.

Máy tính liên quan

• Máy tính hệ số — liệt kê mọi thừa số của một số, không chỉ các phần tử cơ bản của nó.
• Máy tính nhân tử chung lớn nhất — đưa các thừa số nguyên tố được chia sẻ vào công việc tìm kiếm GCF.
• Máy tính bội chung nhỏ nhất — kết hợp các thừa số nguyên tố để tìm bội số chung.
• Máy tính số lớn — xử lý các sản phẩm khổng lồ mà các thừa số nguyên tố lớn có thể tạo ra.