Тест на простоту Бэйли – PSW

Нерешенная задача по математике :

Существует ли составное число, которое проходит тест на простоту Бейли-ПСВ?

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

Тест Бэйли-ПСВ представляет собой комбинацию сильного критерия вероятного простого числа Ферма по основанию 2 и стандартного или сильного критерия вероятного простого числа Люка . Каждый из тестов Ферма и Лукаса имеет свой собственный список псевдопростых чисел, то есть составных чисел, которые проходят тест. Например, первые десять сильных псевдопростых чисел по основанию 2 равны

2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141 и 52633 (последовательность A001262 в OEIS ).

Первые десять сильных псевдопростых чисел Люка (с параметрами Люка ( P , Q ), определенными методом Селфриджа A) являются

5459, 5777, 10877, 16109, 18971, 22499, 24569, 25199, 40309 и 58519 (последовательность A217255 в OEIS ).

Между этими списками нет известных совпадений, и есть даже свидетельства того, что числа имеют тенденцию быть разного рода; фактически, даже при использовании стандартного и не сильного теста Лукаса никакого известного совпадения нет. Например, псевдопростые числа Ферма по основанию 2 имеют тенденцию попадать в класс вычетов 1 (mod m ) для многих малых m , тогда как псевдопростые числа Люка имеют тенденцию попадать в класс вычетов -1 (mod m ). ^{[ 1 ]}^: §6^{[ 2 ]}^{: Таблица 2 и §5} В результате число, которое проходит как сильное основание Ферма 2, так и сильный тест Люка, с большой вероятностью будет простым. Если вы выберете случайную базу, возможно, найдется некоторое составное n, которое пройдет тесты Ферма и Люка. Например, n=5777 является сильным основанием psp 76, а также сильным псевдопростым числом Люка.

Нет составного числа ниже 2 ⁶⁴ (приблизительно 1,845·10 ¹⁹) проходит сильный или стандартный тест Бэйли – PSW, ^{[ 3 ]} этот результат также был отдельно проверен Чарльзом Грейтхаусом в июне 2011 года. Следовательно, этот тест представляет собой детерминистический тест на простоту чисел ниже этой границы. Также нет известных составных чисел выше этой границы, которые прошли бы тест, другими словами, нет известных псевдопростых чисел Бэйли – PSW.

В 1980 году авторы Померанс, Селфридж и Вагстафф предложили 30 долларов за открытие контрпримера, то есть составного числа, прошедшего этот тест. Ричард Гай ошибочно заявил, что стоимость этого приза была увеличена до 620 долларов, но он перепутал последовательность Лукаса с последовательностью Фибоначчи , и его замечания действительно применимы только к гипотезе Селфриджа . ^{[ 4 ]} По состоянию на июнь 2014 года приз остается невостребованным. Однако эвристический аргумент Померанса предполагает, что существует бесконечно много контрпримеров. ^{[ 5 ]} Более того, Чен и Грин ^{[ 6 ]}^{[ 7 ]} построили набор S из 1248 простых чисел такой, что среди почти 2 ¹²⁴⁸ произведений различных простых чисел из S может быть около 740 контрпримеров. Однако они говорят о более слабом тесте PSW, который заменяет тест Лукаса тестом Фибоначчи.

Тест

Пусть n — нечетное положительное целое число, простоту которого мы хотим проверить.

При желании выполните пробное деление , чтобы проверить, делится ли n на небольшое простое число, меньшее некоторого удобного предела.
Выполните тест на сильное вероятное простое число по основанию 2 . Если n не является сильным вероятным простым основанием 2, то n составное; покидать.
Найдите первый D в последовательности 5, −7, 9, −11, 13, −15, ..., для которого символ Якоби ( D / n ) равен −1. Установите P = 1 и Q = (1 - D )/4.
Выполните сильный вероятный простой тест Люка на n с помощью параметров D , P и Q . Если n не является сильным простым числом Люка, то n составное. В противном случае n почти наверняка простое.

Замечания.

