Тест бейли померанца селфриджа уогстаффа

Тест бейли померанца селфриджа уогстаффа

Введение

Алгоритм BPSW — это тест числа на простоту. Этот алгоритм назван по фамилиям его изобретателей: Роберт Бэйли (Ballie), Карл Померанс (Pomerance), Джон Селфридж (Selfridge), Сэмюэль Вагстафф (Wagstaff). Алгоритм был предложен в 1980 году. На сегодняшний день к алгоритму не было найдено ни одного контрпримера, равно как и не было найдено доказательство.

Алгоритм BPSW был проверен на всех числах до 10 15 . Кроме того, контрпример пытались найти с помощью программы PRIMO (см. [6]), основанной на тесте на простоту с помощью эллиптических кривых. Программа, проработав три года, не нашла ни одного контрпримера, на основании чего Мартин предположил, что не существует ни одного BPSW-псевдопростого, меньшего 10 10000 (псевдопростое число — составное число, на котором алгоритм даёт результат "простое"). В то же время, Карл Померанс в 1984 году представил эвристическое доказательство того, что существует бесконечное множество BPSW-псевдопростых чисел.

Сложность алгоритма BPSW есть O (log 3 (N)) битовых операций. Если же сравнивать алгоритм BPSW с другими тестами, например, тестом Миллера-Рабина, то алгоритм BPSW обычно оказывается в 3-7 раз медленнее.

Алгоритм нередко применяется на практике. По-видимому, многие коммерческие математические пакеты, полностью или частично, полагаются на алгоритм BPSW для проверки чисел на простоту.

Краткое описание

Алгоритм имеет несколько различных реализаций, отличающихся друг от друга только деталями. В нашем случае алгоритм имеет вид:

1. Выполнить тест Миллера-Рабина по основанию 2.

2. Выполнить сильный тест Лукаса-Селфриджа, используя последовательности Лукаса с параметрами Селфриджа.

3. Вернуть "простое" только в том случае, когда оба теста вернули "простое".

+0. Кроме того, в начало алгоритма можно добавить проверку на тривиальные делители, скажем, до 1000. Это позволит увеличить скорость работы на составных числах, правда, несколько замедлив алгоритм на простых.

Итак, алгоритм BPSW основывается на следующем:

1. (факт) тест Миллера-Рабина и тест Лукаса-Селфриджа если и ошибаются, то только в одну сторону: некоторые составные числа этими алгоритмами опознаются как простые. В обратную сторону эти алгоритмы не ошибаются никогда.

2. (предположение) тест Миллера-Рабина и тест Лукаса-Селфриджа если и ошибаются, то никогда не ошибаются на одном числе одновременно.

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

Реализация алгоритмов в данной статье

Все алгоритмы в данной статье будут реализованы на C++. Все программы тестировались только на компиляторе Microsoft C++ 8.0 SP1 (2005), также должны компилироваться на g++.

Алгоритмы реализованы с использованием шаблонов (templates), что позволяет применять их как к встроенным числовым типам, так и собственным классам, реализующим длинную арифметику. [ пока длинная арифметика в статью не входит — TODO ]

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

Тест Миллера-Рабина

Я не буду заострять внимание на тесте Миллера-Рабина, поскольку он описывается во многих источниках, в том числе и на русском языке (например. см. [5]).

Замечу лишь, что скорость его работы есть O (log 3 (N)) битовых операций и приведу готовую реализацию этого алгоритма:

Сильный тест Лукаса-Селфриджа

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

Алгоритм Селфриджа

Среди последовательности 5, -7, 9, -11, 13, . найти первое число D, для которого J (D, N) = -1 и gcd (D, N) = 1, где J(x,y) — символ Якоби.

Параметрами Селфриджа будут P = 1 и Q = (1 — D) / 4.

Следует заметить, что параметр Селфриджа не существует для чисел, которые являются точными квадратами. Действительно, если число является точным квадратом, то перебор D дойдёт до sqrt(N), на котором окажется, что gcd (D, N) > 1, т.е. обнаружится, что число N составное.

Кроме того, параметры Селфриджа будут вычислены неправильно для чётных чисел и для единицы; впрочем, проверка этих случаев не составит труда.

Таким образом, перед началом алгоритма следует проверить, что число N является нечётным, большим 2, и не является точным квадратом, иначе (при невыполнении хотя бы одного условия) нужно сразу выйти из алгоритма с результатом "составное".

Наконец, заметим, что если D для некоторого числа N окажется слишком большим, то алгоритм с вычислительной точки зрения окажется неприменимым. Хотя на практике такого замечено не было (оказывалось вполне достаточно 4-байтного числа), тем не менее вероятность этого события не следует исключать. Впрочем, например, на отрезке [1; 10 6 ] max(D) = 47, а на отрезке [10 19 ; 10 19 +10 6 ] max(D) = 67. Кроме того, Бэйли и Вагстаф в 1980 году аналитически доказали это наблюдение (см. Ribenboim, 1995/96, стр. 142).

Сильный алгоритм Лукаса

Параметрами алгоритма Лукаса являются числа D, P и Q такие, что D = P 2 — 4*Q ? 0, и P > 0.

(нетрудно заметить, что параметры, вычисленные по алгоритму Селфриджа, удовлетворяют этим условиям)

Последовательности Лукаса — это последовательности Uk и Vk, определяемые следующим образом:

Далее, пусть M = N — J (D, N).

Если N простое, и gcd (N, Q) = 1, то имеем:

В частности, когда параметры D, P, Q вычислены алгоритмом Селфриджа, имеем:

