Browse Groups

• ... 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
View Source

> 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.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.