КВАДРАТИЧНЫЕ ВЫЧЕТЫ
|
ВВЕДЕНИЯ 2
Теория чисел в Средние века 2
Применение теории чисел в криптографии 5
1. О делимости чисел 5
1.1 Основные понятия теории делимости чисел 5
1.2 Свойства делимости целых чисел 6
1.3 Наименьшее общее кратное и наибольший общий делитель 8
2. Арифметические функции 11
2.1 Мультипликативные функции и их свойства 11
3. Числовые сравнения 13
3.1 Числовые сравнения и их основные свойства 13
3.2 Полная и приведенная системы вычетов 15
3.3 Теорема Эйлера и Ферма 16
4. Сравнения с одним неизвестным 17
4.1 Основные определения 17
4.2 Сравнения первой степени 19
4.3 Китайская теорема об остатках 20
4.4 Полиномиальные сравнения по простому модулю 24
4.5 Полиноминальные сравнения по составному модулю 31
5. Сравнения второй степени 35
5.1 Сравнения второй степени по простому модулю 35
5.2 Символ Лежандра и его свойства 37
5.3 Квадратичный закон взаимности 39
5.4 Символ Якоби и его свойства 47
ЗАКЛЮЧЕНИЕ 51
СПИСОК ЛИТЕРАТУРЫ 52
Теория чисел в Средние века 2
Применение теории чисел в криптографии 5
1. О делимости чисел 5
1.1 Основные понятия теории делимости чисел 5
1.2 Свойства делимости целых чисел 6
1.3 Наименьшее общее кратное и наибольший общий делитель 8
2. Арифметические функции 11
2.1 Мультипликативные функции и их свойства 11
3. Числовые сравнения 13
3.1 Числовые сравнения и их основные свойства 13
3.2 Полная и приведенная системы вычетов 15
3.3 Теорема Эйлера и Ферма 16
4. Сравнения с одним неизвестным 17
4.1 Основные определения 17
4.2 Сравнения первой степени 19
4.3 Китайская теорема об остатках 20
4.4 Полиномиальные сравнения по простому модулю 24
4.5 Полиноминальные сравнения по составному модулю 31
5. Сравнения второй степени 35
5.1 Сравнения второй степени по простому модулю 35
5.2 Символ Лежандра и его свойства 37
5.3 Квадратичный закон взаимности 39
5.4 Символ Якоби и его свойства 47
ЗАКЛЮЧЕНИЕ 51
СПИСОК ЛИТЕРАТУРЫ 52
В Древнем Египте математические операции проводились над целыми числами и аликвотными дробями.
Аликвотная дробь - в математике сумма нескольких попарно различных дробей вида 1 п'
Математические папирусы содержат задачи с решениями и вспомогательные таблицы. Ещё более широкое применение таблиц характерно для Вавилона, которые вслед за шумерами использовали шестидесятеричную систему счисления. Вавилонские клинописные математические тексты включают таблицы умножения и обратных чисел, квадратов и кубов чисел натурального ряда. В Вавилоне знали множество пифагоровых троек, для поиска которых, вероятно, пользовались неизвестным общим приемом. Самой древней археологической находкой в истории арифметики является обломок глиняной таблички Плимптон, 322, датируемый 1800-ми годами до н. э. Он содержит список Пифагоровых троек, то есть натуральных чисел (а, Ь, с) такие что а2 + Ь2 = с2. В тройках встречаются пятизначные числа, да и их самих слишком много, чтобы предположить что они были получены механическим перебором вариантов. Весомый вклад в становление теории чисел оказали пифагорейцы, Евклид и Диофант. Пифагорейцы рассматривали только целые положительные числа и полагали число собранием единиц. Единицы были неделимы и располагались в виде правильных геометрических тел. Пифагорейцам характерно определение «фигурных чисел» («треугольных», «квадратных» и других).
Фигурные числа — числа, которые можно представить с помощью геометрических фигур.
Изучая свойства чисел, они разбили их на чётные и нечётные, простые и составные. Вероятно, именно пифагорейцы с помощью только признака делимости на два смогли доказать, что если 1 + 2 + ••• + 2п = р — простое число, то 2пр — совершенное число. Только в XVIII веке Эйлер доказал, что других четных совершенных чисел не существует, а вопрос о бесконечности числа совершенных чисел до сих пор не решён. Также пифагорейцы нашли бесконечное множество целых решений уравнения х2 + у2 = z2, так называемых пифагоровых троек, и вывели для них общую формулу.
Теория чисел в Средние века
Индийские математики Бхаскары, Брахмагупта и Ариабхата решали диофантовы уравнения вида ах + Ь = су в целых числах. Кроме того, они решали в целых числах 2
уравнения вида ах2 + b = у2, что было наивысшим достижением индийских математиков в области теории чисел. Впоследствии это уравнение и его частный случай при b = 1 привлекли внимание Эйлера, Лагранжа и Ферма. Предложенный метод Лагранжем, метод нахождения решения был близок к индийскому.
Эта дипломная работа относится к аналитической теории чисел. Теория чисел имеет своим предметом числа и их свойства, т.е. числа выступают здесь не как средство или инструмент, а как объект исследования. Натуральный ряд
1, 2, 3,4, 5,..., 9,10,11, ..., 99,100,101, ...
— множество натуральных чисел, является важнейшей областью исследований, необычайно содержательной, важной и интересной. Начала исследований натуральных чисел было заложены в Древней Греции. Были изучены свойства делимости чисел, доказана бесконечность множества простых чисел и открыты способы их построения (Евклид, Эратосфен). Задачи, связанные с решением неопределенных уравнений в целых числах, были предметом исследований Диофанта, их изучением занимались ученые Древней Индии и Древнего Китая, стран Средней Азии.
В XVII веке П. Ферма и в XVIII Л. Эйлер внесли огромный вклад в наши знания о натуральных числах. И если Ферма оставил лишь свои открытия, не сопроводив их доказательствами, то Эйлер, оказавший большое влияние на развитие всей математики, а также и механики, создал новые методы и приемы, реализовал новые идеи, которые играют важную роль и в современных исследованиях и приложениях теории чисел. В частности, Эйлер был первым, кто предложил использовать средства математического анализа при исследовании проблем теории чисел. Основные исследования в теории чисел можно условно сгруппировать по нескольким направлениям. Впрочем, обширность содержания не позволяет охватить при этом все многообразие результатов и методов теории чисел, значительную часть их пришлось опустить.
Исследования свойств простых чисел. Среди натуральных чисел выделяются так называемые простые числа, т.е. числа, которые невозможно представить в виде произведения меньших натуральных сомножителей. Множество их бесконечно. Асимптотический закон распределения простых чисел утверждает, что их количество в пределах от 1 до заданного числа х асимптотически равно ^. Эта теорема была
независимо доказана 1896 г. Ж. Адамаром и Ш. Ж. де ла Валле-Пуссеном. Вопросы распределения простых чисел в различных числовых последовательностях, например, среди значений фиксированного многочлена /(и) составляют одну из проблем этого 3
раздела теории чисел. Для многочленов первой степени она была решена в середине XIX века Г. П. Лежен Дирихле, однако и в настоящее время не доказана бесконечность множества простых чисел в последовательности п2 + 1, п > 1. Исследование расстояний между соседними простыми числами в натуральном ряду составляет другой круг проблем этого направления. Среди нерешенных задач отметим, например, утверждение о бесконечности множества пар простых чисел р, q с условием р — q = 2, так называемую «проблема близнецов». Эти вопросы, несмотря на их кажущуюся сугубо теоретическую направленность, представляют большой практический интерес.
Диофантовы уравнения. Вопросы разрешимости уравнений в целых числах относятся к древнейшей теории чисел. В связи с исследованиями в этой области уже упоминались имена Диофанта, Ферма и Эйлера. Теория сравнений, являющаяся важным инструментом исследования диофантовых уравнений, была систематически разработана К. Ф. Гауссом, отметим, в частности, его квадратичный закон взаимности. Теория алгебраических чисел, толчком к созданию которых послужили в первую очередь исследования уравнения Ферма хп + уп = zn, п > 3, и в настоящее время приносит плоды в этой области. Отметим, полученное в 2000г. П. Михайлеску решение проблемы Каталана о существовании у уравнения ху — zl = 1 единственного решения в целых числах х > 2, у > 2, z > 2, t > 2, а именно 32 — 23 = 1.
Теория чисел - один из древнейших математических разделов. Арифметические исследования послужили базой для создания ряда разделов математики и в то же время теория чисел использует аналитические, алгебраические, геометрические и многие другие методы для решения теоретико числовых проблем, ряд из которых ждал и ждет своего решения столетиями. Для доказательства все еще открытой гипотезы Римана о нулях дзета—функции использовались методы, развитые в теории дифференциальных уравнений, теории функций комплексного переменного, функциональном анализе. А доказательство асимптотического закона о распределении простых чисел впервые было получено методами комплексного анализа. Попытки решения проблемы Ферма, проблем распределения простых чисел стимулировали развитие ряда разделов алгебры.
Теория чисел безусловно относится к фундаментальным разделам математики. Вместе с тем ряд ее задач имеет самое непосредственное отношение к практической деятельности. Так, например, благодаря в первую очередь запросам криптографии и широкому распространению ЭВМ, исследования алгоритмических вопросов теории чисел переживают в настоящее время период бурного и весьма плодотворного развития. Криптографические потребности стимулировали исследования классических задач теории чисел, в ряду случаев привели к их решению, а также стали источником постановки новых фундаментальных проблем.
Применение теории чисел в криптографии
Теория чисел вплоть до XX века считалась чистой наукой, не обладающей практического использования. Так ее назвал, английский математик Харди, Годфри Хоролд (1877-1947). Начиная со второй половины XX века появились криптографические протоколы, полагающиеся на вычислительную трудность решения задачи разложения больших чисел на простые, трудность решения задачи дискретного логарифмирования и других теоретико - числовых задач. Использование соответствующие криптографические протоколы, например, в банковской практике, медицинской, экономической, военной и государственной. Любая информация может быть закодирована последовательностью чисел. Например, букве «a» можно сопоставить число 1, букве «Ь» число 2 и так далее. Можно сопоставить числа пробелам, в точке, другим знакам препинания. После этого процессы зашифрования и расшифрования информации представляет, как некоторые алгоритмы, перерабатывающие одни массивы целых чисел и другие.
Аликвотная дробь - в математике сумма нескольких попарно различных дробей вида 1 п'
Математические папирусы содержат задачи с решениями и вспомогательные таблицы. Ещё более широкое применение таблиц характерно для Вавилона, которые вслед за шумерами использовали шестидесятеричную систему счисления. Вавилонские клинописные математические тексты включают таблицы умножения и обратных чисел, квадратов и кубов чисел натурального ряда. В Вавилоне знали множество пифагоровых троек, для поиска которых, вероятно, пользовались неизвестным общим приемом. Самой древней археологической находкой в истории арифметики является обломок глиняной таблички Плимптон, 322, датируемый 1800-ми годами до н. э. Он содержит список Пифагоровых троек, то есть натуральных чисел (а, Ь, с) такие что а2 + Ь2 = с2. В тройках встречаются пятизначные числа, да и их самих слишком много, чтобы предположить что они были получены механическим перебором вариантов. Весомый вклад в становление теории чисел оказали пифагорейцы, Евклид и Диофант. Пифагорейцы рассматривали только целые положительные числа и полагали число собранием единиц. Единицы были неделимы и располагались в виде правильных геометрических тел. Пифагорейцам характерно определение «фигурных чисел» («треугольных», «квадратных» и других).
Фигурные числа — числа, которые можно представить с помощью геометрических фигур.
Изучая свойства чисел, они разбили их на чётные и нечётные, простые и составные. Вероятно, именно пифагорейцы с помощью только признака делимости на два смогли доказать, что если 1 + 2 + ••• + 2п = р — простое число, то 2пр — совершенное число. Только в XVIII веке Эйлер доказал, что других четных совершенных чисел не существует, а вопрос о бесконечности числа совершенных чисел до сих пор не решён. Также пифагорейцы нашли бесконечное множество целых решений уравнения х2 + у2 = z2, так называемых пифагоровых троек, и вывели для них общую формулу.
Теория чисел в Средние века
Индийские математики Бхаскары, Брахмагупта и Ариабхата решали диофантовы уравнения вида ах + Ь = су в целых числах. Кроме того, они решали в целых числах 2
уравнения вида ах2 + b = у2, что было наивысшим достижением индийских математиков в области теории чисел. Впоследствии это уравнение и его частный случай при b = 1 привлекли внимание Эйлера, Лагранжа и Ферма. Предложенный метод Лагранжем, метод нахождения решения был близок к индийскому.
Эта дипломная работа относится к аналитической теории чисел. Теория чисел имеет своим предметом числа и их свойства, т.е. числа выступают здесь не как средство или инструмент, а как объект исследования. Натуральный ряд
1, 2, 3,4, 5,..., 9,10,11, ..., 99,100,101, ...
— множество натуральных чисел, является важнейшей областью исследований, необычайно содержательной, важной и интересной. Начала исследований натуральных чисел было заложены в Древней Греции. Были изучены свойства делимости чисел, доказана бесконечность множества простых чисел и открыты способы их построения (Евклид, Эратосфен). Задачи, связанные с решением неопределенных уравнений в целых числах, были предметом исследований Диофанта, их изучением занимались ученые Древней Индии и Древнего Китая, стран Средней Азии.
В XVII веке П. Ферма и в XVIII Л. Эйлер внесли огромный вклад в наши знания о натуральных числах. И если Ферма оставил лишь свои открытия, не сопроводив их доказательствами, то Эйлер, оказавший большое влияние на развитие всей математики, а также и механики, создал новые методы и приемы, реализовал новые идеи, которые играют важную роль и в современных исследованиях и приложениях теории чисел. В частности, Эйлер был первым, кто предложил использовать средства математического анализа при исследовании проблем теории чисел. Основные исследования в теории чисел можно условно сгруппировать по нескольким направлениям. Впрочем, обширность содержания не позволяет охватить при этом все многообразие результатов и методов теории чисел, значительную часть их пришлось опустить.
Исследования свойств простых чисел. Среди натуральных чисел выделяются так называемые простые числа, т.е. числа, которые невозможно представить в виде произведения меньших натуральных сомножителей. Множество их бесконечно. Асимптотический закон распределения простых чисел утверждает, что их количество в пределах от 1 до заданного числа х асимптотически равно ^. Эта теорема была
независимо доказана 1896 г. Ж. Адамаром и Ш. Ж. де ла Валле-Пуссеном. Вопросы распределения простых чисел в различных числовых последовательностях, например, среди значений фиксированного многочлена /(и) составляют одну из проблем этого 3
раздела теории чисел. Для многочленов первой степени она была решена в середине XIX века Г. П. Лежен Дирихле, однако и в настоящее время не доказана бесконечность множества простых чисел в последовательности п2 + 1, п > 1. Исследование расстояний между соседними простыми числами в натуральном ряду составляет другой круг проблем этого направления. Среди нерешенных задач отметим, например, утверждение о бесконечности множества пар простых чисел р, q с условием р — q = 2, так называемую «проблема близнецов». Эти вопросы, несмотря на их кажущуюся сугубо теоретическую направленность, представляют большой практический интерес.
Диофантовы уравнения. Вопросы разрешимости уравнений в целых числах относятся к древнейшей теории чисел. В связи с исследованиями в этой области уже упоминались имена Диофанта, Ферма и Эйлера. Теория сравнений, являющаяся важным инструментом исследования диофантовых уравнений, была систематически разработана К. Ф. Гауссом, отметим, в частности, его квадратичный закон взаимности. Теория алгебраических чисел, толчком к созданию которых послужили в первую очередь исследования уравнения Ферма хп + уп = zn, п > 3, и в настоящее время приносит плоды в этой области. Отметим, полученное в 2000г. П. Михайлеску решение проблемы Каталана о существовании у уравнения ху — zl = 1 единственного решения в целых числах х > 2, у > 2, z > 2, t > 2, а именно 32 — 23 = 1.
Теория чисел - один из древнейших математических разделов. Арифметические исследования послужили базой для создания ряда разделов математики и в то же время теория чисел использует аналитические, алгебраические, геометрические и многие другие методы для решения теоретико числовых проблем, ряд из которых ждал и ждет своего решения столетиями. Для доказательства все еще открытой гипотезы Римана о нулях дзета—функции использовались методы, развитые в теории дифференциальных уравнений, теории функций комплексного переменного, функциональном анализе. А доказательство асимптотического закона о распределении простых чисел впервые было получено методами комплексного анализа. Попытки решения проблемы Ферма, проблем распределения простых чисел стимулировали развитие ряда разделов алгебры.
Теория чисел безусловно относится к фундаментальным разделам математики. Вместе с тем ряд ее задач имеет самое непосредственное отношение к практической деятельности. Так, например, благодаря в первую очередь запросам криптографии и широкому распространению ЭВМ, исследования алгоритмических вопросов теории чисел переживают в настоящее время период бурного и весьма плодотворного развития. Криптографические потребности стимулировали исследования классических задач теории чисел, в ряду случаев привели к их решению, а также стали источником постановки новых фундаментальных проблем.
Применение теории чисел в криптографии
Теория чисел вплоть до XX века считалась чистой наукой, не обладающей практического использования. Так ее назвал, английский математик Харди, Годфри Хоролд (1877-1947). Начиная со второй половины XX века появились криптографические протоколы, полагающиеся на вычислительную трудность решения задачи разложения больших чисел на простые, трудность решения задачи дискретного логарифмирования и других теоретико - числовых задач. Использование соответствующие криптографические протоколы, например, в банковской практике, медицинской, экономической, военной и государственной. Любая информация может быть закодирована последовательностью чисел. Например, букве «a» можно сопоставить число 1, букве «Ь» число 2 и так далее. Можно сопоставить числа пробелам, в точке, другим знакам препинания. После этого процессы зашифрования и расшифрования информации представляет, как некоторые алгоритмы, перерабатывающие одни массивы целых чисел и другие.
В данной дипломной работе мы рассмотрели такой раздел математики как теория чисел. Поговорили про то как развивался этот раздел, привели основные определения, теоремы и свойства и решили поставленные примеры.
В первой главе моего диплома я рассмотрел основные понятия теории делимости чисел, свойства делимости целых чисел, наименьшее общее кратное и наибольший общий делитель.
Во второй главе я освоил арифметические функции, то есть комплексно значные функции, и наиболее важные свойства.
В третьей главе своего диплома я разобрал такую тему как числовые сравнения, в ней я изучил про их основные свойства, полную и приведенную систему вычетов, теорему Эйлера и Ферма.
Четвёртая глава посвящена сравнению с одним неизвестным, привели основные определения, китайскую теорему об остатках, сравнения первой степени и привёл некоторые примеры, касающиеся этого раздела.
В пятой главе говорится о такой теме как сравнения второй степени, в ней мы подробно разобрали символ Лежандра и его свойства, квадратичный закон взаимности, символ Якоби и его свойства, разобрали и решили поставленные примеры.
Так же хочется отметить в заключении, что теория чисел широко применяется в криптографии. После того как теорию чисел начали использоваться в криптографии, стало практически невозможно расшифровать послание, даже если знаешь способ шифрования. Хорошие специалисты и по сей день ценятся в этом направлении.
В первой главе моего диплома я рассмотрел основные понятия теории делимости чисел, свойства делимости целых чисел, наименьшее общее кратное и наибольший общий делитель.
Во второй главе я освоил арифметические функции, то есть комплексно значные функции, и наиболее важные свойства.
В третьей главе своего диплома я разобрал такую тему как числовые сравнения, в ней я изучил про их основные свойства, полную и приведенную систему вычетов, теорему Эйлера и Ферма.
Четвёртая глава посвящена сравнению с одним неизвестным, привели основные определения, китайскую теорему об остатках, сравнения первой степени и привёл некоторые примеры, касающиеся этого раздела.
В пятой главе говорится о такой теме как сравнения второй степени, в ней мы подробно разобрали символ Лежандра и его свойства, квадратичный закон взаимности, символ Якоби и его свойства, разобрали и решили поставленные примеры.
Так же хочется отметить в заключении, что теория чисел широко применяется в криптографии. После того как теорию чисел начали использоваться в криптографии, стало практически невозможно расшифровать послание, даже если знаешь способ шифрования. Хорошие специалисты и по сей день ценятся в этом направлении.