Первый шаг предназначен только для повышения эффективности. Тест Бэйли-ПСВ работает без этого шага, но если n имеет небольшие простые множители, то самый быстрый способ показать, что n является составным, — это найти множитель пробным делением.
Шаг 2, по сути, представляет собой однократное применение критерия простоты Миллера-Рабина , но с использованием фиксированной базы 2. В использовании базы 2 нет ничего особенного; псевдопростые числа по разным основаниям, похоже, имеют одинаковую скорость роста ^{[ 1 ]}, ^: §8 поэтому другие базы могут работать так же хорошо. Однако была проделана большая работа (см. выше), чтобы проверить, что комбинация сильного вероятностного простого теста по основанию 2 и сильного теста Люка хорошо помогает отличать простые числа от составных.
Бэйли и Вагстафф доказали теорему 9 на странице 1413 книги. ^{[ 2 ]} что среднее количество D , которое необходимо попробовать, составляет около 3,147755149.
Если n — идеальный квадрат, то шаг 3 никогда не даст D с ( D / n ) = −1; это не проблема, поскольку идеальные квадраты легко обнаружить с помощью метода Ньютона для поиска квадратных корней. Если на шаге 3 не удается быстро получить D , следует проверить, является ли n идеальным квадратом.
Учитывая n , существуют другие методы D , P и Q. выбора ^{[ 2 ]}^{: 1401, 1409} Важно то, что символ Якоби ( D / n ) равен −1. Брессу и Вагон объясняют, почему мы хотим, чтобы символ Якоби был равен -1, а также почему можно получить более мощные тесты на простоту, если Q ≠ ±1. ^{[ 8 ]}^{: 266–269}
Раздел 6 ^{[ 2 ]} рекомендует, чтобы, если Q ≠ ±1, хороший тест на простоту также проверял два дополнительных условия сравнения. Эти два сравнения почти не требуют дополнительных вычислительных затрат и лишь в редких случаях верны, если n является составным: $V_{n+1}\equiv 2Q{\pmod {n}}$ и $Q^{(n+1)/2}=Q\cdot Q^{(n-1)/2}\equiv Q\cdot \left({\tfrac {Q}{n}}\right){\pmod {n}}$ .
Существуют более слабые версии теста Бэйли-PSW, и этот вариант иногда называют тестом Стронга Бэйли-PSW.
Если тест Лукаса заменить тестом Фибоначчи, то его следует называть не тестом Бэйли – PSW, а скорее тестом Селфриджа или тестом PSW. См. гипотезу Селфриджа о проверке простоты .
В 1980 году Померанс, Селфридж и Вагстафф предложили 30 долларов за составное число, проходящее более слабую версию теста Бэйли-ПСВ. Такое число, прошедшее (сильный) тест Бэйли-ПСВ, будет соответствовать критериям. ^{[ 1 ]}
При соответствующем методе выбора D , P и Q существует только пять нечетных составных чисел (также называемых псевдопростыми числами Диксона второго рода) меньше 10. ¹⁵ для чего $V_{n+1}\equiv 2Q{\pmod {n}}$ . ^{[ 9 ]} Авторы ^{[ 9 ]} предложить более сильную версию теста простоты Бэйли-ПСВ, включающую это сравнение; авторы предлагают вознаграждение в размере 2000 долларов за составное число, которое пройдет этот более строгий тест. Эта версия алгоритма уже используется в системе Mathematica.

Опасность полагаться только на тесты Ферма

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

базу А. Выберите Если n — псевдопростое число по основанию a , то n , скорее всего, будет одним из тех немногих чисел, которые являются псевдопростыми по многим основаниям. ^{[ 10 ]}

Например, n = 341 является псевдопростым числом по основанию 2. Это следует из теоремы 1 на стр. 1392 книги. ^{[ 2 ]} что существует 100 значений a (по модулю 341), для которых 341 является псевдопростым основанием a . (Первые десять таких чисел — 1, 2, 4, 8, 15, 16, 23, 27, 29 и 30). Доля таких по сравнению с n обычно значительно меньше.

