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

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

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

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

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

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

${\displaystyle 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
• код програми, що розкладає число на прості множники методом Діксона