Join Log in
Score:1
Dimitri Koshelev avatar Crypto

Factorization of the product of two specific primes

id flag
Dimitri Koshelev

Help me please.

Consider specific primes $p = x^{d} + 1$ and $q = x^{e} + 1$ for some $x, d, e \in \mathbb{N}$. Can their product $n = pq$ be factorized faster than the product of general primes ? In other words, is there a factorization algorithm that is more suitable for such $p$, $q$ than the state-of-the-art algorithms for primes of general form ?

Thank you in advance for your response.

73
0 + 0
rsa
Score:4
poncho avatar Crypto
my flag
poncho

In other words, is there a factorization algorithm that is more suitable for such $p, q$ than the state-of-the-art algorithms for primes of general form ?

If you know that $n$ is of the form $(x^d+1)(x^e+1)$, factorization should be trivial.

$n = x^{d+e} + x^d + x^e + 1 \approx x^{d+e}$ (unless either $x^d$ or $x^e$ is small). We can easily scan through the possible values of $\sqrt[d+e]{n}$ for the various possible values of $d+e$, and find one that gives close to an integer value of $x$; that gives us $x$ and $d+e$; at this point, we know $n - (x^{d+e} + 1) = x^d + x^e$, from here, recovering $d$ and $e$ is easy.

And if (say) $x^d$ is small, then a simple search for small factors (either brute force or if you want to get fancy, ECM) will quickly find $x^d+1$

There are other strategies to factor an $n$ of this form - bottom-line: there are just too few possible values of $x, d, e$ to make this even slightly difficult.

0 + 0
Dimitri Koshelev avatar
id flag
Dimitri Koshelev
poncho, thanks. What if $p = x^d + 1$, but $q$ is a general prime ?
0
Reply
poncho avatar
my flag
poncho
@DimitriKoshelev: actually, all primes $p$ are in that form (with $d=1$ :-)
0
Reply
Dimitri Koshelev avatar
id flag
Dimitri Koshelev
what if $x$ is small ?
0
Reply
Score:1
Einar Rødland avatar Crypto
pk flag
Einar Rødland

Here's a supplement to poncho's answer.

Note that $n-1=x^{d+e}+x^d+x^e$ which is a multiple of $x^{\min(d,e)}$. Unless $x$ is large, it can easily be found by looking for small factors of $n-1$; next, how many times those small factors divide $n-1$, which should be $\min(d,e)$ times (except from the special case of $x=2$ and $d=e$).

This method is particularly effective for small $x$. And if it doesn't give a solution with small, or relatively small, value of $x$, you're in the setting where poncho's approach will be very effective.

0 + 0
Dimitri Koshelev avatar
id flag
Dimitri Koshelev
Einar Rødland, thanks. What if $p = x^d+1$, but $q$ is a general prime ?
0
Reply
Einar Rødland avatar
pk flag
Einar Rødland
@DimitriKoshelev: You can let $d=1$, $x=p-1$, and there's no restriction on $p$. If $x$ is small, but $p$ is big, the possible values of $p$ are more limited. Can't immediately thing of anything better than trial-and-failure.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.