Công cụ phân tích thừa số Fermat

Giới thiệu về công cụ này

Phương pháp phân tích thừa số Fermat khai thác thực tế rằng mọi số nguyên lẻ N đều có thể viết thành hiệu của hai bình phương, N = a² − b² = (a−b)(a+b). Thuật toán bắt đầu từ a = ⌈√N⌉ và tăng a thêm 1 mỗi bước, kiểm tra xem a² − N có tự là một số chính phương (b²) hay không; ngay khi đúng, N được phân tích ngay thành (a−b)(a+b). Máy tính này chạy vòng lặp đó và hiển thị mọi bước nó đã đi để tìm các thừa số.

Phương pháp hội tụ chỉ sau rất ít bước khi hai thừa số của N gần nhau — điểm yếu chính của nó cũng là ứng dụng thực tế quan trọng nhất: sinh viên mật mã học và nhà nghiên cứu bảo mật dùng phân tích Fermat để chứng minh vì sao các modulus RSA phải được xây từ những số nguyên tố cách xa nhau, vì các số nguyên tố chọn quá gần nhau làm modulus bị phá dễ dàng. Đây cũng là bài tập chuẩn trong các khóa học lý thuyết số để minh họa lập luận hiệu của hai bình phương.