Hệ số nhanh

Question

Đối với một số n nhất định (chúng tôi biết rằng n = p^a * q^b, đối với một số số nguyên p, q và một số nguyên a, b) và một số φ (n) (http://en.wikipedia.org/wiki/Euler%27s_totient_function)) tìm p, q, a và b.

Bắt là n và φ (n) có khoảng 200 chữ số để thuật toán phải rất nhanh. Dường như vấn đề này rất khó và tôi hoàn toàn không biết cách sử dụng φ (n).

Cách tiếp cận điều này?

Answer 1

Đối với n = p^a * q^b, tổng thể là φ(n) = (p-1)*p^(a-1) * (q-1)*q^(b-1). Không mất tính tổng quát, p < q.

Vì vậy gcd(n,φ(n)) = p^(a-1) * q^(b-1) nếu p không chia q-1 và gcd(n,φ(n)) = p^a * q^(b-1) nếu p chia q-1.

Trong trường hợp đầu tiên, chúng tôi có n/gcd(n,φ(n)) = p*q và φ(n)/gcd(n,φ(n)) = (p-1)*(q-1) = p*q + 1 - (p+q), do đó bạn có x = p*q = n/gcd(n,φ(n)) và y = p+q = n/gcd(n,φ(n)) + 1 - φ(n)/gcd(n,φ(n)). Sau đó, việc tìm kiếm p và q rất đơn giản: y^2 - 4*x = (q-p)^2, vì vậy q = (y + sqrt(y^2 - 4*x))/2 và p = y-q. Sau đó, tìm số mũ a và b là không đáng kể.

Trong trường hợp thứ hai, n/gcd(n,φ(n)) = q. Sau đó, bạn có thể dễ dàng tìm số mũ b, chia cho q cho đến khi phân chia còn lại, và do đó có được p^a. Phân chia φ(n) bởi (q-1)*q^(b-1) cung cấp cho bạn z = (p-1)*p^(a-1). Sau đó, p^a - z = p^(a-1) và p = p^a/(p^a-z). Tìm số mũ a là một lần nữa tầm thường.

Vì vậy, nó vẫn là để quyết định trường hợp bạn có. Bạn có trường hợp 2 nếu và chỉ khi n/gcd(n,φ(n)) là số nguyên tố.

Vì lý do đó, bạn cần một thử nghiệm nguyên thủy phong nha. Hoặc trước tiên bạn có thể giả sử rằng bạn có trường hợp 1 và nếu điều đó không thành công, hãy kết luận rằng bạn có trường hợp 2.

Answer 2

Hãy thử tìm hiểu xem n/(n - φ (n)) là gì.

Theo dõi:

n/(n - φ (n)) = pq. Bạn chỉ cần tiếp tục chia n cho pq.