solution

Đề bài: [An toàn thông tin] Khôi phục p, q từ n và phi(n)

Khôi phục hai nguyên tố RSA từ n và phi(n)

Nếu lộ phi(n) thì kẻ tấn công khôi phục được p, q của RSA. Với n = p*q và phi = (p-1)(q-1) = n - (p+q) + 1, ta có:

s = p + q = n - phi + 1
p, q là nghiệm của x^2 - s*x + n = 0, tức p = (s - sqrt(s^2 - 4n)) / 2, q = (s + sqrt(s^2 - 4n)) / 2.

Cho n và phi, hãy in p và q (p <= q) trên một dòng, cách nhau bởi dấu cách. Bảo đảm dữ liệu hợp lệ.

Ví dụ

Input:
3233 3120
Output:
53 61

s = 3233 - 3120 + 1 = 114, sqrt(114^2 - 4*3233) = 8, p=53, q=61.

Định dạng đầu vào:
Một dòng chứa hai số nguyên n và phi.
Ràng buộc đầu vào:
n = p*q với p, q nguyên tố phân biệt, n <= 10^18
Định dạng đầu ra:
In p và q với p <= q, cách nhau bởi dấu cách.

Ví dụ:

Đầu vào:

3233 3120

Đầu ra:

53 61

Giải thích:

s = 3233 - 3120 + 1 = 114; căn của 114^2 - 4*3233 là 8; suy ra p = 53, q = 61.

Đang tải editor...