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