Обратное, вообще говоря, неверно. Тем не менее, псевдопростых чисел при данном алгоритме оказывается не очень много, на чём, собственно, и основывается алгоритм Лукаса.

Итак, алгоритм Лукаса заключается в вычислении UM и сравнении его с нулём.

Далее, необходимо найти какой-то способ ускорения вычисления UK, иначе, понятно, никакого практического смысла в этом алгоритма не было бы.

где a и b — различные корни квадратного уравнения x 2 — P x + Q = 0.

Теперь следующие равенства можно доказать элементарно:

Теперь, если представить M = E 2 T , где E — нечётное число, то легко получить:

и хотя бы один из множителей равен нулю по модулю N.

Понятно, что достаточно вычислить UE и VE, а все последующие множители V2E V4E . V2 T-2 E V2 T-1 E можно получить уже из них.

Таким образом, осталось научиться быстро вычислять UE и VE для нечётного E.

Сначала рассмотрим следующие формулы для сложения членов последовательностей Лукаса:

Следует обратить внимание, что деление выполняется в поле (mod N).

Формулы эти доказываются очень просто, и здесь их доказательство опущено.

Теперь, обладая формулами для сложения и для удвоения членов последовательностей Лукаса, понятен и способ ускорения вычисления UE и VE.

Действительно, рассмотрим двоичную запись числа E. Положим сначала результат — UE и VE — равными, соответственно, U1 и V1. Пройдёмся по всем битам числа E от более младших к более старшим, пропустив только самый первый бит (начальный член последовательности). Для каждого i-го бита будем вычислять U2 i и V2 i из предыдущих членов с помощью формул удвоения. Кроме того, если текущий i-ый бит равен единице, то к ответу будем прибавлять текущие U2 i и V2 i с помощью формул сложения. По окончании алгоритма, выполняющегося за O (log(E)), мы получим искомые UE и VE.

Если UE или VE оказались равными нулю (mod N), то число N простое (или псевдопростое). Если они оба отличны от нуля, то вычисляем V2E, V4E, . V2 T-2 E, V2 T-1 E. Если хотя бы один из них сравним с нулём по модулю N, то число N простое (или псевдопростое). Иначе число N составное.

Обсуждение алгоритма Селфриджа

Теперь, когда мы рассмотрели алгоритм Лукаса, можно более подробно остановиться на его параметрах D,P,Q, одним из способов получения которых и является алгоритм Селфриджа.

Напомним базовые требования к параметрам:

Теперь продолжим изучение этих параметров.

D не должно быть точным квадратом (mod N).

Действительно, иначе получим:

D = b 2 , отсюда J(D,N) = 1, P = b + 2, Q = b + 1, отсюда Un-1 = (Q n-1 — 1) / (Q — 1).

Т.е. если D — точный квадрат, то алгоритм Лукаса становится практически обычным вероятностным тестом.

Один из лучших способов избежать подобного — потребовать, чтобы J(D,N) = -1.

Например, можно выбрать первое число D из последовательности 5, -7, 9, -11, 13, . для которого J(D,N) = -1. Также пусть P = 1. Тогда Q = (1 — D) / 4. Этот способ был предложен Селфриджем.

Впрочем, имеются и другие способы выбора D. Можно выбирать его из последовательности 5, 9, 13, 17, 21, . Также пусть P — наименьшее нечётное, привосходящее sqrt(D). Тогда Q = (P 2 — D) / 4.

Понятно, что от выбора конкретного способа вычисления параметров Лукаса зависит и его результат — псевдопростые могут отличаться при различных способах выбора параметра. Как показала практика, алгоритм, предложенный Селфриджем, оказался очень удачным: все псевдопростые Лукаса-Селфриджа не являются псевдопростыми Миллера-Рабина, по крайней мере, ни одного контрпримера найдено не было.

Реализация сильного алгоритма Лукаса-Селфриджа

Теперь осталось только реализовать алгоритм:

Код BPSW

Теперь осталось просто скомбинировать результаты всех 3 тестов: проверка на небольшие тривиальные делители, тест Миллера-Рабина, сильный тест Лукаса-Селфриджа.

Отсюда можно скачать программу (исходник + exe), содержащую полную реализацию теста BPSW. [77 КБ]

Краткая реализация

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

Эвристическое доказательство-опровержение Померанса

Померанс в 1984 году предложил следующее эвристическое доказательство.

Утверждение: Количество BPSW-псевдопростых от 1 до X больше X 1-a для любого a > 0.

Пусть k > 4 — произвольное, но фиксированное число. Пусть T — некоторое большое число.

Пусть Pk(T) — множество таких простых p в интервале [T; T k ], для которых:

Читайте также:  Logitech hid compliant cordless mouse драйвер

(1) p = 3 (mod 8), J(5,p) = -1

(2) число (p-1)/2 не является точным квадратом

(3) число (p-1)/2 составлено исключительно из простых q k ] удовлетворяет условию (1). Также можно показать, что условия (2) и (5) сохраняют некоторую часть чисел. Эвристически, условия (3) и (6) также позволяют нам оставить некоторую часть чисел из отрезка (T; T k ). Наконец, событие (4) обладает вероятностью (c (log T) -1/2 ), так же как и событие (7). Таким образом, мощность множества Pk(T) прблизительно равна при T -> oo

где c — некоторая положительная константа, зависящая от выбора k.

Теперь мы можем построить число n, не являющееся точным квадратом, составленное из l простых из Pk(T), где l нечётно и меньше T 2 / log(T k ). Количество способов выбрать такое число n есть примерно

