Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Any efficient method to find divisors of a number

  1. Oct 25, 2014 #1
    Like if number is too big then normal division is very much tedious task to do
     
  2. jcsd
  3. Oct 26, 2014 #2

    SteamKing

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper

    Which is why calculators and computers were invented.
     
  4. Oct 26, 2014 #3
    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.
     
  5. Oct 26, 2014 #4
    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 [itex]\sqrt N[/itex].
    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 [itex]a^2 \equiv b^2 \left(\mod N\right)[/itex] then [itex]\left(a+b\right)\left(a-b\right) \equiv 0 \left(\mod N\right)[/itex] 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 [itex]a^2 \left(\mod N\right) [/itex] 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 [itex]a^2[/itex]). 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 [itex]a^2 [/itex] 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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Any efficient method to find divisors of a number
Loading...