Метод факторизации Ферма

Метод факторизации Ферма – алгоритм факторизации (разложения на множители) нечётного целого числа n, предложенный Пьером Ферма.

Метод основан на поиске таких целых чисел a и b, которые удовлетворяют соотношению a² – b² = n, что ведёт к разложению n = (a – b)⋅(a + b).

Описание алгоритма

Для разложения на множители нечетного числа n необходимо найти пару чисел a и b, для которых выполняется соотношение a² – b² = n. Соответственно выполняется и (a – b)⋅(a + b) = n, при этом числа (a – b) и (a + b) являются искомыми множителями.

Равенство a² – b² = n равносильно a² – n = b².

В цикле производиться поиск a, при котором b = √(a² – n) целое число.

Реализация алгоритма

static ulong[] FermatFactor(ulong n)
{
    ulong a, b;

    //если число четное, возвращаем результат
    if ((n % 2UL) == 0)
    {
        return new[] { 2UL, n / 2UL };
    }

    a = Convert.ToUInt64(Math.Ceiling(Math.Sqrt(n)));
    if (a * a == n)
    {
        return new[] { a, a };
    }

    while (true)
    {
        ulong tmp = a * a - n;
        b = Convert.ToUInt64(Math.Sqrt(tmp));

        if (b * b == tmp)
        {
            break;
        }

        a++;
    }

    return new[] { a - b, a + b };
}