# Please It is urgent I should submit it tomorrow!!!

• November 10th 2008, 09:44 AM
pouyan_afshin
Please It is urgent I should submit it tomorrow!!!
Hi all:

I will be really appreciated if someone can help me solving this homework.

imagine n = p * q where p and q are primes and are in the form of p = 2t + 1 and q = 2y + 1 where t and y are also prime.

we are given n and a number b which we know gcd(b, t * y) <> 1. (is not equal to one)

How can we efficiently factorize n?

I have some part of the solution.

n can be written as

n = 4 * t * y + 2 * t + 2 * y + 1

now n - 1 = 4 * t * y + 2 * t + 2 * y

now we should do sth with this and knowing the b to factor n. but what I do not know.

If n/(2b+1) is not an integer then you know that b must be t*y. Since n-1 = 4t*y + 2(t+y) it follows that t+y = (1/2)(n-1-4b). Thus you now know t*y and t+y. But t and y are the roots of the quadratic equation $x^2-(t+y)x+ty=0$. So all you have to do to determine t and y is to solve a quadratic equation.