Tích của hai số nguyên tố cụ thể

Nói cách khác, có thuật toán phân tích thừa số nào phù hợp hơn cho những trường hợp như vậy không? $p, q$ hơn các thuật toán tối tân cho các số nguyên tố có dạng tổng quát ?

Nếu bạn biết điều đó $n$ có dạng $(x^d+1)(x^e+1)$, nhân tố hóa nên tầm thường.

$n = x^{d+e} + x^d + x^e + 1 \approx x^{d+e}$ (trừ khi một trong hai $x^d$ hoặc $x^e$ nhỏ). Chúng ta có thể dễ dàng quét qua các giá trị có thể có của $\sqrt[d+e]{n}$ cho các giá trị khác nhau có thể có của $d+e$, và tìm một giá trị gần với giá trị nguyên của $x$; điều đó mang lại cho chúng tôi $x$ và $d+e$; tại thời điểm này, chúng tôi biết $n - (x^{d+e} + 1) = x^d + x^e$, từ đây, phục hồi $d$ và $e$ dễ.

Và nếu (nói) $x^d$ nhỏ, thì một tìm kiếm đơn giản cho các yếu tố nhỏ (có thể là bạo lực hoặc nếu bạn muốn có được sự ưa thích, ECM) sẽ nhanh chóng tìm thấy $x^d+1$

Có những chiến lược khác để tạo ra một yếu tố $n$ của biểu mẫu này - dòng dưới cùng: chỉ có quá ít giá trị có thể có của $x, d, e$ để làm cho điều này thậm chí hơi khó khăn.