для большого T и фиксированного k. Кроме того, каждое такое число n меньше e T 2 .

Обозначим через Q1 произведение простых q T . Таким образом, количество способов выбрать n с дополнительными условиями

должно быть, эвристически, как минимум

Но каждое такое n — это контрпример к тесту BPSW. Действительно, n будет числом Кармайкла (т.е. числом, на котором тест Миллера-Рабина будет ошибаться при любом основании), поэтому оно автоматически будет псевдопростым по основанию 2. Поскольку n = 3 (mod 8) и каждое p | n равно 3 (mod 8), очевидно, что n также будет сильным псевдопростым по основанию 2. Поскольку J(5,n) = -1, то каждое простое p | n удовлетворяет J(5,p) = -1, и так как p+1 | n+1 для любого простого p | n, отсюда следует, что n — псевдопростое Лукаса для любого теста Лукаса с дискриминантом 5.

Таким образом, мы показали, что для любого фиксированного k и всех больших T, будет как минимум e T 2 (1 — 4 / k) контрпримеров к тесту BPSW среди чисел, меньших e T 2 . Теперь, если мы положим x = e T 2 , будет как минимум x 1 — 4 / k контрпримеров, меньших x. Поскольку k — случайное число, то наше доказательство означает, что количество контрпримеров, меньших x, есть число, большее x 1-a для любого a > 0.

Практические испытания теста BPSW

В этом разделе будут рассмотрены результаты, полученные мной в результате тестирования моей реализации теста BPSW. Все испытания проводились на встроенном типе — 64-битном числе long long. Длинная арифметика не тестировалась.

Тестирования проводились на компьютере с процессором Celeron 1.3 GHz.

Все времена даны в микросекундах (10 -6 сек).

Среднее время работы на отрезке чисел в зависимости от предела тривиального перебора

Имеется в виду параметр, передаваемый функции prime_div_trivial(), который в коде выше равен 29.

Скачать тестовую программу (исходник и exe-файл). [83 КБ]

Если запускать тест на всех нечетных числах из отрезка, то результаты получаются такими:

начало
отрезка
конец
отрезка
предел >
перебора >
10 2 10 3 10 4 10 5
1 10 5 8.1 4.5 0.7 0.7 0.9
10 6 10 6 +10 5 12.8 6.8 7.0 1.6 1.6
10 9 10 9 +10 5 28.4 12.6 12.1 17.0 17.1
10 12 10 12 +10 5 41.5 16.5 15.3 19.4 54.4
10 15 10 15 +10 5 66.7 24.4 21.1 24.8 58.9

Если запускать тест только на простых числах из отрезка, то скорость работы такова:

начало
отрезка
конец
отрезка
предел >
перебора >
10 2 10 3 10 4 10 5
1 10 5 42.9 40.8 3.1 4.2 4.2
10 6 10 6 +10 5 75.0 76.4 88.8 13.9 15.2
10 9 10 9 +10 5 186.5 188.5 201.0 294.3 283.9
10 12 10 12 +10 5 288.3 288.3 302.2 387.9 1069.5
10 15 10 15 +10 5 485.6 489.1 496.3 585.4 1267.4

Таким образом, оптимально выбирать предел тривиального перебора равным 100 или 1000.

Для всех следующих тестов я выбрал предел 1000.

Среднее время работы на отрезке чисел

Теперь, когда мы выбрали предел тривиального перебора, можно более точно протестировать скорость работы на различных отрезках.

Скачать тестовую программу (исходник и exe-файл). [83 КБ]

начало
отрезка
конец
отрезка
время работы
на нечетных числах
время работы
на простых числах
1 10 5 1.2 4.2
10 6 10 6 +10 5 13.8 88.8
10 7 10 7 +10 5 16.8 115.5
10 8 10 8 +10 5 21.2 164.8
10 9 10 9 +10 5 24.0 201.0
10 10 10 10 +10 5 25.2 225.5
10 11 10 11 +10 5 28.4 266.5
10 12 10 12 +10 5 30.4 302.2
10 13 10 13 +10 5 33.0 352.2
10 14 10 14 +10 5 37.5 424.3
10 15 10 15 +10 5 42.3 499.8
10 16 10 15 +10 5 46.5 553.6
10 17 10 15 +10 5 48.9 621.1

Или, в виде графика, приблизительное время работы теста BPSW на одном числе:

То есть мы получили, что на практике, на небольших числах (до 10 17 ), алгоритм работает за O (log N). Это объясняется тем, что для встроенного типа int64 операция деления выполняется за O(1), т.е. сложность деления не зависисит от количества битов в числе.

Если же применить тест BPSW к длинной арифметике, то ожидается, что он будет работать как раз за O (log 3 (N)). [ TODO ]

Приложение. Все программы

Скачать все программы из данной статьи. [242 КБ]

Литература

Использованная мной литература, полностью доступная в Интернете:

  1. Robert Baillie; Samuel S. Wagstaff
    Lucas pseudoprimes
    Math. Comp. 35 (1980) 1391-1417
    mpqs.free.fr/LucasPseudoprimes.pdf
  2. Daniel J. Bernstein
    Distinguishing prime numbers from composite numbers: the state of the art in 2004
    Math. Comp. (2004)
    cr.yp.to/primetests/prime2004-20041223.pdf
  3. Richard P. Brent
    Primality Testing and Integer Factorisation
    The Role of Mathematics in Science (1990)
    wwwmaths.anu.edu.au/

