Быстрое тестирование на простоту для больших n в 1000 * - PullRequest
Новая
       24

Быстрое тестирование на простоту для больших n в 1000 *

0 голосов
/ 01 мая 2020

Я работаю над проектом, который требует от меня выяснить, являются ли чрезвычайно большие числа простыми числами или нет. Конечно, я читал, как найти простые числа, и предложил очень простой метод грубой силы: 

def is_prime_brute_force(p):
    if p == 2 or p == 3:
        return true
    if p == 1 or p % 2 == 0 or any(p % i == 0 for i in range(3, floor_sqrt(p), 2)):
        return false
    return true

Я также исследовал такие вероятностные c методы, как Миллер -Rabin Primality Test и маленькая теорема Ферма (см. здесь для реализации первого кода Розетты).

Хотя параметры вероятности c на порядок быстрее, чем грубые сила, они все еще очень медленные для очень больших входных данных n (например, известное простое число 10**9999 + 33603).

Я столкнулся с интересным наблюдением (конечно, я не первый, кто сталкивался с таким наблюдением), что все простые числа соответствуют уравнению p = 6 * k + 1 или p = 6 * k -1. В Python такая функция выглядит следующим образом 

def is_prime_eq(p):
    if p == 2 or p == 3:
        return True
    if p == 0 or p == 1:
        return False

    # The same as `return (p % 6 == 1) or (p % 6 == 5)`
    prime_test = lambda p, a, m : (p % a == m) or (p % a == (a-m))
    return prime_test(p, 6, 1)

Выше гарантировано вернет true, если p - простое число, но истинный результат не означает, что p - простое число. Простой пример - 25 (25 = 1 (мод 6), но явно 25 = 5 ^ 2).

Мне интересно, есть ли более общий способ применить это интересное свойство простых чисел, возможно, с другим значения a для улучшения скорости моей функции is_prime.

Ответы [ 2 ]

1 голос
/ 01 мая 2020

На math.stackexchange ( здесь ) было размещено довольно полезное решение, которое я отразил ниже

В отношении этого алгоритма, ваш предложенный "более быстрый" алгоритм эквивалентно 

def is_prime_brute_force(p):
    if p == 2 or p == 3:
        return true
    if p == 1 or p % 2 == 0 or p % 3 == 0:
        return false
    return true

Надеюсь, вы понимаете, почему это не очень полезно. Любой композит, который является продуктом простых чисел >= 5, будет оцениваться как простое число. Обычно мы используем вероятностные c тесты простоты (например, Миллера-Рабина) для чисел, все простые делители которых достаточно велики, поэтому игнорирование всех простых делителей больше 3 делает его довольно бесполезным.

Тесты на простоту по своей природе довольно дороги на современном оборудовании. Лучшее, что вы можете сделать, - это попытаться оптимизировать некоторые предположения на входе.

1 голос
/ 01 мая 2020

Просто используйте вероятностный c тест. Вероятностные c тесты - это современный уровень тестирования простоты, намного более быстрый, чем любой детерминированный c тест, и для изобретения чего-либо более быстрого потребуется теоретический опыт мирового класса.

gmpy2, вероятно, ваш лучший вариант в Python. Он имеет встроенную поддержку для множественных вероятностных c тестов простоты и других функций теории чисел, а также собственный тип int произвольной точности, оптимизированный для гораздо более быстрых операций с большими значениями.

...