Thread: Odd 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.

Umm … if is known, then surely its prime factors are also known?

Originally Posted by Mouhaha

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.

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.

Originally Posted by Nehushtan

Umm … if is known, then surely its prime factors are also known?

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

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.

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).

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

That would be quite the discovery! However keep in mind that the condition "a mod(p) = q-p" would rarely hold for most composites that are the product of two primes.