Список других рекомендуемых книг, которых мне не удалось найти в Интернете:

  1. Zhaiyu Mo; James P. Jones
    A new primality test using Lucas sequences
    Preprint (1997)
  2. Hans Riesel
    Prime numbers and computer methods for factorization
    Boston: Birkhauser (1994)

Profile

Comments 474

Bookmarks 1.4k

Лично моё имхо — весь секрет в том, что каждый должен заниматься своим делом.

Всегда с теплотой вспоминаю прошлую работу —

  • Митинги только по нужным поводам, никаких ежедневных «прогрессных» кроме пяти минут с утра за чаем — болтать, как говорится, не работу ворочать
  • Документацию пишут те, у кого лучше всего получается писать именно для людей, а не компьютеров. Выделяется часок-другой и они подробно расспрашивают разраба, как же это работает. При этом документация становится куда понятнее, так как если бы мне сказали описать алгоритм, то я бы написал, что пепяка ударяет в мемяку, из той вылетает два реквеста и один электрон, файл сохранился, завтрак испортился. Но тех, кто пишет документацию, такой ответ не устроит, и они обязательно спросят те вещи, которые за время работы стали для меня уже очевидными — какая именно пепяка ударяет в какое место мемяки, куда улетает запрос и т.д.
  • То же самое с ручным тестированием — им занимаются не разрабы. Поскольку я уже запомнил, что если нажать на «Б» раньше чем на «А», то прога с какой-то вероятностью вылетает, и подсознательно уже так не делаю, ибо «ну потом поправлю». А тестировщики об этом не в курсе и в процессе документирования обязательно так сделают, и повесят мне задачу этот косяк исправить, чтобы точно не забыл.
  • Нормальный график и периодическая удалёнка. Серьёзно, попробовав на новом месте фуллтайм, понял, что это неплохой такой способ к существованию, но жить так нельзя. На старом месте вполне можно было прийти часов в 11-12 и уйти хоть в полпервого ночи, лишь бы работа была сделана.
  • Явная видимость состояния проекта. Все задачи как на ладони, видишь, всё ли ты сделал и приняли ли это. На новом месте даже трекер спрятан ибо «ну он на сервере заказчика, поэтому только у ПМа есть доступ к нему». Щито.
  • Никакого принудительного общения. Пришёл в офис, тебя никто донимать не будет, если ты занят, чтобы не вырывать из потока. Сидишь на удалёнке — если ничего экстренного, то не будут названивать в телефон, а черканут в чатике.

В итоге каждый занимался именно своим делом, задачи решались в срок, всё жило и цвело.
А новое место, конечно, «энтерпрайз корпорейт вери биг кампани», но по ощущениям большая часть людей и занимается именно что болтовнёй. При этом тесты все делаются в экселе, и их как и доки пишут те же, кто и код. Добавляем их природную безалаберность и итог немного предсказуем, в доках без бутылки не разберёшься, вплоть до того что в enum’ах в доках вместо подчёркиваний местами ПРОБЕЛЫ.

Tl;dr: работу надо работать, а не оптимизацией болтовни заниматься.

> Проведём маленький эксперимент, если Вы не против — мне любопытно чего такого я не знаю на фундаментальном уровне, из того, что преподают в ВУЗах в качестве базы.

Ну я вот писал программу по нескольким курсам, один из основных — «Алгоритмы и структуры данных», вот база (не все, особенно и последнего семестра, нужно знать и доказывать, но основные свойства полезно знать).

Вот примерный список, я надеюсь, он после обкатки скорректируется. Общий объем 225 часов (чисто лекции, практика Python-C-C++ идет отдельными часами).

Поиск в массиве
1.1 Линейный поиск
1.2 Двоичный поиск
1.3 Троичный поиск
1.4 Интерполяционный поиск
Структуры данных
1.5 Массив
1.6 Стек
1.7 Очередь, двусторонняя очередь
1.8 Словарь
1.9 Хеш-таблица

Читайте также:  Starline online ru личный кабинет регистрация

Сортировки, анализ алгоритмов
2.1 Bubble sort (пузырьковая сортировка)
2.2 Merge sort (сортировка слиянием)
2.3 Quick sort (быстрая сортировка)
2.4 Bucket sort (блочная сортировка)
2.5 Heap sort (пирамидальная сортировка)
2.6 Insertion sort (сортировка вставками)
2.7 Counting sort (сортировка подсчетом)
2.8 Radix sort (порязрядная сортировка)
2.9 Timsort и другие гибридные алгоритмы сортировки

Рекурсия, математическая индукция
3.1 Хвостовая рекурсия
3.2 Обратная польская запись
3.3 Числа Каталана
3.4 Вычисление биномиальных коэффициентов
3.5 Метод градиентного спуска
3.6 Метод сопряженных градиентов
3.7 Принцип динамического программирования
3.8 Метод ветвей и границ
3.9 Методы Gradient boosting
3.10 Алгоритм Кадана
3.11 Поиск методом золотого сечения
3.12 Производящие функции
3.13 Запаздывающие генераторы Фибоначчи
3.14 Memoization
3.15 Корекурсия
3.16 Задача 3-SAT
3.17 Алгоритм фрактального сжатия
Структуры данных (рекурсивные)
3.18 Список
3.19 Дерево
3.20 Граф

