1
$\begingroup$

Say $N=AB$ where $A$ and $B$ are primes. We write: $$A=a+x,\qquad B=a-x.$$ That is, $$a=\frac{A+B}{2};\qquad x=\frac{A-B}{2};$$ $A$ and $B$ are odd numbers. Therefore $A+B$ and $A-B$ are even. And $a$ and $x$ are integers. $$\begin{align*} AB&=(a+x)(a-x);\\ AB&=a^2-x^2\\ N&=a^2-x^2\\ a^2&=N+x^2 \end{align*}$$

Steps: Find a perfect square number, $K$, greater than $N$ [ie, we have to look out for perfect square numbers only which are greater than $N$].

If $K-N=M$ is a perfect square:

$A=\sqrt{K}+\sqrt{M}$

$B=\sqrt{K}-\sqrt{M}$

[Since $K=a^2$ and $M=x^2$ ; $N=a^2-x^2=K-M$]

$N=A*B$

Example:

Factorization of $1159[=N]$

$1600$ is a perfect square number greater than $1159$

$$\begin{align*} 1600-1159&=441=21^2\\ K&=1600\\ M&=441\\ A&=40+21=61\\ B&=40-21=19\\ N&=61\times 19=1159 \end{align*}$$

Would this process be a convenient one for a composite [of the form $N=A*B$, $A$ and $B$ are primes] that is 400 digits long, if you are allowed to use a microprocessor?

1 Answers 1