solution

Nếu người tạo khóa RSA vô tình chọn hai số nguyên tố $p, q$ gần nhau thì môđun $n = p \cdot q$ có thể bị phá vỡ rất nhanh bằng thuật toán phân tích Fermat, không cần thử chia lần lượt các số nguyên tố.

Ý tưởng: vì $p, q$ gần nhau nên tồn tại $a, b$ nguyên không âm sao cho

$n = a^2 - b^2 = (a-b)(a+b), \quad p = a - b,\ q = a + b.$

Thuật toán bắt đầu từ $a = \lceil \sqrt{n} \rceil$, kiểm tra $a^2 - n$ có phải số chính phương không; nếu chưa thì tăng dần $a$ lên 1 đơn vị và lặp lại, đến khi tìm được $b$ nguyên sao cho $b^2 = a^2 - n$.

Cho $n = p \cdot q$ với $p, q$ là hai số nguyên tố (có thể bằng nhau) và hiệu $|p - q|$ đủ nhỏ để thuật toán Fermat hội tụ nhanh, hãy tìm $p$ và $q$.

Ví dụ: $n = 10201 = 101 \times 101$, in ra 101 101.