Строки
4.1 Z-функция
4.2 Алгоритм Кнута-Морриса-Пратта
4.3 Алгоритм Ахо-Корасик
4.4 Алгоритм Бойера-Мура
4.5 Алгоритм Бойера-Мура-Хорспула
4.6 Сходство Джаро-Винклера
4.7 Расстояние Левенштейна, алгоритм Укконена
4.8 Расстояние Дамерау-Левенштейна
4.9 Алгоритм Карпа-Миллера-Розенберга
4.10 Алгоритм Каркайнена-Сандерса
4.11 Алгоритм Арикавы-Аримуты-Касаи-Ли-Парка
4.12 Алгоритм Ву-Менбера
4.13 Алгоритм Ландау-Вишкена
4.14 Алгоритм Майерса
Структуры
4.15 Префиксное дерево
4.16 Суффиксный массив
4.17 Суффиксное дерево

Порядковые статистики, потоковые алгоритмы
5.1 Алгоритм BFPRT
5.2 Алгоритм Манро-Патерсона
5.3 Алгоритм Канна-Гринвальда
5.4 Алгоритм большинства голосов Бойера-Мура
5.5 Алгоритм Lossy Count

Деревья
6.1 Эйлеров обход дерева, DFS, BFS
6.2 Двоичное дерево поиска
6.3 Декартово дерево
6.4 Красно-черное дерево
6.5 АВЛ-дерево, дерево Фибоначчи
6.6 Splay tree (расширяющееся дерево)
6.7 B, B+, B* дерево, 2-3 дерево
6.8 PQ-дерево
6.9 Дерево отрезков
6.10 Дерево Фенвика
6.11 Алгоритм двоичного подъема (задача LCA)
6.12 Алгоритм Фарах-Колтона и Бендера (RMQ, LCA)
6.13 Sqrt-декомпозиция
6.14 Центроидная декомпозиция
6.15 Heavy-light декомпозиция
6.16 Фибоначчиева куча
6.17 Куча, 2-3 куча
6.18 Очередь с приоритетами
6.19 Множество
6.20 Система непересекающихся множеств
6.21 Лес непересекающихся множеств
6.20 Ассоциативный массив

Графы
7.1 Обход в ширину (BFS)
7.2 Обход в глубину (DFS)
7.3 Топологическая сортировка
7.4 Алгоритм Munagala-Ranade
7.5 Алгоритм Mehlhorn-Meyer
7.6 Задача о динамической связности
7.7 Алгоритм поиска точек сочленения графа
7.8 Алгоритм поиска мостов графа
7.9 Алгоритм Косараю
7.10 Алгоритм Тарьяна
7.11 Задача 2-SAT
7.11 Алгоритм Брона-Кербоша
7.12 Конденсация графа
7.13 Раскраска графа
7.14 Задача о назначениях
7.15 Венгерский алгоритм
7.16 Алгоритм Ульмана
Структуры
7.17 Матрица смежности
7.18 Матрица достижимости
7.19 Матрица сильной связности
7.20 Матрица Лапласа
7.21 Матрица Инцидентности
7.22 Список смежности
7.23 Список ребер

Графы: циклы
8.1 Алгоритм поиска Эйлерова цикла
8.2 Алгоритм поиска Эйлерова пути
8.3 Алгоритм поиска Гамильтонова цикла
8.3 Алгоритм поиска Гамильтонова пути
8.4 Задача Коммивояжера

Графы: остовное дерево
9.1 Теорема Кирхгофа
9.2 Теорема Кэли о числе деревьев, код Прюфера
9.3 Лемма о безопасном (минимальном) ребре
9.4 Алгоритм Краскала
9.5 Алгоритм Примы
9.6 Алгоритм Борувки
9.7 Задача устранения петель в сети Ethernet (STP)
9.8 Задача Штейнера

Графы: кратчайший путь
10.1 Алгоритм Дейкстры
10.2 Алгоритм Best-First
10.3 Алгоритм A*
10.4 Алгоритм Левита
10.5 Алгоритм Беллмана-Форда
10.6 Алгоритм Флойда-Уоршелла
10.7 Алгоритм ALT
10.8 Алгоритм Reach-based pruning

Графы: потоки в сетях
11.1 Алгоритм Форда-Фалкерсона
11.2 Алгоритм Эдмонса-Карпа (алгоритм Диница)
11.3 Алгоритм поиска потока минимальной стоимости
11.4 Сети Петри
11.5 Алгоритм проверки графа на двудольность
11.6 Алгоритм раскраски двудольного графа
11.7 Алгоритм Хопкрофта-Карпа
11.8 Венгерский алгоритм
11.9 Blossom алгоритм (алгоритм Эдмондса)
11.10 Алгоритм Штор-Вагнера

Геометрия
12.1 Метод Гаусса
12.2 Поиск точек в прямоугольнике
12.3 Алгоритм Бентли-Оттмана
12.4 Алгоритм Грэхема
12.5 Алгоритм Джарвиса
12.6 Алгоритм Чана
12.7 Алгоритм Киркпатрика
12.8 Метод трассировки луча
12.9 Метод суммирования углов
12.10 Диаграмма Вороного и триангуляция Делоне
12.11 Алгоритм Форчуна
12.12 Рекурсивное построение диаграммы Вороного
12.13 SLERP
Структуры
12.13 R, R+, R* дерево
12.14 K-мерное дерево
12.15 BSP, VP дерево
12.16 Дерево покрытий

Персистентные структуры
13.1 Метод копирования пути
13.2 Метод толстых узлов
Структуры
13.3 Персистентный стек
13.4 Персистентная очередь
13.5 Персистентное дерево

Консенсус в сетях
14.1 Алгоритм Paxos
14.2 Задача Византийских генералов
14.3 Кворум
14.4 CAP-теорема
14.5 PACELC-теорема
14.6 Королевский алгоритм
14.7 Алгоритм Zyzzyva
Структуры
14.8 Blockchain

