C#. Длинная арифметика. Ро-метод Полларда

Длинная арифметика   21 октября 2013  Автор статьи:  

В данной статье рассмотрим факторизацию на основе Ро-метода Полларда. Разложение большого числа в среднем происходит за n^(1/4), что достаточно быстро. Данный метод не гарантирует, что число будет полностью разложено, но очень часто быстро возвращает результат. Основной идеей p-разложения является построение ряда, который бы сходился к ответу. Так как данный ряд в какой-то момент зациклится, то его можно представить в виде латинской буквы P, где цикл как раз и есть верхняя часть, а первые члены — ножка. Каждый последующий член в классическом алгоритме находится по формуле:
x = x^2 — 1 mod n
Каждый член, который по номеру равен какой-то степени двойки, сохраняется. При этом если НОД разницы члена ряда и сохраненного им числа, которое мы раскладываем, не равен 1 или числу, то мы нашли искомый делитель. Например, если раскладываемое на множители число — n, сохраняемый член ряда — y, а текущий член ряда — x, то мы должны проверить, что
НОД(x-y,n)!=1&&НОД(x-y,n)!=n
Иногда метод Полларда разложения больших чисел зацикливается не находя результата, что часто случается на маленьких числах. Например, n = 4, тогда какой бы не был исходный x, следующий x будет равняться 0, 1 или 3, а это означает, что мы никогда не сможем найти ответ, если y = 0. На самом деле таких примеров достаточно много. Поэтому для использования данного метода проверим не делится ли исходное число на первых сто чисел, после этого же применим метод Полларда. В классических учебниках он представлен как метод нахождения делителей числа, поэтому, чтобы с помощью него разложить число необходимо выполнить дополнительные действия. В нашей программе данной задачей будет заниматься функция Factorization. Внутри нее будет пущен цикл, который будет проверять не разложено ли наше число до простого, и в случае, если не разложено, то искать следующий делитель. После этого делить число на найденный делитель и продолжать свою работу. В случае, если делитель — составное число, необходимо его предварительно разложить. Сам метод Полларда реализован в функции PollardRho и соответствует описанию выше. Единственным отличием от классической реализации является то, что в случае если i достигает какого-то порога, функция возвращает само число, что интерпретируется моим алгоритмом как не удавшаяся попытка и он запускает это число еще раз, пока у него не получится его разложить. Для запуска всего процесса лучше воспользоваться функцией Factorization2, так как она сначала пытается найти маленькие делители числа и только потом запускает Factorization.

public static List Factorization2(BigInteger a)
{
if(IsPrimeMillerRabin(a, 20))
{
return new List() {a};
}
List ans = new List();
BigInteger b = new BigInteger(a.ToString());
for (int i = 2; i < 100; i++) { BigInteger temp = new BigInteger(i.ToString()); if (b.Mod(temp).Equals(BigInteger.Zero)) { ans.AddRange(Factorization2(temp)); b = b.Div(temp); ans.AddRange(Factorization2(b)); return ans; } } return Factorization(a); } public static List Factorization(BigInteger a)
{
List ans = new List();
BigInteger temp = new BigInteger(a.ToString());
while (!IsPrimeMillerRabin(temp, 20))
{
BigInteger temp2 = PollardRho(temp);
if (temp.Equals(temp2))
{
continue;
}
if (IsPrimeMillerRabin(temp2, 20))
{
ans.Add(temp2);
}
else
{
ans.AddRange(Factorization(temp2));
}
temp = temp.Div(temp2);
}
ans.Add(temp);
return ans;
}
private static BigInteger PollardRho(BigInteger n)
{
int i = 1;
BigInteger x = Generate(n.Substract(new BigInteger("2")));
BigInteger y = new BigInteger(x.ToString());
int k = 2;
while (true)
{
i++;
if (i > 10000)
{
return n;
}
x = ((((x.Multiply(x)).Substract(BigInteger.One))).Add(n)).Mod(n);
BigInteger temp = y.Substract(x);
temp.ChangeSign(true);
BigInteger d = GCD(temp, n);
if (!d.Equals(BigInteger.One) && !d.Equals(n))
{
return d;
}
if (i == k)
{
y = x;
k = 2 * k;
}
}
}

Научиться программировать

  • на Delphi

  • на Java

  • на C++