Sum and product of factors of a semiprime

Bacterius · #1 $Old$ November 4th, 2009, 01:48 AM

Hi all, I'm new on this forum (it is great

)

I have a maybe-hard maybe-easy question, which is the following (I have worked quite a lot on it but can't find a way around it) :

Say $n = pq$ , with p and q [non-trivial] primes (so n is semiprime)
Now say $m = p + q$ (same values of p and q obviously)

I know "n", but I need "m" (I don't know p or q). Is there a way around this, or is it just impossible ? Isn't there some kind of relation between the product and the sum of the factors of any semiprime ?

Regards.

tonio · #2 $Old$ November 4th, 2009, 06:23 AM

Quote:

Originally Posted by Bacterius $View Post$

Hi all, I'm new on this forum (it is great

)

I have a maybe-hard maybe-easy question, which is the following (I have worked quite a lot on it but can't find a way around it) :

Say $n = pq$ , with p and q [non-trivial] primes (so n is semiprime)
Now say $m = p + q$ (same values of p and q obviously)

I know "n", but I need "m" (I don't know p or q). Is there a way around this, or is it just impossible ? Isn't there some kind of relation between the product and the sum of the factors of any semiprime ?

Regards.

I wouldn't say "impossible" but as close to it as you can imagine, in particular if the number n is big, and it must be big if you can't find more or less easily its two prime divisors, EVEN after being said it only has two!
This is the reason why we can have some security when paying, working and having fun with a computer: some codes are based precisely in that (for example, the Public one): you can know the number n, but only the receiver of a message knows its prime divisors.
Just for fun, find the prime divisors of 251646847 (i - this is a product of two primes, ii -don't even dream in trying to find a prime that divides this number by hand, lest you'll get a severe hand-and-brain tiredness)

Tonio

Bruno J. · #3 $Old$ November 4th, 2009, 08:15 AM

If you knew $m$ , then you could just solve the quadratic equation $x^2-mx+n=0$ to get $p$ and $q$ . Solving a quadratic is very easy, so finding $m$ is definitely as difficult as finding the two factors $p$ and $q$ from just $n$ .

Bacterius · #4 $Old$ November 4th, 2009, 12:01 PM

Oh I see. Well ... that's too bad because I was actually trying to avoid factorization

PS : Tonio, 251646847 = 9697 x 25951 on a basic quadratic sieve (no matrix, just the sieving) that I did for fun. But thanks for the info.

But anyway, isn't there a way mathematically to express that a number is square ? Example, if I know that (x² - 84) for example gives a square for 2 values only ? I can find the first one easily (x = 84/4 + 1), but the second one is x = 10 but I can't make an equation to find both solutions cleanly.

Bruno J. · #5 $Old$ November 4th, 2009, 01:04 PM

I can find another integer solution, namely $22^2-84=20^2$ , and infinitely many rational solutions, for example $(19/2)^2-84=(5/2)^2$ .

Bacterius · #6 $Old$ November 4th, 2009, 01:21 PM

Well I knew the 22, since 84/4 + 1 = 22. And I'm only considering perfect squares. There is x = 10 too, since 100 - 84 = 16. But how can I mathematically find the 10 ? (since the 22 is a trivial solution)

Bruno J. · #7 $Old$ November 4th, 2009, 02:22 PM

I wrote $x^2-84=y^2$ , and factored it as $(x-y)(x+y)=84$ . Now if you factor $84$ as $84=AB$ , and set $x-y=A$ , $x+y=B$ , you'll find that $x,y$ are integers if and only if both $A,B$ are even or both are odd. Clearly both cannot be odd, and the only way for both to be even is to have $A=2, B=42$ , or $A=14, B=6$ . If you then solve for $x=(A+B)/2,y=(A-B)/2$ you will find the two solutions $(10,4),(22,20)$ .

Bacterius · #8 $Old$ November 4th, 2009, 02:30 PM

But you still get to factorize 84, so the whole point is lost.
So does this show that factorization is necessary to solve this type of problem ? But factorizing the sum of the two prime factors wouldn't it be easier than factorizing the semiprime itself (since the sum is obviously a lot smaller and even) ? There might be a way around this ?

Bacterius · #9 $Old$ November 5th, 2009, 09:54 PM

Ok I'll try to explain this as well as I can :
I have a function :

$f(x) = x^2 - 4n$

Where $n$ is a known constant.

Is there a "quick" way to find the two distinct values of $x$ when $f(x)$ is a perfect square ?

I can find one easily : if you let $x = (n + 1)$ , then you get :

$f(n + 1) = (n + 1)^2 - 4n$
$f(n + 1) = n^2 + 2n + 1 - 4n$
$f(n + 1) = n^2 - 2n + 1$
$f(n + 1) = (n - 1)^2$

Which obviously is a square. The problem is, this solution is somewhat trivial, and there is only one other solution which is non-trivial and that I need, but I can't find an algebraic way to solve it ...