Skip to main content

Dixon's Factorization

In number theory, Dixon's factorization method (also Dixon's random squares method or Dixon's algorithm) is a general-purpose integer factorization algorithm; it is the prototypical factor base method. Unlike for other factor base methods, its run-time bound comes with a rigorous proof that does not rely on conjectures about the smoothness properties of the values taken by polynomial. The algorithm was designed by John D. Dixon, a mathematician at Carleton University, and was published in 1981.


function onlyUnique(value, index, self) {
   return self.indexOf(value) === index;
 }
 
function dixon(n)
{
    //Logic
    var base = [2, 3, 5, 7];
    var start = parseInt(Math.sqrt(n));
    var pairs=[];
    var len= 4;

    for(var i = start; i < n; i++)
    {
      var v=[];
      for(var j = 0; j < len; j++)
      {
        var lhs = parseInt(Math.pow(i,2))% n;
        var rhs = parseInt(Math.pow(base[j],2)) % n;

        if(lhs == rhs)
        {
          v.push(i);
          v.push(base[j]);
          pairs.push(v);
        }
      }
    }

    var newvec = [];
    len = pairs.length;

    for(var i = 0; i < len; i++){
        var factor = stein_gcd(pairs[i][0] - pairs[i][1], n);
        if(factor != 1) newvec.push(factor);
}