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

6

I originally wrote this as a comment, but perhaps should be an answer.

This is a well known method known as Fermat factorization or Difference of Squares factorization. By itself, you could even have Fermat factorization perform worse than trial division (Fermat factorization works best when both prime factors are close to one another, and hence to the square root of $N$; trial division works best when $N$ has a small prime factor).

Combining it judiciously with trial division using a method of Lehman gives an algorithm which is roughtly $O(N^{1/3})$. This is not suitable for factoring RSA-sized composites (there are some $\approx 250$ digit RSA composites that have not been factored yet).

The idea behind Fermat factorization is also part of the insipiration behind the predecessors of the General Number Field Sieve which is the most efficient known algorithm for factoring general numbers.

  • 1
    @AnamitraPalit: I would urge you to familiarize yourself with the literature on the $p$roblem, which is *vast*. Nothing you are saying is new, nothing you are doing is new, nothing you are proposing is *practical*, even with computers, to factor numbers in the 250-digit range. This is *well known*, and simply throwing up ideas as they occur to you, based on not being familiar with the literature, is unlikely to be anything other than a waste of your time (and anybody who tries to implement it).2011-11-26