Алгоритм проверки первичности

Question

Проверка первичности, вероятно, является одной из "тех" сложных проблем математики. Итак, что является лучшим и самым быстрым алгоритмом, доступным для проверки простоты огромного числа. Наиболее грубый и самый медленный путь, вероятно, таков:

public static bool IsPrime(int i)
{
    for (var x = 2; x < i - 1; i++)
    {
         if (i % x == 0)
         {
             return false;
         }
    }
    return true;
}

Недавно я прочитал, что 768-битный алгоритм RSA был взломан с использованием грубой силы с использованием массива вычислительных сеток. Как они выполняют грубую силу на огромном простом числе? Каждый блок обработки обрабатывает последовательность чисел, вычисляет ее и проверяет на простоту все числа, которые лежат в этом диапазоне?

Answer 1

Проверьте тесты простоты в Википедии для указателей на текущие алгоритмы

Что касается вашей наивной реализации, обратите внимание, что вы можете немедленно вернуть false, если число делится на 2, что позволяет просто проверять нечетные числа. Кроме того, если вы не найдете фактор, где x <= sqrt (i), он прост. Это потому, что если вы нашли фактор, больший, чем sqrt (i), то он должен быть в паре с коэффициентом <em>меньшим , чем sqrt (i). Поэтому, если вы сначала не найдете этот меньший фактор, все готово.

Есть также еще пара трюков, которые вы можете применить к наивному алгоритму, прежде чем отправиться на помощь к https://mathoverflow.net/ за помощью:)

Answer 2

Взлом RSA-768 напрямую не включал какой-либо алгоритм проверки простоты, скорее, был необходим алгоритм факторизации : RSA-768 является продуктом двух очень больших простых чисел, а взлом включает поиск этих простых чисел. .

Использовался алгоритм факторизации Числовое поле * Ленстры .

Вы можете прочитать полную статью здесь: Факторизация 768-битного модуля RSA .

Answer 3

Это должно быть немного быстрее:

public static bool IsPrime(int i) {        
    // only go up to the root of i 
    // +1 to be save from floating point rounding errors, ceil should work too.
    var max = sqrt(i) + 1;

    // skip numbers dividable by 2, except 2 itself
    if (i == 2) return true;
    if (i % 2 == 0) return false;
    for (var x = 3; x < max; x+=2)  {
         if (i % x == 0)  {
             return false;
         }
    }
    return true;
}

Answer 4

Я предполагаю, что есть какое-то распределение рабочей нагрузки, но я сомневаюсь, что они использовали такой простой алгоритм для теста на простоту. Возможно, они использовали числовое сито или Ленстра с эллиптической кривой факторизации .

Answer 5

Тестирование первичности! = Факторизация.

Для взлома конкретного открытого ключа RSA и извлечения закрытого ключа требуется факторизация.

Процесс создания пары открытых / закрытых ключей RSA включает тестирование на простоту. Большинство тестов простоты, не используемых для факторизации, не дают 100% -ного определенного ответа, а скорее это вероятностный с произвольно высокой вероятностью (больше итераций теста = более высокая вероятность).

И технически у вас может быть детерминированный тест на простоту , который является быстрым и не требует фактического вычисления каких-либо факторов рассматриваемого числа.

Answer 6

Предлагаю использовать Маленькая теорема Ферма . Значение 'x' является простым if ((a ^ (x-1))% x) == 1 . Где 'a' - любое число и 'x', не равное 1, 0 или 2 .

Answer 7

public static bool IsPrime(int i)
{
    for (var x = 2; x < (i/2); x++)
    {
         if (i % x == 0)
         {
             return false;
         }
    }
    return true;
}