Следовательно, если n является псевдопростым по основанию a , то вероятность того, что n будет псевдопростым по отношению к какому-либо другому основанию, с большей вероятностью, чем среднее значение, будет псевдопростым. ^{[ 1 ]}^: 1020 Например, существует 21853 псевдопростых чисел по основанию от 2 до 25·10. ⁹. Это всего лишь два из миллиона нечетных целых чисел в этом диапазоне. Однако: ^{[ 1 ]}^: 1021

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

Число 29341 — наименьшее псевдопростое число по основаниям от 2 до 12. Все это говорит о том, что вероятные простые тесты по разным основаниям не являются независимыми друг от друга, так что выполнение тестов Ферма на вероятные простые числа для все большего и большего количества оснований будет давать уменьшающуюся отдачу. С другой стороны, расчеты в ^{[ 2 ]}^: 1400 и расчеты до 2 ⁶⁴ Упомянутые выше предполагают, что вероятные простые тесты Ферма и Люка независимы , так что комбинация этих типов тестов может составить мощный тест на простоту, особенно если используются сильные формы тестов.

Обратите внимание, что число, псевдопростое по всем простым основаниям 2, ..., p, также является псевдопростым по всем основаниям, которые являются p-гладкими .

Также существует перекрытие сильных псевдопростых чисел по разным основаниям. Например, 1373653 — наименьшее сильное псевдопростое число по основаниям со 2 по 4, а 3215031751 — наименьшее сильное псевдопростое число по основаниям со 2 по 10. Арно ^{[ 11 ]} дает 397-значное число Кармайкла N , которое является сильным псевдопростым числом по всем основаниям меньше 307. Поскольку это N является числом Кармайкла, N также является (не обязательно сильным) псевдопростым псевдопростым числом по всем основаниям меньше p , где p — это 131-значный наименьший простой фактор N . Быстрый расчет показывает, что N является не вероятным простым числом Люка, когда D , P и Q выбираются методом, описанным выше, поэтому это число будет правильно определено тестом Бэйли – PSW как составное.

Применение комбинированных тестов простоты Ферма и Люка

Следующие системы компьютерной алгебры и пакеты программного обеспечения используют некоторую версию теста на простоту Бэйли – PSW.

Maple isprime , Функция ^{[ 12 ]} Mathematica Функция PrimeQ (которая уже использует версию Baillie–PSW 2020 года), ^{[ 13 ]} PARI/ GP Функции isprime и ispseudoprime , ^{[ 14 ]} и SageMath is_pseudoprime функция ^{[ 15 ]} все они используют комбинацию критерия сильного вероятного простого числа Ферма и критерия Люка. Maxima Функция primep использует такой тест для чисел больше 341550071728321. ^{[ 16 ]}

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

Класс BigInteger в стандартных версиях Java и в реализациях с открытым исходным кодом, таких как OpenJDK. имеет метод isProbablePrime . Этот метод выполняет один или несколько тестов Миллера-Рабина со случайными основаниями. Если n , проверяемое число, имеет 100 или более бит, этот метод также выполняет нестрогий тест Люка, который проверяет, равно ли Un ₊₁ 0 (mod n ). ^{[ 18 ]}^{[ 19 ]} Использование случайных оснований в тестах Миллера-Рабина имеет преимущества и недостатки по сравнению с выполнением одного теста по основанию 2, как указано в тесте Бэйли-PSW. Преимущество состоит в том, что при использовании случайных базисов можно получить оценку вероятности того, что n является составным. Недостаток заключается в том, что, в отличие от теста Бэйли-ПСВ, нельзя с уверенностью сказать, что если n меньше некоторой фиксированной границы, такой как 2 ⁶⁴, то n простое.

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

Начиная с версии 6.2.0, GNU Multiple Precision Arithmetic Library библиотеки функция mpz_probab_prime_p использует сильный тест Лукаса и тест Миллера-Рабина; предыдущие версии не использовали Baillie-PSW. ^{[ 25 ]} Magma в Функции IsProbablePrime и IsProballyPrime используют 20 тестов Миллера-Рабина для чисел > 34·10. ¹³, но не объединяйте их с тестом вероятного простого числа Люка. ^{[ 26 ]}

