How to factor numbers that are the product of two primes

What are techniques to factor numbers that are the product of two prime numbers? For example, how would we factor $262417$ to get $397\cdot 661$? Would we have to guess that factorization or is there an easier way?

Solutions Collecting From Web of "How to factor numbers that are the product of two primes"

The problem of the factorization is the main property of some cryptograpic systems as RSA.

This fact has been studied for years and nowadays we don’t know a algorithm to factorize a big arbitrary number efficiently.

However, if $p*q$ satisfies some propierties (e.g $p-1$ or $q-1$ have a soft factorization (that means the number factorizes in primes $p$ such that $p \leq \sqrt{n}$)), you can factorize the number in a computational time of $O(log(n))$ (or another low comptutational time)

If you are interested in it, you can check this pdf with some famous attacks to the security of RSA related with the fact of factorization of large numbers.

There is an easier way. The length of prime numbers is not a problem – it is the randomness that lies within.

Let $n=262417$

$397 + 661 = 1058$

$1058 / 2 = 529 = d$

$d^2 = 279841 = a$

Let $s = a – n$

$s = 279841 – 262417 = 17424$ (this square defines distance between $p$ and $q$)

$\sqrt{s} = 132 = t$

$n = p \cdot q$

$n = (d + t)(d – t)$

$n = (529 + 132)(529 – 132) = 661 \cdot 397 = 262417$

To find $s$ you need to know pattern in prime numbers, which will also help you structure semiprime $n$ – “an almost beautiful” arithmetic progression.