Способы проверки простоты числа
Когда Гаусс написал в 1801 г., что «Проблема различения простых и составных чисел и разложения последних на простые сомножители, как известно, является одной из самых важных и полезных в арифметике» он не знал, что 200 лет спустя эта проблема будет иметь огромное значение для криптографии: ее приложениями каждый день пользуются миллионы людей.
Мы обсудим, как проверить простоту целых чисел детерминированными и вероятностными алгоритмами. От слушателей потребуется знакомство с арифметикой вычетов, включая малую теорему Ферма.
Материалы:
- Листок 1
- Листок 2
- Листок 3
- Листок 4
Keith Conrad, Ph.D. Harvard University 1997.
Летняя школа «Современная математика», г. Дубна
21-27 июля 2015 г.
Похожее
-
BBC
Мир математики немыслим без них – без простых чисел. Что такое простые числа, что в них особенного и какое значение они имеют для повседневной жизни? В этом фильме британский профессор математики Маркус дю Сотой откроет тайну простых чисел.
-
Keith Conrad
Для каждого простого p существует нормирование на поле рациональных чисел, пополнение относительно которого называется p-адическими числами. Эти пополнения играют важную роль в теории чисел и смежных областях математики. В этом курсе мы узнаем, что такое p-адические числа, и обсудим несколько элементарных применений к задачам алгебры и теории чисел. От слушателей потребуется знакомство с арифметикой вычетов и пополнением метрического пространствa.
-
Keith Conrad
ABC-гипотеза была сформулирована в 1985 г. и быстро стала центральной проблемой в теории чисел из-за её связей с другими нерешёнными проблемами, а также из-за того, что многие уже доказанные известные результаты были бы её следствиями. В 2012 году японский математик Мотидзуки выложил доказательство ABC-гипотезы в интернете, но математическое сообщество еще не пришло к единому мнению, правильно ли оно. В курсе мы введём ABC-гипотезу, опишем несколько эквивалентных её вариантов, и проследим ее связи с другими проблемами и теоремами в теории чисел. От слушателей потребуется знакомство с арифметикой вычетов и многочленами над полями.
-
Keith Conrad
И целые числа, и многочлены (от одной переменной с коэффициентами в Q, R или Z/pZ) можно делить с остатком. Эта и подобные аналогии в структуре целых чисел и многочленов играли и продолжают играть важную роль в математике, особенно в теории чисел. В этом курсе мы исследуем такие аналогии в контексте теории чисел: на примере непрерывных дробей, уравнения Пелля, квадратичных вычетов, и abc-гипотезы. От слушателей требуется знакомство с пределами и арифметикой вычетов.
-
Дмитрий Орлов
Начав с основной теоремы арифметики, мы расскажем про АВС-гипотезу, которая была сформулирована в 1985 году и быстро стала одной из центральных проблем в теории чисел из-за её связей с другими нерешёнными задачами, а также из-за того, что многие уже доказанные известные результаты были бы её следствиями.
-
Владимир Успенский
Эту формулу нашел Гаусс, он использовал ee в одном из своих доказательств квадратичного закона взаимности. Лишь через несколько лет он сумел доказать, что сумма S_m всегда положительна, так что S_m рано квадратному корню из m. Гаусс записал в дневнике, что его озарение было подобно “вспышке молнии”. Позднее многие известные математики предложили свои доказательства. Одно из самых элегантных принадлежит Дирихле, оно использует ряды Фурье. Предполагается знакомство с понятием сравнения по модулю. Полезно (но необязательно) иметь представление о малой теореме Ферма и о квадратичных вычетах по простому модулю. Знакомства с рядами Фурье не предполагается, необходимые сведения будут сообщены.
-
Роман Федоров
Дзета-функция Римана была введена Эйлером в 1737-м году. Она может быть задана рядом ζ(s) = ∑ 1/n^s при тех значениях s, при которых этот ряд сходится. Я буду рассказывать, в основном, об обобщениях дзета-функции Римана — так называемой арифметической дзета-функции, которая ставится в соответствие диофантову уравнению (дзета-функция Римана соответствует «тривиальному» уравнению x=0).
-
Владимир Арнольд
Ж. Л. Лагранж доказал, что последовательность неполных частных (начиная с некоторого места) периодична, если и только если число x — квадратичная иррациональность. Р. О. Кузьмин доказал, что в последовательности неполных частных почти любого вещественного числа доля d_m равных m неполных частных одинакова (для типичных вещественных чисел). Доля d_m убывает при m→∞ как 1/m^2 и её величина была предсказана Гауссом (ничего не доказавшим). В. И. Арнольда высказал (лет 20 назад) гипотезу, что статистика Гаусса–Кузьмина d_m выполняется также для периодов цепных дробей корней квадратных уравнений x^2+px+q=0 (с целыми p и q): если выписать вместе неполные частные, составляющие периоды всех цепных дробей корней таких уравнений с p^2+q^2≤R^2, то доля неполного частного m среди них будет стремиться к числу d_m при R→∞. В. А. Быковский со своими хабаровскими учениками доказали недавно эту давнюю гипотезу. Несмотря на это, вопрос о статистике не букв, а составленных из них слов [a_k+1, a_k+2,…, a_k+T], которые являются периодами цепных дробей каких-либо корней x уравнений x^2+px+q=0 далеко не решён.
-
Георгий Шабат
В школе нам всем прививается ошибочное представление о том, что на множестве рациональных чисел Q имеется единственное естественное расстояние (модуль разности), относительно которого все арифметические операции непрерывны. Однако существует ещё бесконечное множество расстояний, так называемых p-адических, по одному на каждое число p. Согласно теореме Островского, «обычное» расстояние вместе со всеми p-адическими уже действительно исчерпывают все разумные расстояние Q. Термин адельная демократия введен Ю. И. Маниным. Согласно принципу адельной демократии, все разумные расстояния на Q равны перед законами математики (может быть, лишь традиционное «чуть=чуть равнее…». В курсе будет введено кольцо аделей, позволяющее работать со всеми этими расстояниями одновременно.
-
Жак Сезиано
Мы знаем о Диофанте немного. Кажется, он жил в Александрии. Никто из греческих математиков не упоминает его до IV века, так что он вероятно жил в середине III века. Самая главная работа Диофанта, «Арифметика» (Ἀριθμητικά), состоялась в начале из 13 «книгах» (βιβλία), т. е. главах. Мы сегодня имеем 10 из них, а именно: 6 в греческом тексте и 4 других в средневековом арабском переводе, место которых в середине греческих книг: книги I-III по-гречески, IV-VII по-арабски, VIII-X по-гречески. «Арифметика» Диофанта прежде всего собрание задач, всего около 260. Теории, по правде говоря, нет; имеются только общие инструкции в введении книги, и частные замечания в некоторых задачах, когда нужно. «Арифметика» уже имеет черты алгебраического трактата. Сперва Диофант пользуется разными знаками, чтобы выражать неизвестное и его степени, также и некоторые вычисления; как и все алгебраические символики средних веков, его символика происходит от математических слов. Потом, Диофант объясняет, как решить задачу алгебраическим способом. Но задачи Диофанта не алгебраические в обычном смысле, потому что почти все сводятся к решению неопределённого уравнения или систем таких уравнений.
Далее >>>
|
|