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

"Я хочу, чтобы меня услышали в России. Абсолютно все. Тысячи жертв, сотни пленных, которые просто не могут понять ради чего их отправили в Украину.
Отправили в Украину умирать. Убивать других. Чем скорее вы скажете своей власти, что войну нужно немедленно остановить – тем больше ваших людей останутся живыми.
Мы видим, что действительно есть выступления ваших граждан против войны. И мы знаем, что многие в России сейчас просто шокированы подлостью и жестокостью власти. И это очень правильная реакция. Я благодарю вас за эту реакцию! Спасибо Леониду Парфёнову, Дмитрию Муратову, Юрию Дудю, Лие Ахеджаковой, Валерию Меладзе – ну, и тысячам. Тысячам достойных других россиян, чья совесть звучит – звучит громко.
Просто остановите тех, кто лжет вам. Лжет нам. Лжет всему миру.
Нужно закончить эту войну. Мы можем жить в мире. В мире глобальном. В мире человечества".

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

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

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

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

Равенство a2 – b2 = n равносильно a2 – n = b2.

В цикле производиться поиск a, при котором b = √(a2 – 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 };
}

Смотрите также: