Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

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.

share|improve this answer
    
Regarding the trial method:A deselection method could prove useful.We simply exclude divisors which are composite in nature. This can save the trouble of dividing the composite[N=A*B] by long numbers. This procedure may be combined with Fermat's method.I am not sure whether they do it in this way in the combination technique. –  Anamitra Palit Nov 26 '11 at 2:59
1  
@AnamitraPalit: The method has been studied extensively, and it is simply not practical for large numbers. There are plenty of modern ideas to speed it up, and they have already been incorporated into the General Number Field Sieve. Your idea (Fermat's idea) is 400 years behind the times. Excluding composites is already worked into Lehman's method. You are not saving that much time, comparatively speaking, and the method is just not good enough for even 200 digit numbers, let alone 400 digit numbers. You are going over well-trod ground, 400 years too late. –  Arturo Magidin Nov 26 '11 at 3:01
    
We take the same composite number, N=AB,where a,b are primes. (N-p)/p=m is calculated [p is taken to be a prime number] If m is an integer the job is done!If m is an integer it will be even[since N-p=mp,N-p is even and p is prime]. This method might prove computer friendly if the prime factors are far apart from $\sqrt{N}$.Since N-p<N the process of division will involve a smaller number of loops –  Anamitra Palit Nov 26 '11 at 5:10
1  
@AnamitraPalit: I would urge you to familiarize yourself with the literature on the problem, 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). –  Arturo Magidin Nov 26 '11 at 5:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.