Loading ...
Sorry, an error occurred while loading the content.

Re: Help on Semi-prime

Expand Messages
  • djbroadhurst
    ... No. Explanation: by the CRT, the residue of a , modulo N, is unique. Hence b tells us nothing new, since b = a + m*N, where m is any integer.
    Message 1 of 2 , Apr 30, 2013
    • 0 Attachment
      --- In primenumbers@yahoogroups.com,
      "kad" <yourskadhir@...> wrote:

      > Let N = pq be any semi-prime where factors p and q are unknown.
      > By knowing 'N' alone is it possible to find a and b such that
      > a = b = k(mod p) and a = b = l(mod q) where k != l.

      No.

      Explanation: by the CRT, the residue of 'a', modulo N, is unique.
      Hence 'b' tells us nothing new, since b = a + m*N,
      where 'm' is any integer. Knowledge of Mod(a,N) immediately
      gives the factorization: N = gcd(N,a-k)*gcd(N,a-1),
      so finding 'a' is as difficult as factorizing the semiprime N.

      David
    Your message has been successfully submitted and would be delivered to recipients shortly.