Целочисленное программирование
15.1 Каноническая форма, сложность решения
15.2 Алгоритмы полного перебора
15.3 Алгоритм Нарайаны
15.4 Задача о ранце
15.5 Алгоритм Meet-in-the-Middle
15.6 Задача раскроя
15.7 Метод обратного поиска
15.8 Задача планирования производства
15.9 Задача оптимизации телекоммуникационных сетей
15.10 Метод секущих плоскостей, алгоритм Гомори
15.11 Алгоритм Альфа-Бета отсечений
15.12 Жадные алгоритмы
15.13 Матроиды, алгоритм Радо-Эдмонса

Быстрые вычисления
16.1 Умножение Карацубы
16.2 Алгоритм Шенхаге-Штрассена
16.3 Алгоритмы возведения числа в степень
16.4 Алгоритмы возведения в степень числа по модулю
16.5 Алгоритм Кули-Тьюки
16.6 Алгоритм Штрассена

Факторизация
17.1 Алгоритм Евклида (НОД)
17.2 Алгоритм факторизации Ферма
17.3 Метод квадратичных форм Шенкса
17.4 Ро-алгоритм Полларда
17.5 Метод квадратичного решета
17.6 Общий метод решета числового поля
17.7 Факторизация с помощью эллиптических кривых
17.8 Тест Агравала-Каяла-Саксены
17.9 Алгоритм Берлекэмпа

Дискретное логарифмирование
18.1 Алгоритм Гельфонда-Шенкса
18.2 Алгоритм COS

Обработка очередей
18.1 Семейство алгоритмов Round-robin
18.2 Алгоритм EDF
18.3 Алгоритм SRTF
18.4 Алгоритм Fixed-priority pre-emptive scheduling
18.5 Задача составления расписания (JSP, OSSP)
18.6 CFS планировщик
18.7 BFS планировщик

Кеширование
19.1 T-дерево
19.2 Алгоритм Белади
19.3 FIFO, LIFO кеширование
19.4 LRU, PLRU кеширование
19.5 MRU кеширование
19.6 RR кеширование
19.7 LFU кеширование
19.8 MQ кеширование
19.9 ARC кеширование

Рандомизированные алгоритмы
20.1 Метод Монте-Карло
20.2 Поиск наименьшего набора ребер, разрезающего циклы
20.3 Муравьиный алгоритм
20.4 Алгоритм Каргера
20.5 Изоморфизм графов (алгоритм Blum-Kanan)
20.6 Rapidly exploring random tree
20.7 Тасование Фишера-Йетса
20.8 Алгоритм Karloff–Zwick

Вероятностные тесты на простоту
21.1 Тест Ферма
21.2 Тест Миллера-Рабина
21.1 Тест Бейли-Померанца-Селфриджа-Уогстаффа

Вебграфы
22.1 Модель Болобаша-Альберта
22.2 Модель Болобаша-Риордана
22.3 Модель Бакли-Остгус
22.4 Модель копирования
22.5 PageRank, Google matrix
Структуры
22.1 MapReduce
22.2 Apache GiGraph
22.3 Pregel

Хеширование
23.1 Двойное хеширование
23.2 Фильтр Блума
23.3 Count-min sketch
23.4 Универсальное хеширование
23.5 SWIFFT
23.6 MD5
23.7 SHA-2
23.8 SHA-3 (Keccak)
23.9 Дерево Меркла
23.10 Подпись Меркла
23.11 Хеш-функции, учитывающие близость (LSH)
23.12 Хеширование на основе расстояния Хэмминга
23.13 MinHash
23.14 SimHash
23.15 Поиск ближайшего соседа c помощью LSH

** При этом стоит учесть что запланированы еще курсы по Теории графов, Дискретной математике, Экстремальным задачам, Машинному обучению, Теории сложности и пр.пр.пр. Т.е. это просто фундаментальный курс по алгоритмам и структурам данных, который является точкой отсчета для всего остального (ну как курс по Математическому анализу).

*** Это несколько больше чем я сам знаю, так что это еще и мой план для себя подтянуть неизвестные/забытые темы. Обсудив его с коллегами, на предмет кто будет читать мы пришли к выводу, что мы все были бы рады и сейчас прослушать такой курс.

Да блин, хватит упарываться уже. К чему эта сугубая религиозность: ФП, ООП, это все мелочи. ФП и ООП это всего лишь инструменты для построения абстракции. Мы ж не спорим чо круче пила или молоток. ФП — небольшие функции для обработки состояния без сохранения состояния. ООП — хранение состояния системы во время всего жизненного цикла. Зачем противопоставлять эти концепции? Они ж взаимодополняют друг друга?

ФП всего лишь говорит вам — не хотите неопределенного поведения — уберите сайд-эффекты. Это не значит, что их не должно быть, просто они должны жить отдельно. Отделяйте операции над данными от самих данных. Я для себя выработал следующий подход: Обработка данных — класс, который через конструктор принимает объект с состоянием.

Таким образом все состояние над которым мы производим операции можно протестировать, потому что мы его задаем только в конструкторе. Легко пользоваться моками. И да, несмотря на то, что NumericOperation хранит ссылку на состояние это не мешает нам писать в ФП стиле. Ведь функция add — чистая.

Для того, чтобы поддерживать систему и дальше. даже если она будет очень сложной — используйте Dependency Injection. Таким образом вы не будете сами инстанцировать классы, вы будете только указывать каким образом это сделать и какие зависимости должны быть прокинуты. Так можно расширять контракт без потери обратной совместимости на уровне входных данных. Мы не должны зависеть от атомарных типов. Мы должны зависеть от абстракций.

