Тестирование примитивности для начинающих
«Тестирование простоты для начинающих» — это математическая книга для студентов, посвященная тестам на простоту , методам проверки того, является ли данное число простым числом , в основе которого лежит тест на простоту AKS , первый метод решения этой проблемы за полиномиальное время . Он был написан Лассе Ремпе-Гилленом и Ребеккой Вальдекер и первоначально опубликован на немецком языке как Тесты простых чисел для начинающих: теория чисел, алгоритмы, криптография (Vieweg+Teubner, 2009). [1] [2] Он был переведен на английский язык как «Проверка простоты для начинающих» и опубликован в 2014 году Американским математическим обществом как 70-й том серии книг Студенческой математической библиотеки. [2] [3] [4] [5] Второе издание на немецком языке было выпущено издательством Springer в 2016 году.
Темы
[ редактировать ]Тестирование на простоту для начинающих состоит из шести глав, разделенных на две части: четыре главы, посвященные базовому материалу по теории чисел и теории сложности вычислений , и три, посвященные тесту на простоту AKS. [1] [5]
Глава 1 включает базовый материал по теории чисел, в том числе фундаментальную теорему арифметики об однозначном разложении на простые числа, биномиальную теорему , алгоритм Евклида для определения наибольших общих делителей и решето Эратосфена для генерации последовательности простых чисел. Глава 2 начинает изучение алгоритмов и их сложности, включая алгоритмы базовых вычислений в арифметике, понятие вычислимости , алгоритмы с полиномиальным временем, рандомизацию и недетерминированное полиномиальное время . В рандомизированных алгоритмах он вводит различие между алгоритмами Лас-Вегаса , которые всегда возвращают правильный ответ через случайный промежуток времени (например, быстрая сортировка ), и алгоритмами Монте-Карло, для которых существует небольшая вероятность получить неправильный ответ (на примере алгоритмов, основанных на о лемме Шварца–Циппеля для проверки полиномиальной идентичности ). В главе 3 представлен дополнительный материал по теории чисел, в том числе китайская теорема об остатках и малая теорема Ферма. и основанный на нем критерий простоты Ферма . Он также знакомит с вычислениями с помощью полиномов и модульной арифметики . Первая часть книги завершается главой 4, посвященной истории простых чисел и проверке простоты, включая теорему о простых числах (в ослабленной форме), применению простых чисел в криптографии и широко используемому тесту простоты Миллера-Рабина . который работает за рандомизированное полиномиальное время. [5]
В главе 5 малая теорема Ферма обобщается на полиномы и вводится рандомизированный тест на простоту, основанный на этом обобщении. В главе 6 представлены ключевые математические результаты, лежащие в основе корректности теста на простоту AKS, а в главе 7 описан сам тест. [5] Корректность и полиномиальное время работы алгоритма строго доказаны. [3] Упражнения включены в каждую главу, а в разделе в конце книги приведены ответы на некоторые из них. [1] [2] В другом приложении перечислены некоторые нерешенные проблемы теории чисел. [3]
Аудитория и прием
[ редактировать ]в первую очередь предназначено для студентов, изучающих математику, Несмотря на то, что «Тестирование на первичность для начинающих» оно требует очень небольших базовых знаний и может также подойти для учащихся старших классов средней школы. [2] [3] Он основан на летней программе для студентов этого уровня, проводимой авторами в Германии с целью познакомить студентов с новейшими исследованиями. [4]
Рецензенты Робин Чепмен и Джеффри Эме согласны с тем, что общее содержание книги, вероятно, слишком незначительно, чтобы использовать ее в качестве основного учебника для курса теории чисел для студентов, но она может быть хорошим дополнением к такому курсу или к курсу по теории чисел. криптография. [3] [4] Рецензент Фредерик Грин рекомендует его как хорошее введение в математические исследования в целом, а также предлагает использовать его исследователями в качестве быстрого справочника по проверке простоты. [5]
Ссылки
[ редактировать ]- ^ Jump up to: а б с Мейдл, Вильфрид, «Обзор тестов на простоту для начинающих », zbMATH , Zbl 1195.11003
- ^ Jump up to: а б с д Вагстафф, Сэмюэл С. младший , «Обзор тестирования на простоту для начинающих », MathSciNet , MR 3154407
- ^ Jump up to: а б с д и Чепмен, Робин (июль 2014 г.), «Обзор тестирования на простоту для начинающих » (PDF) , Информационный бюллетень Лондонского математического общества , вып. 438, с. 49
- ^ Jump up to: а б с Эме, Джеффри (ноябрь 2016 г.), «Приятно рецензировать: две книги о простых числах и факторинге», Cryptologia , 41 (1): 97–100, doi : 10.1080/01611194.2016.1236625 , S2CID 36760384
- ^ Jump up to: а б с д и Грин, Фредерик (июнь 2016 г.), «Обзор тестирования на примитивность для начинающих » (PDF) , ACM SIGACT News , 47 (2): 6–9, doi : 10.1145/2951860.2951863 , S2CID 26146309