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

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

Заканчивать primality tests на Wikipedia для указателей на текущие алгоритмы

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

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

Answer 2

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

Answer 3

Я предполагаю, что есть какое-то распределение нагрузки, но я сомневаюсь, что они использовали такие простой алгоритм теста прочности. Возможно, они использовали number field sieve или Lenstra's elliptic curve factorization.

Answer 4

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

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 5

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

Используемый алгоритм факторизации был Ленстра Number Field Sieve.

Здесь вы можете прочитать полную статью: Factorization of a 768-bit RSA modulus.

Answer 6

Первоначальное тестирование! = Факторизация.

Нарушение конкретного открытого ключа RSA и получение секретного ключа требует факторизации.

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

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

Answer 7

Предлагаю использовать Fermat's Little Theorem. Значение 'х' первична если ((а^(х-1))% х) == 1.Где «а» любое число и «х» не равен 1, 0 или 2.