Тест Бейли — Померанца — Селфриджа — Уогстаффа (БПСВ, BPSW) — вероятностный алгоритм проверки на простоту, который определяет, является число составным или вероятно простым. Назван по фамилиям его изобретателей — Роберта Бэйли, Карла Померанца, Джона Селфриджа, Сэмюэля Вагстаффа.

Тест сочетает тест Ферма на сильную псевдопростоту по основанию 2 и тест Люка на сильную псевдопростоту. Для тестов Ферма и Люка существуют отдельные списки псевдопростых чисел, то есть составных чисел, которые проходят испытание на простоту. Например, первые десять сильных псевдопростых чисел для испытания Ферма по основанию 2:

2047, 3277, 4033, 4681, 8321, 15 841, 29 341, 42 799, 49 141 и 52 633 [1]

Первые десять псевдопростых чисел теста Люка (с параметрами P = 1 , Q = − 1 <displaystyle P=1,Q=-1> ):

Читайте также:  Как покупать на амазоне в россию

5459, 5777, 10 877, 16 109, 18 971, 22 499, 24 569, 25 199, 40 309 и 58 519 [2] .

Мощность теста состоит в том, что не существует известных пересечений списков псевдопростых чисел Ферма и псевдопростых чисел Люка. Существуют основания полагать, что в эти списки попадают, как правило, различные типы чисел. Например, псевдопростые по основанию 2, как правило, попадают в класс вычетов 1 по модулю m для многих малых m, в то время как псевдопростые числа Люка, как правило, попадают в класс вычетов −1 по модулю m <displaystyle m> [3] :§6 [4] :Table 2 & §5 . В результате число, которое проходит как сильный тест Ферма, так и сильное испытание Люка, с большой вероятностью будет простым.

Ни одно составное число, меньшее 2 64 (что примерно равно 1,845 · 10 19 ), не проходит тест БПСВ [5] . Таким образом, этот тест можно считать детерминированным тестом простоты для чисел, меньших указанной границы. Также пока не известно ни одно составное число, большее границы, которое проходит тест.

В 1980 году Померанц, Селфридж и Вагстафф предложили вознаграждение в размере $30 тому, кто отыщет контрпример, то есть найдет составное число, которое проходит этот тест. Ричард Гай ошибочно полагал, что размер вознаграждения составляет $620, но он перепутал последовательности Люка и Фибоначчи, и его замечания оказались применимы лишь к одной гипотезе Селфриджа [6] . По состоянию на июнь 2014 года приз так и не был востребован. Тем не менее, эвристический аргумент Померанца указывает на то, что таких контрпримеров существует бесконечно много [7] . Кроме того, Чен и Грин [8] [9] построили множество S, состоящее из 1248 таких простых чисел, что среди 2 1248 произведений различных простых чисел из S может быть около 740 контрпримеров. Однако, они рассматривали более слабый БПСВ-тест, который вместо теста Люка использует тест Фибоначчи.

Содержание

Алгоритм [ править | править код ]

Пусть n <displaystyle n> — нечётное натуральное число, которое необходимо проверить на простоту.

  1. По желанию [уточнить] провести перебор простых делителей, меньших заданной верхней границы, и проверить, является ли число полным квадратом. Если найден простой множитель или число является полным квадратом, проверка завершена — число не простое.
  2. Произвести сильную проверку на простоту по основанию 2. Если n <displaystyle n>не является сильно вероятно простым по основанию 2, то n <displaystyle n>является составным; на этом проверка завершается.
  3. Найти первое D <displaystyle D>в последовательности 5, −7, 9, −11, 13, −15, …, для которого символ Якоби ( D / n ) <displaystyle (D/n)>равен −1. Положим P = 1 <displaystyle P=1>и Q = ( 1 − D ) / 4 <displaystyle Q=(1-D)/4>.
  4. Выполнить сильный тест Люка на простоту с параметрами D , P , Q <displaystyle D,P,Q>. Если n <displaystyle n>не является сильно вероятно простым, то n <displaystyle n>является составным; на этом проверка заканчивается. В противном случае, n <displaystyle n>с высокой вероятностью является простым.

  1. Первый этап лишь повышает эффективность. Тест БПСВ работает и без этого шага, однако, если n <displaystyle n>имеет небольшие простые делители, то самый быстрый способ показать, что n <displaystyle n>является составным — найти такой делитель серией проверок.
  2. На втором этапе однократно применяется тест Миллера — Рабина на простоту. Выбор основания не влияет на эффективность конкретной проверки. Однако, многочисленные исследования показали, что сочетание сильного теста на простоту именно по основанию 2 и сильного теста Люка на простоту показывает хорошие результаты в проверке чисел на простоту.
  3. Бейли и Уогстафф доказали [4] , что среднее количество D <displaystyle D>, которое необходимо перебрать, примерно равно 3,147755149.
  4. Если n <displaystyle n>является полным квадратом, то на этапе 3 никогда не найдется D <displaystyle D>, такое что ( D / n ) = − 1 <displaystyle (D/n)=-1>; однако, это не станет проблемой, поскольку полные квадраты легко обнаружить при помощью метода Ньютона для квадратных корней. Если на шаге 3 не удается найти D <displaystyle D>за короткое время, следует проверить, является ли n <displaystyle n>полным квадратом.
  5. Для заданного n <displaystyle n>существуют и другие методы подбора коэффициентов [4] :1401, 1409 . Важно то, что символ Якоби ( D / n ) <displaystyle (D/n)>должен быть равен −1. Брессон и Вэгон доказали, что для эффективности тестирования символ Якоби должен быть равен −1, а значение Q ≠ ± 1 <displaystyle Q
    eq pm 1>[10] :266–269 .