Криптографические библиотеки часто имеют функции первичного тестирования. Альбрехт и др. обсудить тесты, используемые в этих библиотеках. Некоторые используют комбинированный тест Ферма и Люка; многие этого не делают. ^{[ 27 ]}^{: Таблица 1} Что касается некоторых из последних, Albrecht et al. смогли конструировать составные числа, которые библиотеки объявили простыми.

Ссылки

^ Перейти обратно: ^а ^б ^с ^д ^и Померанс, Карл ; Селфридж, Джон Л .; Вагстафф, Сэмюэл С. младший (июль 1980 г.). «Псевдопростые числа до 25·10 ⁹» (PDF) . Математика вычислений . 35 (151): 1003–1026. doi : 10.1090/S0025-5718-1980-0572872-7 . JSTOR 2006210 .
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж Бэйли, Роберт; Вагстафф, Сэмюэл С. младший (октябрь 1980 г.). «Лукас Псевдопраймс» (PDF) . Математика вычислений . 35 (152): 1391–1417. дои : 10.1090/S0025-5718-1980-0583518-6 . JSTOR 2006406 . МР 0583518 .
^ Хорошо, Томас Р. (13 января 2012 г.) [Впервые опубликовано 10 июня 2005 г.]. «Тест на примитивность Бэйли – PSW» . trnicely.net . Архивировано из оригинала 21 ноября 2019 г. Проверено 17 марта 2013 г.
^ Гай, Р. (1994). «Псевдопростые числа. Псевдопростые числа Эйлера. Сильные псевдопростые числа». §A12 в Нерешенных задачах теории чисел . 2-е изд., с. 28, Нью-Йорк: Springer-Verlag. ISBN 0-387-20860-7 .
^ Померанс, К. (1984). «Есть ли контрпримеры для теста на простоту Бэйли – PSW?» (PDF) .
^ Грин, Джон Р. (nd). «Бейли – PSW» . Университет Миннесоты в Дулуте . Проверено 29 мая 2020 г.
^ Чен, Чжо; Грин, Джон (август 2003 г.). «Некоторые комментарии к псевдопростым числам Бэйли – PSW» (PDF) . Ежеквартальный журнал Фибоначчи . 41 (4): 334–344.
^ Брессу, Давид ; Вагон, Стэн (2000). Курс вычислительной теории чисел . Нью-Йорк: Key College Publishing в сотрудничестве со Springer. ISBN 978-1-930190-10-8 .
^ Перейти обратно: ^а ^б Роберт Бэйли; Эндрю Фиори; Сэмюэл С. Вагстафф-младший (июль 2021 г.). «Усиление теста на первичность Бэйли-PSW». Математика вычислений . 90 (330): 1931–1955. arXiv : 2006.14425 . дои : 10.1090/mcom/3616 . ISSN 0025-5718 . S2CID 220055722 .
^ Вагстафф, Сэмюэл С. младший. (1982). «Псевдопростые числа и обобщение гипотезы Артина » Акта Арифметика 41 (2): 141–150. дои : 10.4064/aa-41-2-141-150 .
^ Арно, Ф. (август 1995 г.). «Построение чисел Кармайкла, являющихся сильными псевдопростыми числами по нескольким основаниям» . Журнал символических вычислений . 20 (2): 151–161. дои : 10.1006/jsco.1995.1042 .
^ isprime - Справка Maple документация на сайте Maplesoft.com.
^ Центр документации по языку и системе Wolfram - Некоторые замечания по внутренней реализации документация на wolfram.com.
^ Руководство пользователя по документации PARI/GP (версия 2.11.1) для PARI/GP.
^ Документация SageMath документация для SageMath.
^ Документация руководства Maxima для Maxima.
^ FLINT: Быстрая библиотека документации по теории чисел для FLINT 2.5.
^ BigInteger.java DocJar: Поиск по API Java с открытым исходным кодом.
^ Документация BigInteger.java для OpenJDK.
^ Модуль Math::Primality Perl с тестом BPSW
^ Math::Prime::Util Perl-модуль с тестами на простоту, включая BPSW
^ Math::Prime::Util::GMP Perl-модуль с тестами на простоту, включая BPSW, с использованием C+GMP
^ NZMATH. Архивировано 17 января 2013 г. в системе вычислений теории чисел Wayback Machine на Python.
^ «СимПи» . SymPy — библиотека Python для символьной математики .
^ Документация по алгоритму тестирования GNU MP 6.2.0 Prime для GMPLIB.
^ Система вычислительной алгебры Magma - документация по тестированию простых чисел и простоты для Magma.
^ Альбрехт, Мартин Р.; Массимо, Джейк; Патерсон, Кеннет Г.; Соморовский, Юрай (15 октября 2018 г.). Простое и предубежденное: тестирование примитивности в состязательных условиях (PDF) . Конференция ACM SIGSAC по компьютерной и коммуникационной безопасности 2018. Торонто: Ассоциация вычислительной техники . стр. 281–298. дои : 10.1145/3243734.3243787 .

