Any efficient method to find divisors of a number

[Rishav sapahi]

Like if number is too big then normal division is very much tedious task to do

 

[SteamKing]

Like if number is too big then normal division is very much tedious task to do

Which is why calculators and computers were invented.

 

[Rishav sapahi]

Which is why calculators and computers were invented.

I am asking about the algorithm on which they works as I have come across an algorithm on fundamental theorem of arithmetic but it was not so much clear.

 

[Boorglar]

The simplest (but of course the slowest) is trial division. This can be done by checking the divisibility of N by all primes up to \sqrt N.
This is an exponential time algorithm (exponential in the number of bits).

There are faster algorithms based on Fermat's idea to find two perfect squares modulo N. If you have found that a^2 \equiv b^2 \left(\mod N\right) then \left(a+b\right)\left(a-b\right) \equiv 0 \left(\mod N\right) and this leads usually to a non trivial factorization of N by finding the gcd of (a+b), N and (a-b), N.

Most of the fast (as in subexponential, but still superpolynomial time) algorithms are based on Fermat's method, and differ on the method of finding the congruence of squares. The simplest is Dixon's Factorization method (see http://en.wikipedia.org/wiki/Dixon's_factorization_method). It looks for numbers such that a^2 \left(\mod N\right) is the product of small prime factors (called smooth numbers). When enough such numbers have been found, it is possible to find a subset of these numbers whose product is a perfect square (which is different that a^2). This gives a congruence of squares.

The Quadratic Sieve is an optimization of Dixon's factorization method which uses sieving in order to speed up the process of finding numbers such that a^2 is smooth modulo N. See http://en.wikipedia.org/wiki/Quadratic_sieve for more details.

Finally, the fastest currently known algorithm for factoring large integers is the General Number Field sieve (http://en.wikipedia.org/wiki/General_number_field_sieve). This one is complicated because it deals with different algebraic structures (called "number fields") and looks for factorizations in these fields instead. This turns out to be faster, and using correspondences between the integers and these number fields, we can obtain a factorization in the integers. I honestly don't know how this works though...

Wikipedia has a list of many factorization algorithms, some of which work only for numbers of special form (and are thus faster in these specific cases):
http://en.wikipedia.org/wiki/Integer_factorization