RSA: special parameters construction

I have to show that the following construction of $q$ allows to factorize $N$ :

• $p \in \mathbb{P}$, the set of primes
• $q \gets p \cdot \left((p - 1)^{-1} \bmod e\right) \bmod e$
• $k=1$
• while $q \not \in \mathbb{P}$:
• $q \gets q + k \cdot e$
• $k \gets k + 1$
• end while

I tried to analyse $N \bmod e$ and transform the expression but without success.

If some can give me some hints

Edit:

$p$ is 512 bits size, $e$ is 504 bits size.

Let's $\alpha = (p - 1)^{-1} \bmod e$ then $N = p \cdot (\alpha + 1 + k \cdot e)$

Finding $q$ is equivalent to finding $\alpha$.

• Isn't $q$ going to be super small (assuming $e$ is small), given the density of the primes? – Thomas Sep 27 '15 at 18:32
• Note that e has to be large for this to make sense. Suppose e is larger than p. What is q congruent to modulo e? What is then N congruent to modulo e? – K.G. Sep 27 '15 at 18:48
• ... and what can you do with the resulting congruence? – SEJPM Sep 27 '15 at 19:04
• $\mathbb{P}$ is prime set number. $e$ is the public exponent which 63 bits size and $p$ is 64 bits size – Jeremy Sep 28 '15 at 10:51
• Please provide more information. Else I would suggest this question looks like a fake. – user27950 Oct 5 '15 at 18:51

It is easily seen that the value of $q$ is invariant modulo $e$. As a consequence, we always have $q \equiv p\cdot (p-1)^{-1} \pmod e$ and thus $q(p-1) \equiv p \pmod{e}$. So, the resulting modulus $N = pq$ is such that $N \equiv (p+q) \pmod e$.

Example: With $p=10598342506117936057$ and $e=5004898192290387253$, the proposed construction yields the prime $q = 106091356957242239963$. One can check that $p\cdot q \bmod e = 1577041040681269201 = (p+q) \bmod e$.

The value of $q$ generated is such that $q\equiv p\cdot(p - 1)^{-1}\pmod e$. Multiplying by $p-1$, it follows that $q\cdot(p-1)\equiv p\pmod e$, thus $p\cdot q\equiv p+q\pmod e$, thus $$\exists j\in\mathbb N,\; p+q=(N\bmod e)+j\cdot e$$ where

• we know $N$ and $e$, thus know $(N\bmod e)$;
• $j=(p+N/p-(N\bmod e))/e$, thus $j\ge j_\text{min}$ with $j_\text{min}=\lceil(p_\text{min}+N/p_\text{max})/e\rceil$ which we can compute (the minimum $j_\text{min}$ will be at least $2^7$);
• the question's $k$ is unlikely to be more than few times $\log e$ (given the density of primes), and that tells us $j$ can't be too large (it's very likely less than $2^{19}$).

We are thus expected to meet the right $j$ after manageably few tries starting from $j_\text{min}$ onwards; further, $p+q$ is even, $e$ is odd, thus $j$ is of the same known parity as $(N\bmod e)$ is, which halves our likely number of candidate $j$ (to very likely less than $2^{18}$).

It holds that $\Big({p+q\over2}\Big)^2-\Big({p-q\over2}\Big)^2=N$, thus the right $j$ is such that $\left({(N\bmod e)+j\cdot e\over 2}\right)^2-N$ is a square. When we find a $j$ matching this condition, $N$ factors as $${(N\bmod e)+j\cdot e\over 2}\pm\sqrt{\left({(N\bmod e)+j\cdot e\over 2}\right)^2-N}$$

As an alternate method, if we can fully factor $e$ into $\prod r^s$ with a moderate number of terms (say $t<10$, which can be feasible for random $e$, including any prime $e$), then we can find the solutions to $p\cdot q\equiv p+q\pmod e$: we solve that modulo each of the $r^s$, then combine the results using the Chinese Remainder Theorem, giving $2^t$ possible values for $p\bmod e$. And, for each of these, we have manageably few $p$ to try (less than $2^9$).