Дальнейшее чтение

Якобсен, Дана Статистика, таблицы и данные псевдопростых чисел (списки псевдопростых чисел по основанию 2, Лукаса и других псевдопростых чисел до 10). ¹⁴)
Хорошо, Томас Р., Тест на простоту Бэйли – PSW. , заархивировано из оригинала 28 августа 2013 г. , получено 7 августа 2007 г.
Вайсштейн, Эрик В. «Тест на примитивность Бэйли – PSW» . Математический мир .

[PSW-1] Перейти обратно: ^а ^б ^с ^д ^и Померанс, Карл ; Селфридж, Джон Л .; Вагстафф, Сэмюэл С. младший (июль 1980 г.). «Псевдопростые числа до 25·10 ⁹» (PDF) . Математика вычислений . 35 (151): 1003–1026. doi : 10.1090/S0025-5718-1980-0572872-7 . JSTOR 2006210 .

[lpsp-2] Перейти обратно: ^а ^б ^с ^д ^и ^ж Бэйли, Роберт; Вагстафф, Сэмюэл С. младший (октябрь 1980 г.). «Лукас Псевдопраймс» (PDF) . Математика вычислений . 35 (152): 1391–1417. дои : 10.1090/S0025-5718-1980-0583518-6 . JSTOR 2006406 . МР 0583518 .

[TRNicely-3] Хорошо, Томас Р. (13 января 2012 г.) [Впервые опубликовано 10 июня 2005 г.]. «Тест на примитивность Бэйли – PSW» . trnicely.net . Архивировано из оригинала 21 ноября 2019 г. Проверено 17 марта 2013 г.

[4] Гай, Р. (1994). «Псевдопростые числа. Псевдопростые числа Эйлера. Сильные псевдопростые числа». §A12 в Нерешенных задачах теории чисел . 2-е изд., с. 28, Нью-Йорк: Springer-Verlag. ISBN 0-387-20860-7 .

[5] Померанс, К. (1984). «Есть ли контрпримеры для теста на простоту Бэйли – PSW?» (PDF) .

[6] Грин, Джон Р. (nd). «Бейли – PSW» . Университет Миннесоты в Дулуте . Проверено 29 мая 2020 г.

[ChenAndGreene-7] Чен, Чжо; Грин, Джон (август 2003 г.). «Некоторые комментарии к псевдопростым числам Бэйли – PSW» (PDF) . Ежеквартальный журнал Фибоначчи . 41 (4): 334–344.

[Bressoud-8] Брессу, Давид ; Вагон, Стэн (2000). Курс вычислительной теории чисел . Нью-Йорк: Key College Publishing в сотрудничестве со Springer. ISBN 978-1-930190-10-8 .

[bpsw2-9] Перейти обратно: ^а ^б Роберт Бэйли; Эндрю Фиори; Сэмюэл С. Вагстафф-младший (июль 2021 г.). «Усиление теста на первичность Бэйли-PSW». Математика вычислений . 90 (330): 1931–1955. arXiv : 2006.14425 . дои : 10.1090/mcom/3616 . ISSN 0025-5718 . S2CID 220055722 .

