Let n=p*q (p and q are odd prime). Let a mod(p)=(q-p). The numbers a and n are known. Can you find p and q? Thank you.

Printable View

- Mar 3rd 2013, 08:25 AMMouhahaOdd semi-prime challenge
Let n=p*q (p and q are odd prime). Let a mod(p)=(q-p). The numbers a and n are known. Can you find p and q? Thank you.

- Mar 3rd 2013, 09:30 AMNehushtanRe: Odd semi-prime challenge
Umm … if $\displaystyle n$ is known, then surely its prime factors are also known? (Thinking)

- Mar 3rd 2013, 10:48 AMjamixRe: Odd semi-prime challenge
1 ) For the special case of a < p < q, we have a mod (p) = a = q-p from which one gets q = p + a. We then have the relation n = p x q = p x (p + a) = p^2 + ap........Subtracting n from both sides gives us

p^2 + ap - n = 0, which is a quadratic equation in terms of "p". Since the discriminant is a^2 + 4n > 0, this will have a solution via the quadratic equation.

Now this case assumes that a < p. Hence if our given "a" is small enough, we can just check all the prime numbers 2,3,5......that are < a. If we find a prime factor first, then as Nehushtan points out, were already done but if not, we can solve this easily via the quadratic formula above as our initial assumption will have been justified.....

2) FOR GENERAL CASE (ie "a" is too large to be efficiently solved as described above), we have a - kp = q - p for some "**unknown**" integer k and we have q = a + (k-1)p..........Following along the same lines as before, we get (k-1)p^2 + ap - n = 0.........Since we do not know what "k-1" is we cannot solve directly via quadratic formula, however because we know that "p" is an integer, it follows that a^2 + 4 x (k-1) x n is a square...........From here I'm not sure of any method other than a "brute force" approach that will efficiently solve for p. - Mar 3rd 2013, 11:23 AMjamixRe: Odd semi-prime challenge
On the surface of things, this would be an inefficient method since factorization is slow. With that said, since q-p = a mod (p) < p, we have that q < 2p. However we also have p < q, since "a mod(p)" is by definition positive. Since p < q < 2p, this question could likely be solved very quickly via the "Fermat factoring algorithm" for large n!

Fermat's factorization method - Wikipedia, the free encyclopedia - Mar 3rd 2013, 11:28 AMMouhahaRe: Odd semi-prime challenge
Here is an example :

n=7313

a=955

We have to solve the following equation :

955 mod(p)=q-p

It is easy to factorize n in this case.

n=7313=71*103

955 mod 71 = 32

q-p=103-71=32

But if n is 400 digit-number it will be a headache.

What is the added information that we need to solve it even if n is a huge number?

I assume that I have found a mathematical way to find the number a. - Mar 3rd 2013, 05:38 PMjamixRe: Odd semi-prime challenge
If a^2 < n / 2, then a < p (where p is the smaller prime factor of n) and the problem can be solved via the quadratic formula.

I don't know how it can be solved more generally, but as the p < q < 2p, the problem does make using the "Fermat factoring method" of n more desirable (keep in mind that for a 400-digit number, this method will still be inefficient).

Quote:

I assume that I have found a mathematical way to find the number a.