Ошибки при использовании теста Ферма отдельно от теста Люка [ править | править код ]

В списках псевдопростых чисел по разным основаниям существуют значительные совпадения.

Если n <displaystyle n> — псевдопростое по некоторому основанию a <displaystyle a> , то n <displaystyle n> , вероятно, является псевдопростым и по многим другим основаниям [11] .

Например, n = 341 <displaystyle n=341> псевдопросто по основанию 2. Бейли и Вагстафф доказали [4] , что существует 100 значений a <displaystyle a> (по модулю 341), для которых 341 псевдопросто по основанию a <displaystyle a> . (Первые десять из них: 1, 2, 4, 8, 15, 16, 23, 27, 29, и 30). Количество таких a <displaystyle a> по сравнению с n <displaystyle n> обычно гораздо меньше.

Поэтому, если n <displaystyle n> — псевдопросто по основанию a <displaystyle a> , высока вероятность того, что n <displaystyle n> псевдопросто и по какому-то ещё основанию. Например, существует 21853 псевдопростых чисел по основанию 2 на отрезке от 0 до 25·10 9 . Это лишь около двух чисел на миллион из всех нечетных на этом отрезке. Однако:

  • 4709 из этих 21853 чисел (более 21 процента) также псевдопросты по основанию 3; (и по всем 3-гладким основаниям)
  • 2522 из этих 4709 чисел (более 53 процента) псевдопросты по основаниям 2, 3, и 5; (и по всем 5-гладким основаниям)
  • 1770 из этих 2522 чисел (более 70 процентов) псевдопросты по основаниям 2, 3, 5, и 7. (и по всем 7-гладким основаниям)

29341 — наименьшее псевдопростое по основаниям от 2 до 10. (и по всем 7-гладким основаниям). Это указывает на то, что вероятностные тесты простоты по разным основаниям не независимы, таким образом проведение теста Ферма по все большему количеству результатов будет отсеивать с каждым разом все меньшее количество псевдопростых. С другой стороны, вычисления вплоть до 2 64 , упомянутые выше, говорят о том, что тесты Ферма и Люка являются независимыми, таким образом, комбинация этих тестов является мощным тестом на простоту, особенно при использовании сильных форм этих тестов.

Существуют также пересечения между сильными псевдопростыми числами по разным основаниям. Например, 1373653 является наименьшим сильным псевдопростым по всем основаниям от 2 до 4 (и по всем 3-гладким), а 3215031751 — наименьшее сильное псевдопростое по всем основаниям от 2 до 10 (и всем 7-гладким). Арнольд [12] предъявляет 397-значное составное число N, который является сильным псевдопростым по всем основаниям, меньшим 307. (и по всем 293-гладким). Поскольку N является числом Кармайкла, N также будет (не обязательно сильно) псевдопростым по всем основаним меньшим р, где р — наименьший 131-значный простой делитель N. В то же время, быстрый подсчет показывает, что N не является псевдопоростым числом Люка, если D, P, Q были выбраны методом, описанным выше, таким образом тест БПСВ определит, что это число составное.

Применения сочетания тестов Ферма и Люка на простоту [ править | править код ]

Нижеперечисленные компьютерные системы и программные пакеты используют различные версии теста БПСВ.

Функции IsPrime в Maple [13] , PrimeQ в Mathematica [14] , is_pseudoprime в Sage [15] и функции isprime и ispseudoprime в PARI/GP [en] [16] используют сочетание теста Миллера — Рабина (сильного теста Ферма) и теста Люка. Функция Primep в Maxima использует такой тест для чисел, превосходящих 341550071728321 [17] .

В библиотеке FLINT [en] содержатся функции n_is_probabprime и n_is_probabprime_BPSW , которые используют комбинированный тест, а также другие функции, которые используют испытания Ферма и Люка по отдельности [18] .

Класс BigInteger в стандартных версиях Java и в версиях с открытым исходным кодом, таких как OpenJDK, имеет метод isProbablePrime . Этот метод проводит один или несколько тестов Миллера — Рабина по случайными основаниям. Если проверяемое число содержит 100 и более битов, этот метод также проводит тест Люка, который проверяет, что U n + 1 = − ( mod n ) <displaystyle U_=-<pmod >> [19] [20] . Использование случайных оснований в тестах Миллера — Рабина имеет как преимущества, так и недостатки по сравнению с проверкой лишь по основанию 2, как в тесте БПСВ. Преимуществом использования случайных оснований является то, что можно получить вероятностную оценку того, что n является составным. Недостатком является то, что, в отличие от теста БПСВ, нельзя с уверенностью сказать, что если n меньше, чем некоторая фиксированная граница, например 2 64 , то n является простым.

В языке Perl модули Math::Primality [21] и Math::Prime::Util [22] [23] содержат функции для выполнения сильного теста БПСВ, а также отдельные функции для сильного теста на псевдопростоту и сильного теста Люка. Библиотека NZMATH [24] языка Python содержит сильный тест на псевдопростоту и сильный тест Люка, но не содержит их комбинации.

Функция mpz_probab_prime_p из GNU Multiple Precision Arithmetic Library использует тест Миллера — Рабина, но не использует тест Люка [25] . Функции IsProbablePrime и IsProbablyPrime из Magma проводят 20 тестов Миллера — Рабина для чисел больших 34·10 13 , однако не используют их сочетание с тестом Люка [26] .

Ссылка на основную публикацию
Adblock detector