Sorry, an error occurred while loading the content.

Help on Semi-prime

Expand Messages
• 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 =
Message 1 of 2 , Apr 29, 2013
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. If it is possible will it be useful to factorize 'N' quickly.

For example 77 = 7*11 using 77 suppose we found a = 17 and b = 94 here 17 = 94 = 3(mod 7) and 17 = 94 = 6(mod 11). Can any one please explain whether is it possible to do so, if it is possible whether it will be useful to factorize a given number quickly.
• ... 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 2 of 2 , Apr 30, 2013

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