[SSW2-10] Вагстафф, Сэмюэл С. младший. (1982). «Псевдопростые числа и обобщение гипотезы Артина » Акта Арифметика 41 (2): 141–150. дои : 10.4064/aa-41-2-141-150 .

[Arnault397Digit-11] Арно, Ф. (август 1995 г.). «Построение чисел Кармайкла, являющихся сильными псевдопростыми числами по нескольким основаниям» . Журнал символических вычислений . 20 (2): 151–161. дои : 10.1006/jsco.1995.1042 .

[12] sprime - Справка Maple документация на сайте Maplesoft.com.

[13] Центр документации по языку и системе Wolfram - Некоторые замечания по внутренней реализации документация на wolfram.com.

[14] Руководство пользователя по документации PARI/GP (версия 2.11.1) для PARI/GP.

[15] Документация SageMath документация для SageMath.

[16] Документация руководства Maxima для Maxima.

[17] FLINT: Быстрая библиотека документации по теории чисел для FLINT 2.5.

[18] BigInteger.java DocJar: Поиск по API Java с открытым исходным кодом.

[19] Документация BigInteger.java для OpenJDK.

[20] Модуль Math::Primality Perl с тестом BPSW

[21] Math::Prime::Util Perl-модуль с тестами на простоту, включая BPSW

[22] Math::Prime::Util::GMP Perl-модуль с тестами на простоту, включая BPSW, с использованием C+GMP

[23] NZMATH. Архивировано 17 января 2013 г. в системе вычислений теории чисел Wayback Machine на Python.

[24] «СимПи» . SymPy — библиотека Python для символьной математики .

[25] Документация по алгоритму тестирования GNU MP 6.2.0 Prime для GMPLIB.

[26] Система вычислительной алгебры Magma - документация по тестированию простых чисел и простоты для Magma.

[27] Альбрехт, Мартин Р.; Массимо, Джейк; Патерсон, Кеннет Г.; Соморовский, Юрай (15 октября 2018 г.). Простое и предубежденное: тестирование примитивности в состязательных условиях (PDF) . Конференция ACM SIGSAC по компьютерной и коммуникационной безопасности 2018. Торонто: Ассоциация вычислительной техники . стр. 281–298. дои : 10.1145/3243734.3243787 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

v т и Теоретико-числовые алгоритмы
Тесты на примитивность	АКС АПРЕЛЬ Бэйли – PSW Эллиптическая кривая Поклингтон Ферма Лукас Лукас-Лемер Лукас-Лемер-Ризель Теорема Прота Пепина Квадратичный Фробениус Solovay–Strassen Миллер-Рабин
Прайм-генерирующий	Сито Аткина Решето Эратосфена Сито Причарда Решето Сундарама Факторизация колес
Целочисленная факторизация	Непрерывная дробь (CFRAC) Диксона Эллиптическая кривая Ленстры (ECM) Эйлера Ро Полларда п - 1 р + 1 Квадратное сито (QS) Сито общего числового поля (GNFS) Сито специального числового поля (SNFS) Рациональное сито Ферма Квадратные формы Шанкса Пробное подразделение Шора
Умножение	Древний Египет Длинный Карацуба Тум-Кук Улицы Шенхаге Фюрера
Евклидово деление	Двоичный Разбивка на части Фурье Гольдшмидт Ньютон-Рафсон Длинный Короткий СТО
Дискретный логарифм	Бэби-шаг, гигантский шаг Поллард Ро Поллард кенгуру Полиг-Хеллман Индексное исчисление Функциональное поле сита
Наибольший общий делитель	Двоичный евклидов Расширенный евклидов Лемерс
Модульный квадратный корень	Лук Поклингтон Тонелли – Шанкс Берлекамп Кунерт
Другие алгоритмы	Чакравала Ворона Возведение в степень возведением в степень Целочисленный квадратный корень Целочисленное отношение ( LLL ; KZ ) Модульное возведение в степень Сокращение Монтгомери Пучок Система Трахтенберга
Курсивом обозначено, что алгоритм предназначен для чисел специальных форм.