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.