110pt Let n pq be a product of two distinct primes Show that

1.[10pt] Let n pq be a product of two distinct primes. Show that if o(n) and n are known, then it is possible to compute p and g efficiently. Hint: Derive a quadratic equation (over the integers) in the unknown p

Solution

SOLUTION :-

Let n= pq be the product of two distinct primes.

Given

(n)=(p1)(q1)

thus,

(n)=(p1)(q1)

= pq - p -q +1

= pq - (p+q) + 1

= n - (p+q) +1

thus,

p+q = n + 1 - (n)

pq = n

By using quadratic formula we solve p,q.