5
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Isn't $q$ going to be super small (assuming $e$ is small), given the density of the primes? $\endgroup$ – Thomas Sep 27 '15 at 18:32
  • 3
    $\begingroup$ 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? $\endgroup$ – K.G. Sep 27 '15 at 18:48
  • $\begingroup$ ... and what can you do with the resulting congruence? $\endgroup$ – SEJPM Sep 27 '15 at 19:04
  • 1
    $\begingroup$ $\mathbb{P}$ is prime set number. $e$ is the public exponent which 63 bits size and $p$ is 64 bits size $\endgroup$ – Jeremy Sep 28 '15 at 10:51
  • $\begingroup$ Please provide more information. Else I would suggest this question looks like a fake. $\endgroup$ – user27950 Oct 5 '15 at 18:51
1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for?Browse other questions tagged or ask your own question.