Lets say we have 2 public values: N and y

$$ N = pq $$

$$ y = r(p-1) $$

Where p, q, and r are large primes, are different, have a large distance between them and are kept secret.

I have three questions:

  1. Does the release of y make factorization of N easier? If so, how much easier does the problem become (if at all)?
  2. Does the problem become easy (ie. solvable in seconds/days/months/years)?
  3. If it does, can changing p to a large random safe-prime make it slightly harder or as hard as factoring N?
  • $\begingroup$ More could be said about how easy the factorization of $N$ becomes if you put some orders of magnitude around $p,q,r$. Two sorts of attacks come to mind: one involves factoring $y$ to get candidates for $r$ (and hence for $p-1$), the other involves using $y$ as an exponent to raise a random base modulo $N$ (thus getting a GCD with $N$ as a multiple of $p$ but not $q$). Mileage will vary depending on the relative sizes of these primes $p,q,r$. $\endgroup$
    – hardmath
    Commented Apr 11 at 21:19
  • $\begingroup$ $(p-1)$ will have small factors. $\endgroup$
    – kelalaka
    Commented Apr 11 at 21:21
  • $\begingroup$ @hardmath Lets say that p, q, r are 2048-4096 bits. $\endgroup$
    – block103
    Commented Apr 11 at 21:49
  • 2
    $\begingroup$ HINT: Pick a random number and raise it to the power $y\mod N$. What can you say about this value mod $p$? $\endgroup$
    – Daniel S
    Commented Apr 11 at 23:38


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.