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

Printable View

• Nov 10th 2008, 10: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.

Thanks for your help in advance.
• Nov 11th 2008, 04:23 AM
Opalg
If t and y are prime then the only factors of t*y are 1, t, y and t*y. So the only possibilities for b are b=t, b=y or b=t*y.

If b = t or y then 2b+1 will be a factor of n. So start by dividing n by 2b+1. If the answer is an integer then you have already factorised n.

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.