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

Метод факторизації Ферма – алгоритм факторизації (розкладання на множники) непарного цілого числа 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 };
}