If n = pq, then prove that the following two equations are valid: (1) p + q = n

Question

If n = pq, then prove that the following two equations are valid:
(1) p + q = n - (p - 1)(q - 1) + 1

(2) p - q = sqrt( (p + q)^2 - 4n)

Suppose that an algorithm were discovered that given an integer n = pq, a product of two distinct primes, could quickly (in polynomial time) calculate !(n) = (p - 1)(q - 1). Then use the fact that
p = 1/2 ((p + q) + (p - q))
and that
q = 1/2 ((p + q) - (p - q))
and the results of equations (1) and (2) to explain why there would be an efficient (polynomial time) algorithm to factor n into its prime divisors.

Explanation / Answer

Hi Willy: I just hava a doubt whether n is the producto of two primes or not. Suppose it's. Then the algorithm to calculate it's prime factors would be: pro := phi(n); sum := n - pro + 1; dif := sqrt((p + q)^2 - 4*n) p = (sum + dif)/2; q = (sum - dif)/2; The algorithm is polynomial in time, as takes a constant number of steps, and in any step, it takes at most polynomial time (in calculating phi(n)). Hope this helps.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.