Алгоритм проверки простоты чисел
Проверка простоты чисел является, вероятно, одной из "тех" жестких проблем в математике. Так, что, лучший и самый быстрый алгоритм, доступный для проверки простоты чисел огромного количества. Самое сырое и самый медленный путь, вероятно:
public static bool IsPrime(int i)
{
for (var x = 2; x < i - 1; i++)
{
if (i % x == 0)
{
return false;
}
}
return true;
}
Недавно я считал, что 768-разрядный алгоритм RSA был взломан с помощью грубой силы, с помощью массива грид-вычислений. Как они выполняют грубую силу на огромном простом числе? Каждый блок обработки поднимает серию числа, учитывает его и проверяет на простоту чисел все число, которое находится в том диапазоне?
6 ответов
Проверьте Promitality Tests на Wikipedia для указателей на текущие алгоритмы
в отношении вашей наивной реализации, отметить, что вы можете сразу же вернуть false, если номер делится К 2, позволяя вам просто проверить нечетные номера. Кроме того, если вы не найдете фактора, где X <= SQRT (I), это Prime. Это потому, что если вы нашли фактор больше, чем SQRT (i), то он должен быть сопряжен с фактором меньше , чем SQRT (I). Так что, если вы не найдете это меньший фактор сначала, вы закончите.
Также есть еще пара трюков, которые вы можете подать заявку на наивный алгоритм, прежде чем вы должны выйти в https://mathoverflow.net/ для справки:)
Это должно быть значительно быстрее:
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;
}
Я полагаю, что есть какой-то распределение рабочей нагрузки, но я сомневаюсь, что они использовали такой простой алгоритм для теста в примат. Может быть, они использовали сито поля или эллиптической кривой Ленстры .
public static bool IsPrime(int i)
{
for (var x = 2; x < (i/2); x++)
{
if (i % x == 0)
{
return false;
}
}
return true;
}
Примациальное тестирование! = Факторизация.
Разбитие определенного открытого ключа RSA и извлечение закрытого ключа требует факторизации.
Процесс построения пары Public / Public / Party RSA включает тестирование в размере. Большинство тестирование в главности, не используемое для факторизации, не дают 100% определенного ответа, а скорее это вероятностное с произвольно высокой вероятностью (более тестовые итерации = более высокая вероятность).
И технически вы можете провести детерминированный тест на главную силу , который быстро и не включает в себя фактически вычисления любых факторов рассматриваемого числа.
Трескание RSA-768 не связано напрямую, не связано с любым алгоритмом проверки примата, скорее, что нужно было алгоритмом факторизации : RSA-768 - это продукт двух очень больших Простые простые пребывания и растрескивание это включает в себя поиск этих простых чисел.
Использованный алгоритм факторизации был ситом номера номеров Lenstra .
Вы можете прочитать полную статью: Факторизация 768-битного модуля RSA .