Метод факторизації Діксона

Метод факторизації Діксона(або алгоритм Діксона) є універсальним алгоритмом факторизації. Метод заснований на багаторазовому виділенні з числа його множника. Складність алгоритму не залежить від кількості його простих множників. Алгоритм був створений Джоном Діксоном, математиком Карлетонського університету, і був опублікований в 1981 році.

Складність алгоритму

При оптимальній реалізації складність алгоритму, як показано в [1] становить:

$O\left(\exp\left(2 \sqrt 2 \sqrt{\log n \log \log n}\right)\right)$

в Нотації Ландау, або

$L_n [1/2, 2 \sqrt 2]$

В L-нотації.

Реалізація мовою С++

C++ функція, що знаходить множник числа методом Діксона:

int factor(int n) 
{
   int x, xx, y, d, q, rt;
   int i, j;
   rt = sqrt(double(n));
   if (issquare(n)) 
       return rt;
   x = rt;
   while(x++) 
   {
       d = gcd(x, n);
       if (1<d && d<n) 
          return d;
       xx = (x*x)%n;
       if(issquare(xx)) 
       {
          y = sqrt(double(xx));
          q = (x-y)%n;
          d = gcd(q, n);
          if(1<d && d<n) 
             return d;  
       }
   }
   return 0;
}

Джерела

• J. D. Dixon, "Asymptotically fast factorization of integers," Math. Comput., 36(1981), p. 255-260.
• код програми, що розкладає число на прості множники методом Діксона.
• Використано матеріали зі статті в англійській Вікіпедії.