Квадратичные вычеты и невычеты и их приложения тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

ФГБОУ ВПО «Московский государственный университет имени М. В. Ломоносова»

На правах рукописи

Копьев Дмитрий Викторович

Квадратичные вычеты и невычеты и их приложения

Специальность 01.01.06 — математическая логика, алгебра и теория чисел

Автореферат диссертации на соискание учёной степени кандидата физико-математических наук

005546590

Москва — 2014

О з ДПР 2014

/7

//

005546590

Работа выполнена на кафедре математического анализа механико-математического факультета ФГБОУ ВПО «Московский государственный университет имени М. В. Ломоносова».

Научный руководитель: Чубариков Владимир Николаевич,

доктор физико-математических наук, профессор

Официальные оппоненты: Рахмонов Зарулло Хусенович,

доктор физико-математических наук, профессор (Институт математики имени А. Джураева

Академии наук Республики Таджикистан

Авдеев Иван Федорович,

кандидат физико-математических наук, доцент (ГОУ ВПО «Орловский государственный университет», факультет экономики и управления) Ведущая организация: ФГБОУ ВПО «Московский педагогический

государственный университет» Защита диссертации состоится 25 апреля 2014 г. в 16 ч. 45 мин. на заседании диссертационного совета Д 501.001.84, созданного на базе ФГБОУ ВПО «Московский государственный университет имени М. В. Ломоносова», по адресу: Российская Федерация, 119991, г. Москва, ГСП-1, Ленинские горы, д. 1, ФГБОУ ВПО МГУ имени М. В. Ломоносова, механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в Фундаментальной библиотеке ФГБОУ ВПО «Московский государственный университет имени М. В. Ломоносова» (г. Москва, Ломоносовский проспект, д. 27, сектор А). Автореферат разослан 25 марта 2014 года.

Учёный секретарь диссертационного совета Д 501.001.84, созданного на базе ФГБОУ ВПО МГУ имени М. В. Ломоносова доктор физико-математических наук, профессор Александр Олегович Иванов

Общая характеристика работы Актуальность темы

Диссертация относится к аналитической теории чисел. Одними из важнейших объектов исследования этой области математики являются квадратичные вычеты и невычеты. Если число а взаимно просто с числом т и сравнение х2 = a (mod тп) разрешимо, то а называется квадратичным вычетом по модулю ш, если данное сравнение неразрешимо, то а называется квадратичным невычетом по модулю т. А. Лежандр ввел специальный символ для обозначения квадратичных вычетов л невычетов по простому модулю р, принимающий значения ±1.

Само понятие квадратичного вычета было введено Л. Эйлером, хотя первые результаты для сравнений второй степени были получены еще П. Ферма. П. Ферма показал, при каких условиях на модуль р сравнение х2 = — 1 (mod р) имеет решение, т.е. при каких условиях —1 будет квадратичным вычетом. С помощью символа Лежандра его результат можно сформулировать следующим образом:

а Л.Эйлер наптел критерий разрешимости сравнения х2 = 2 (mod р). В 1801 г. К.Ф. Гауссом1 было опубликовано первое полное доказательство квадратичного закона взаимности, сформулированного в 1783 г. Л. Эйлером2: если р и q — простые нечетные числа, то

В 1837 г. К. Якоби обобщил символ Лежандра на случай нечетного составного модуля: пусть Р — ргр2 ...рп — разложение нечетного числа Р на простые сомно-

1 C.F. Gauss Disquisitiones Arithmeticae, Göttingen: Königlichen Gesellschaft der Wissenchaften. 1863 (original: 1801).

2L. Euler Disquisitio accuratior circa residua ex divisione quadratorum altiorumque potestatum per números primos relicta, Opera Omnia, I, 3, pp. 513-543 (original: 1783).

1 если а — квадратичный вычет по модулю р; — 1 если а — квадратичный невычет по модулю р\ 0 если р\а.

жители и о — взаимно просто с Р, тогда

Одной из важнейших задач теории чисел является задача об оценке наименьшего квадратичного невычета пр по модулю р. И.М.Виноградов первым получил результаты в этом направлении. Он доказал3, что пр < р*&\п2р. В 1952 г.

Г.Дэвенпорт, П.Эрдеш4 улучшили оценку Виноградова для наименьшего квад-

11 _ ратичного невычета, показав, что пр < р^Ы^р. В 1957 г. Д. Берджесс8 также

1 I.

улучшил результат И.М.Виноградова. Он показал, чтопр < р^ .

В предположении справедливости гипотезы Римана Ю.В. Линников была получена следующая оценка наименьшего квадратичного невычета пр = 0(рЕ). В 1952 г. Н.К. Анкени7 улучшил результат Ю.В. Линника и показал, что в предположении справедливости гипотезы Римана пр = О (log2 р).

Принципиальным шагом в нахождении порядка наименьшего квадратичного невычета, представляющим самостоятельный интерес, является решение задачи о распределении квадратичных вычетов и невычетов на коротком промежутке. Обратим внимание, что согласно теореме Гаусса, в полной системе вычетов половина из них будет квадратичными вычетами, а другая половина — квадратичными невычетами. Задачу о распределении квадратичных вычетов и невычетов на коротком промежутке возможно меньшей длины поставил в 1914г. И.М.Виноградов. И.М.Виноградов8 и Г.Полна9 независимо друг от друга доказали, что на промежутке длины порядка у/р\пр асимптотически поровну квадратичных вычетов и невычетов.

В 1957 г. Д.Берджесс10 улучшил результат И.М.Виноградова, он показал, что квадратичных вычетов и невычетов будет асимптотически поровну на промежутке длины превосходящей р*+е.

3И.М.Виноградов О распределении квадратичных вычетов и невычетов // Жури, физ.-матем. об-ва при Пермском ун-те. 1919. 2, С. 1-16.

4 Я. Davenport, Р. Erdas The destribution of quadratic and higher residues // Puhl. Math., Debrecen. 1952.

2, №3-4, P. 252-265.

6D.A. Burgess The destribntion of quadratic residues and nonresidues. // Math. 1957. 4, №8, P. 106-112.

6 Ю.В.Лин ник Замечание о наименьшем квадратичном невычете. Докл. АН СССР, 1942. Т. 36. №4-5, С.119-120

7N.C. Ankeny The least quadratic non-residue. // Ann. of Math. 1952. 55, P. 65-72.

sИ.М. Виноградов Sur la distribution des residues et des non residues des puissances // Журн. физ.-матем. об-ва при Пермском ун-те. 1918. 1, С. 94-98.

9G.Pàlya Über die Verteelung der quadratischen Reste und Nichtreste // Gött. Nachr. 1918. P.21-29.

WD.A. Burgess The destribution of quadratic residues and nonresidues. // Math. 1957. 4, №8, P. 106-112.

В.H. Чубариков сформулировал многомерный аналог задачи Виноградова на коротком промежутке о количестве вычетов х < X таких, что

fx + аЛ (х + ап\ ,л . ,—

- =£Ь..., -]=£п, £{ = ±1,1=1,71,

\ Pi / \ Рп J

арх,...р„ — простые числа. Первые результаты принадлежат Э.К.Жимбо11, его результат по точности отвечал результату Виноградова — Полна. Он также получил закон распределения квадратичных вычетов и невычетов на очень коротком промежутке.

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

В 1987 г. A.A. Карацуба12, получил результат о совместном распределении вычетов и невычетов в арифметических последовательностях;^ а, р + Ь, где р пробегает последовательность простых чисел таких, что р = a (mod q), где q также простое число.

В 1988 г. О.В. Попов рассмотрел задачу о распределении квадратичных вычетов и невычетов в последовательности бесквадратных чисел. Он получил следующий результат. Пусть 0 < е < Í = е2/32, р — простое число. Тогда для х > pi+2S+£ число квадратичных вычетов по модулю р в последовательности бесквадратных чисел, не превосходящих X, равно

\x + o{Xp-¡).

Теоретико-числовые методы играют также важную роль в криптографии с открытым ключом. Ее основы были заложены в работах У. Диффи и М.Е.Хеллмана13 и Р. Ривеста, А. Шамира и JI. Адельмана14, последняя из которых посвящена известному протоколу RS А.

Одним из протоколов с открытым ключом является протокол «Ментальный покер», разработанный в 1976 г. также Р. Ривестом, А. Шамиром и JI. Адельманом15.

Важнейшим свойством символов Лежандра и Якоби является квадратичный за-

" 9.К. Жимбо О распределении значений модулей неполных сумм Гаусса // Вестник Моск. ун-та. Сер. 1, Математика. Механика. 2001. №2. С.66-67.

12A.A. Карацуба О суммах характеров с простыми числами // Докл. АН СССР. 1970. Т.190. №3.

Í3M.E. Hellman, W.Diffie New directions in cryptography // IEEE Transaction on Information Theory, vol. 22, 1976, p. 644-654,

uR.L.Rivest., A.Shamir, L. Adle.man. A method for obtaining digital signatures and public-key crypt,osystems // Communications of the ACM. New York, NY, USA: ACM, 1978. V. 21. №2. 1978. P. 120-126.

UR.L.Rivest, A. Shamir, L.Adleman. Mental poker // Mathematical Gardner. 1981. P. 37-43.

кон взаимности. Одно из возможных доказательств этого факта использует свойства сумм Гаусса (см., например, книгу16).

Проблема вычисления одномерных сумм Гаусса хорошо известна и неоднократно рассматривалась в литературе. Так, даже в учебной литературе17 рассмотрено применение формулы суммирования Пуассона к простому случаю, когда коэффициент при квадратичном члене равен единице. В других монографиях18 рассмотрена та же ситуация, и предложена другая процедура их вычисления, основанная на общих свойствах полных сумм и символов Якоби. Многомерный случай вычисления бесконечных экспоненциальных сумм рассматривался у Э. Ландау19, однако используемая в этой работе процедура не может быть напрямую применена к рассматриваемой задаче для конечной суммы Гаусса.

Одним из направлений теории чисел являются также исследования по теории моментов арифметических функций и нахождение законов распределения сумм Гаусса, Клоостермана, сумм характеров и т. д. В этом направлении стоит отметить результаты В.Н. Чубарикова и Э.К. Жимбо?0'21, а также В.Н. Чубарикова и Р.Н. Бояринова22, И.С.Тимергалиева и Р.Н. Бояринова23.

Цель и задачи исследования

Получение новых оценок для задач о распределении квадратичных вычетов и невычетов в различных совместно распределенных последовательностях (арифметических прогрессиях и последовательности бесквадратных чисел). Получение арифметических подходов к атаке на один криптографический протокол. Вычисление точного значения многомерной суммы Гаусса в особом случае. Получение закона распределения значений очень коротких усредненных сумм Гаусса.

16Г. Девенпорт Высшая арифметика. Введение в теорию чисел. — М.: Наука. Гл. ред. фия.-мат. лит. — 1965. - 176 с.

17Г.Я. Архипов, В.А. Садовничий, В.Н. Чубариков Лекции по математическому анализу. — М.: Дрофа. - 2003. - 640 с.

18Н.М.Коробов Тригонометрические суммы и их приложения. — М.: Наука. Гл. ред. физ.-мат. пит,— 1989 -240 с.

19E.Landau Handbuch der Lehre von der Verteilung der Primzahlen. Teubner. 1909. 961 p.

2аЭ.К.Жимбо, В.Н. Чубариков Об распределении арифметических функций по простому модулю// Дискр. матем. 2001. №2. С.47-58.

21Э.К.Жимбо, В.Н. Чубариков Об асимптотических распределениях значений арифметических функций // Доклады академии наук. Т. 377, №2, 2001. С. 156-157.

25Р.Н. Бояринов, В.Н. Чубариков О распределении значений функций на последовательности Фибоначчи //Доклады академии наук. Т. 379, Ж, 2001. С. 9-11.

"И.С. Ъшергалиев, Р.Н. Бояринов О распределении значений неполных сумм Гаусса // Чебышевский сб. 2013. 14:3. С. 127-133.

Методы исследования

В работе применяются методы аналитической теории чисел, комплексного анализа и теории вероятностей.

Научная новизна

Результаты диссертации являются новыми и получены автором самостоятельно. Они состоят в следующем:

1. Получены законы распределения символов Якоби в последовательностях по системе различных попарно взаимно простых модулей по непрерывному промежутку и по последовательности бесквадратных чисел. Получена оценка суммы Гаусса специального вида.

2. Арифметическим методом обнаружены уязвимости одного криптографического протокола.

3. Вычислено точное значение многомерной суммы Гаусса. Найден закон распределения очень коротких усреднённых сумм Гаусса.

Теоретическая и практическая ценность

Диссертация имеет теоретический характер. Результаты диссертации представляют интерес для специалистов в области аналитической теории чисел и могут найти применение в теории чисел.

Апробация работы

Результаты диссертации докладывались на следующих научно-исследовательских семинарах:

1. Научно-исследовательский семинар «Аналитическая теория чисел» под руководством проф. Г. И. Архипова и проф. В. Н. Чубарикова в 2012—2013 гг.

2. Семинар «Арифметические функции» под руководством проф. В. Н. Чубарикова и доц. Р. Н. Бояринова в 2011—2012 гг.

3. Семинар «Арифметические методы в криптографии» под руководством проф. В. Н. Чубарикова и проф. М. П. Минеева в 2010—2011 гг.

Результаты диссертации докладывались также на следующих международных научных конференциях:

1. VII Международная научная конференция «Алгебра и теория чисел: современные проблемы и приложения», посвященная памяти профессора Анатолия Алексеевича Карацубы (г. Тула, 11—16 мая 2010 г.).

2. Международная научная конференция «Современные проблемы теории функций и дифференциальных уравнений», посвященная 85-летию академика Михайлова Л. Г. (г. Душанбе, 17—18 июня 2013 г.)

Публикации

Основные результаты диссертации опубликованы в 5 работах автора (список приведён в конце автореферата), из них 2 работы — в журналах, включённых Высшей аттестационной комиссией России в список изданий, рекомендуемых для опубликования основных научных результатов диссертаций на соискание ученой степени кандидата и доктора наук.

Структура и объем диссертации

Диссертация состоит из введения, трёх глав и списка литературы, насчитывающего 45 наименований. Объём диссертации составляет 71 страницу.

Краткое содержание работы

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

В первой главе «Распределении значений символов Якоби в последовательностях по системе различных модулей» рассмотрена задача о распределении квадратичных вычетов и невычетов в совместно распределенных последовательностях по различным модулям. Получено улучшение результата Э.К. Жимбо. Результат по точности отвечает результату Д. Берджесса.

Пусть <3 = т\тг ■ ■ • тпп, где шх, ш2,..., тп — попарно взаимно простые числа. Обозначим символом V (X) количество значений х < X, удовлетворяющих соотношениям

Теорема 1.5. Пусть ф = тпхгпъ... тпп, где тпх, тп2,..., т^ — попарно взаимно простые бескубические числа. Тогда для любого фиксированного е такого, что О < е < 0,0625, при <Х ¡¿¿С}, гдеш = величина

где\ЦГ{Х)\<^Е ХС1~\.

Доказательство этой теоремы существенно опирается на следующую оценку произведений символов Якоби.

Теорема 1.1. Пусть т\, ГП2,..., ть — попарно взаимно простые бескубические числа,, <5 = т\т2... ти- Далее пусть

¿Л "11 ) V т2 ) " Л гпк ) '

тогда для любого фиксированного £ такого, что 0 < е < 0,0625, при <3, где со = величина |5| >С£ ХС2~е.

Также получен более общий результат для произвольных взаимно простых модулей, но для промежутка большей длины, чем в теореме 1.1.

Теорема 1.6. Пусть ф = тп\гп2... тп, где тщ, тг,... ,тп — попарно взаимно простые числа, причем по крайней мере для одного из чисел, гщ найдется такое простое р, что р3|тг. Тогда для любого фиксированного е такого, что 0 < е < 0,15625, при < X < С}, где и> — 4е, величина

где |ТУ(Х)| <£ ХСЗ-Ъ.

Пусть Р (X) — количество бесквадратных значений х < X, удовлетворяющих соотношениям

+ аЛ _ /х + а,

\ т1 ) ' V тп

Теорема 1.7. Пусть <5 = ГП1Ш2... тп, где т\, тпг,..., тп — попарно взаимно простые бескубические числа. Тогда для любого фиксированного £ такого, что 0 < £ < 0,0533, при < X < С}, где и = величина

где \W(X)\ XQ-г.

Теорема 1.8. Пусть Q = ТП\ТП2... тпп, где ттц, Ш2,..., ш„ — попарно взаимно простые числа, причем по крайней мере для одного из чисел пц найдется такое простое р, чтор3\тп{. Тогда для любого фиксированного е такого, что 0 < е < при Q*+p < X ^ Q, где р = бе, величина

где |WpO| «£ XQ-т.

Вторая глава диссертации «Уязвимость протокола „Ментальный покер"» посвящена возможности атаки этого протокола, существенно использующей свойства квадратичных вычетов и невычетов.

Приведем краткое описание атакуемого протокола.

Два абонента Л и В раздают карты а, 0 и 7 следующим образом: Л и В получают по одной карте, и одна карта отправляется в прикуп. При этом должны соблюдаться следующие условия:

1) каждый игрок может получить любую из трех карт а, р и 7 с равными вероятностями;

2) каждый игрок знает только свою карту;

3) в случае спора можно пригласить судью и выяснить кто прав, а кто виноват;

4) при раздаче карт никто не знает, кому какая карта досталась (хотя раздача происходит по открытой линии связи и наблюдатель £ может записать все передаваемые сообщения).

Участники выбирают некоторое большое простое число р и три различных случайных числа cti, /?i и 7i, которыми кодируются карты а, /3 и 7 соответственно, причем эта информация известна всем. Затем Л выбирает случайным образом число са, взаимно простое с.р — 1, и строит такое число йл, что с Ad а = 1 (mod р— 1). Игрок В также аналогичным образом строит пару чисел св и dв, такую, что свйв = 1 (mod р — 1). Эти числа каждый игрок держит в секрете.

1-й шаг. Абонент Л вычисляет числа «1 = а\А (mod р)\ иг = ¡3[А (mod р); и3 = 7\А (mod р) и высылает их игроку В, предварительно перемешав их случайным образом.

2-й шаг. Абонент В получает три числа, выбирает случайно одно из полученных чисел, например U2, и отправляет его абоненту Л по линии связи. Это и будет та карта, которая достанется Л в процессе раздачи. Абонент Л, получив это сообще-

ние, может вычислить щ = udxA = ß\AdA = ßi (mod p), то есть он: узнает, что ему досталась карта ß.

3-й mar. Абонент В вычисляет для оставшихся двух чисел vi = itjB (mod р). Уз = исъв (mod р) и отправляет их абоненту Л.

4-й шаг. Абонент Л выбирает случайно одно из полученных чисел, например Ui, вычисляет число w\ = vfA (mod р) и отправляет это число обратно В. Абонент В вычисляет число z^ = wda (mod р) и узнает свою карту 2 = wdB = = uCBdBdA ^ acAcBdAdB ^ ^ (mod р). Карта, соответствующая vz, отправляется в прикуп.

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

Третья глава диссертации «О вычислении суммы Гаусса специального вида» посвящена вычислению полной суммы Гаусса с квадратичной формой в показателе степени, у которой коэффициенты взаимно просты со знаменателем. Доказана следующая теорема.

Теорема 3.1. Пусть Q — нечетное число, коэффициенты квадратгтной формы Т(х 1,...,х„) попарно взаимно просты cQ, D — определитель матрицы квадратичной формы Т(:Ei,..., хп), и

тогда

Доказана также следующая теорема о распределении значений коротких усредненных сумм Гаусса.

Теорема 3.2. Пусть

x+h x+h / , 4N

ш- £ £ х(п

n=x+l !7l=X+l \ Г /

где р — простое, (а,р) = 1, числа х,к — целые в пределах 0^х<ри0</г<р, а х ~ комплексный характер по модулю р.

Тогда при р —> +оо, поскольку Л(р) +оо и 0 величина £ = £{Ь,,р) =

асимптотически имеет экспоненциальное распределение с параметром

h , \ — 2 Л - 2.

Благодарности

Автор приносит благодарность научному руководителю профессору В. Н. Чуба-рикову за постановку задач и внимание к работе.

Публикации автора по теме диссертации

[1] Копьев Д. В. О вычетах и невычетах по системе модулей // Докл. АН. Т. 453, № 2, 2013. С. 136-137.

[2] Копьев Д. В., Минеев М. П., Чубариков В. Н. О некоторых арифметических подходах к задачам криптографии // Современные проблемы математики и механики. Том 3. Математика. Выпуск 1. Под редакцией Т. П. Лукашенко и В. Н. Чубарикова. М.: Изд-во МГУ, 2009. 369 с. С. 55-64.

[3] Копьев Д. В. Об уязвимости одного криптографического протокола. Вестник Моск. ун-та. Серия 1. Математика. Механика. № 1. 2009. С. 55—56.

[4] Копьев Д. В. О «Ментальном покере» // Материалы VII Международной научной конференции «Алгебра и теория чисел: современные проблемы и приложения», посвященная памяти профессора Анатолия Алексеевича Карацубы. Тула: Изд-во ТГПУ имени Л. Н. Толстого. С. 104.

[5] Копьев Д. В. О распределении значений символов Якоби в последовательностях по системе различных модулей // Материалы международной научной конференции «Современные проблемы теории функций и дифференциальных уравнений», посвященной 85-летию академика АН Республики Таджикистан Михайлова Л. Г. (Душанбе, 17-18 июня 2013 г.). С. 75-78.

В работе [2] Д. В. Копьеву принадлежит параграф «Взлом одного криптопро-токола с помощью арифметических функций».

Отпечатано в отделе оперативной печати Геологического ф-та МГУ Тираж (00 экз. Заказ №22

Московский государственный университет имени М.В.Ломоносова Механико-математический факультет

на правах рукописи

04201458477 УДК 511.35

Копьев Дмитрий Викторович

Квадратичные вычеты и невычеты и их приложения

01.01.06 — математическая логика, алгебра и теория чисел

диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель: доктор физико-математических наук, профессор В. Н. Чубариков

Москва - 2013

Содержание

Обозначения 4

Введение 6

1 Распределении значений символов Якоби в последовательностях по системе различных модулей 18

1.1 Вспомогательные леммы и утверждения..............18

1.2 Оценки вспомогательных сумм...................20

1.3 Доказательство теоремы д^я случая бескубических модулей . . 31

1.4 Доказательство теоремы в рбщем случае .............32

1.5 Распределение квадратичных вычетов и невычетов в последовательностях бесквадратных чисел.................34

2 Уязвимость протокола ,Дентальный покер" 39

3 О вычислении суммы Гауссу специального вида. 44

3.1 Вспомогательные леммы и утверждения..............44

3.2 Вычисление суммы Гаусса с квадратичной формой в показателе степени ................................55

3.3 Распределение значений очень коротких усредненных сумм Гаусса.................................58

Литература 65

Используемые обозначения

В диссертации используются следующие обозначения:

1 если а — квадратичный вычет по модулю р\

— 1 если а — квадратичный невычет по модулю р;

О если р\а.

— символ Лежандра;

{я) =

Р1,Р2, • ■ • ,рп — простые числа; е{а) = е2пга;

[ж] — целая часть вещественного числа х; {а;} = х —[х] ~ дробная часть числа х\

символ Якоби, где ф = Р1Р2 ■ ■. рп, а

1, если п = 1;

/¿(п) = (—1)г, если п = рур2 ■ ■ .рг, Р1 — простые числа;

О, если р2 | п для некоторого простого числа р — функция Мёбиуса;

1, если п бесквадратное;

Ап) = |

I 0, в противном случае — характеристическая функция множества бесквадратных чисел (чисел, не делящихся на квадрат простого числа).

Записи /(ж) = 0(д(х)) (символ Э.Ландау) и /(ж) <С д(х) (символ И.М.Виноградова) при х —> оо означают, что существуют положительные числа С и жо, такие, что |/(ж)| ^ Сд(х) при ж ^ жо-

Введение

Настоящая диссертация относится к аналитической теории чисел. Одними из важнейших объектов исследования этой области математики являются квадратичные вычеты и невычеты. Если число а взаимно просто с числом т и сравнение х2 = a (mod т) разрешимо, то а называется квадратичным вычетом по модулю га, если данное сравнение неразрешимо, то а называется квадратичным невычетом по модулю га. А. Лежандр ввел специальный символ для обозначения квадратичных вычетов и невычетов по простому модулю р, принимающий значения ±1.

а

1 если а — квадратичный вычет по модулю

-1

если а — квадратичный невычет по модулю р;

О если р\а.

Само понятие квадратичного вычета было введено Л.Эйлером, хотя пер-

вые результаты для сравнений второй степени были получены еще П. Ферма.

П. Ферма показал, при каких условиях на модуль р сравнение х2 = —1 (mod р) имеет решение, т.е. при каких условиях — 1 будет квадратичным вычетом. С помощью символа Лежандра его результат можно сформулировать следующим образом:

1 если р = I (mod 4); — 1 если если р = 3 (mod 4).

а Л. Эйлер нашел критерий разрешимости сравнения х2 = 2 (mod р). В 1801 г. К.Ф.Гауссом [2] было опубликовано первое полное доказательство квадратичного закона взаимности, сформулированного в 1783 г. Л. Эйлером [1]: если р и q — простые нечетные числа, то

© - (3 •

В 1837 г. К. Якоби обобщил символ Лежандра на случай нечетного составного модуля: пусть Р = р\р2. • - рп ~~ разложение нечетного числа Р на простые сомножители и а — взаимно просто с Р, тогда

I

Одной из важнейших задач теорир чисел является задача об оценке наименьшего квадратичного невычета^ по модулю р. И.М.Виноградов первым

получил результаты в этом направлении. Он доказал [8], чтопр < р2^ In2 р.

В 1952 г. Г. Дэвенпорт, П. Эрдеш [34] улучшили оценку Виноградова для наи-

1 1

меньшего квадратичного невычета, показав, что пр < р^ lnv? р. В 1957 г.

Д. Берджесс [30] также улучшил результат И.М.Виноградова. Он показал, — +€

ЧТО Пр < р4^ .

В предположении справедливости гипотезы Римана Ю.В. Линником [22] была получена следующая оценка наименьшего квадратичного невычета пр = 0(ре). В 1952 г. Н.К. Анкени [29] улучшил результат Ю.В. Линника и показал, что в предположении справедливости гипотезы Риманапр = 0(log2p).

Принципиальным шагом в нахождении порядка наименьшего квадратичного невычета, представляющим самостоятельный интерес, является решение задачи о распределении квадратичных вычетов и невычетов на коротком промежутке. Обратим внимание, что согласно теореме Гаусса, в полной системе вычетов половина из них будет квадратичными вычетами, а другая половина — квадратичными невычетами. Задачу о распределении квадратичных вычетов и невычетов на крротком промежутке возможно меньшей длины поставил в 1914 г. И.М.Виноградов. И.М.Виноградов [7] и Г. Полиа [38] независимо друг от друга доказали, что на промежутке длины порядка у/р\пр асимптотически поровну квадратичных вычетов и невычетов.

В 1957 г. Д. Берджесс [30] улучщил результат И.М.Виноградова, он пока-

зал, что квадратичных вычетов и невычетов будет асимптотически поровну

на промежутке длины превосходящей р* .

В.Н. Чубариков сформулировал многомерный аналог задачи Виноградова на коротком промежутке о количестве вычетов х < X таких, что

х + а\ \ ( х + а.

- = еп, £{ = ±1,г = 1 ,п,

V Р1 / V Рп )

а Ръ • • -Рп — простые числа. Первое результаты принадлежат Э.К. Жимбо [12], его результат по точности отвечал результату Виноградова — Полиа. Он также получил закон распределения квадратичных вычетов и невычетов на очень коротком промежутке.

В главе 1 «Распределении значений символов Якоби в последовательностях по системе различных модулей» рассмотрена задача о распределении квадратичных вычетов и невычетов в совместно распределенных последовательностях по различным модулям. Получено улучшение результата Э.К. Жимбо. Результат по точности отвечает результату Д. Берджесса.

Обозначим символом V (X) количество значений х < X, удовлетворяющих соотношениям

гс + аЛ _ : / х + ап \ _ к ГП1 ) 1}"'\шп)

Теорема 1.5 Пусть ф = 77717772... тп, где 7711,7712,..., тп — попарно взаимно простые бескубические числа. Тогда для любого фиксированного с такого, что 0 < е < 0,0625, при < X ^ С}, где и) = величина

где \УУ{Х)\ <£

Доказательство этой теоремы существенно опирается наследующую оценку произведений символов Якоби.

Теорема 1.1 Пусть 7711,7712,... ,гпк — попарно взаимно простые бескубические числа, = 77717772.. .т^. Далее пусть

5 = Е

х + аА / х + <22 \ (х + а^

^у ч т1 / V т2 / V гпк у

х<Х 4 ' ' 4

тогда для любого фиксированного е такого, что 0 < г < 0, 0625, при (< X ^ где и = величина |£| <Се Х(^)~£.

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

Теорема 1.6 Пусть ф = гп\т2 ... тп, где 7771,7772, • • •,тп ~~ попарно взаимно простые числа, причем по крайцей мере для одного из чисел тг найдется

*

такое простоер, что ръ\т,1. Тогда для любого фиксированного е такого, что

О < £ < 0,15625, при Q< X ^ Q, где ш — 4е, величина

где |W(X)| <С£ XQ-T,

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

В 1987 г. A.A. Карацуба [17], получил результат о совместном распределении вычетов и невычетов в арифметических последовательностях р-\- а, р + Ь, гдер пробегает последовательность'простых чисел таких, чтор = a (mod q), где q также простое число.

В 1988 г. О.В. Попов [24] рассмотрел задачу о распределении квадратичных вычетов и невычетов в последовательности бесквадратных чисел. Он получил следующий результат. Пусть 0 < е ^ 6 = £2/32, р — простое число. Тогда для х > p*+2S+£ число квадратичных вычетов по модулю р в последовательности бесквадратных чисел, не превосходящих X, равно

^Х + 0(Хр~6).

7Г

I

В настоящей диссертации рассматривается следующее обобщение этой задачи. Пусть Q = mi77i2... тп, где mi, rri2, ■ ■ ., тп — попарно взаимно простые

числа, Е (X) — количество бесквадратных значений х < X, удовлетворяющих соотношениям

/х + аЛ / ж + а

V 7711 ) £1'"'\ГПп

Теорема 1.7 Пусть ф = 77717772... тп, где т\, т2,..., тп — попарно взаимно простые бескубические числа. Тогда для любого фиксированного £ такого, что 0 < £ < 0,0533, при (¿*+ш+2£ < X ^ где и = величина

где \№{Х)\ <£ Хд-г.

Теорема 1.8 Пусть ф = 77717772.. .'тП) где 7711, гп2,..., тп — попарно взаимно простые числа, причем по крайцей мере для одного из чисел т,{ найдется такое простое р, чтор3\гПг. Тогда для любого фиксированного £ такого, что

I

0 < £ < при < X ^ где р — б£, величина где \\¥{Х)\

Теоретико-числовые методы играют также важную роль в криптографии с открытым ключом. Ее основы были заложены в работах У. Диффи и

М.Е.Хеллмана [36] и Р. Ривеста, А. Шамира и Л.Адельмана [39], последняя из которых посвящена известному протоколу RSA.

Одним из протоколов с открытым ключом является протокол «Ментальный покер», разработанный в 1976 г. также Р. Ривестом, А. Шамиром и Л. Адельманом [40]. Он состоит в следующем.

Два абонента Ли В раздают карты а, ¡3 и 7 следующим образом: Л и В получают по одной карте, и одн^ карта отправляется в прикуп. При этом должны соблюдаться следующие условия:

1) каждый игрок может получить любую из трех карт а, ¡3 и 7 с равными вероятностями;

2) каждый игрок знает только срою карту;

i

3) в случае спора можно пригласить судью и выяснить кто прав, а кто

i

виноват;

4) при раздаче карт никто не зн^ет, кому какая карта досталась (хотя раздача происходит по открытой линии связи и наблюдатель S может записать все передаваемые сообщения).

Участники выбирают некоторое большое простое число р и три различных случайных числа оц, (3\ и 71, которыми кодируются карты а, (3 и 7 соответственно, причем эта информация известна всем. Затем Л выбирает случайным образом число с а-, взаимно простое с р — 1, и строит такое число

¿л, что с Ad а = 1 (mod р — 1). Игрок В также аналогичным образом строит пару чисел св и ds, такую, что csds = 1 (mod р — 1). Эти числа каждый игрок держит в секрете.

1-й шаг. Абонент Л вычисляет числа щ = а\А (mod р); щ = ¡3\А (mod р)\ щ = (mod р) и высылает их игроку В, предварительно перемешав их случайным образом.

2-й шаг. Абонент В получает три числа, выбирает случайно одно из полученных чисел, например щ, и отправляет его абоненту Л по линии связи. Это и будет та карта, которая достанется Л в процессе раздачи. Абонент Л, получив это сообщение, может вычислить U2 = udA = fi^AdA = (mod p), то есть он узнает, что ему досталась царта /3.

3-й шаг. Абонент В вычисляет для оставшихся двух чисел v\ = и\в (mod р), vз = (mod р) и отправляет их абоненту Л.

4-й шаг. Абонент Л выбирает случайно одно из полученных чисел, например г>1, вычисляет число w\ = vdA\ (mod р) и отправляет это число обратно В. Абонент В вычисляет число z\ = wde (mod р) и узнает свою карту z = wdB = vfAdB = u\BdBdA = a\ACB*AdB = ai (mod p). Карта, соответствующая г>з, отправляется в прикуп.

Вторая глава диссертации «Уязримость протокола „Ментальный покер"»

j

посвящена возможности атаки на э?от протокол, существенно использующей

свойства квадратичных вычетов и невычетов. Показано, что при неудачном выборе чисел, кодирующих карты, можно отследить перемещение карт по столу. Также показано, что даже в случае правильного выбора кодирующих чисел абонент Л может попытаться обмануть абонента В, ив случае успеха он с вероятностью | будет знать распределение карт на игровом столе.

Важнейшим свойством символо^ Лежандра и Якоби является квадратичный закон взаимности. Одно из возможных доказательств этого факта использует свойства сумм Гаусса (см., например, книгу [11]).

Проблема вычисления одномерных сумм Гаусса хорошо известна и неоднократно рассматривалась в литературе. Так, в книге [4] рассмотрено применение формулы суммирования Пуарсона применительно к простому случаю, когда коэффициент при квадратичном члене равен единице. В монографии [20] рассмотрена та же ситуация, и предложена другая процедура их вычисления, основанная на общих свойствах полных сумм и символов Якоби.

Третья глава диссертации «О вычислении суммы Гаусса специального вида» посвящена вычислению полно^ суммы Гаусса с квадратичной формой в показателе степени, у которой коэффициенты взаимно просты со знаменателем. Доказана следующая теорема,

Теорема 3.1. Пусть <5 — нечещное число, коэффициенты квадратичной

формы Т(х 1,..., хп) попарно взаицно просты с И — определитель мат-

\

рицы квадратичной формы Т(х\,.. ., хп), и

<2 Я

Т{хъ ■ • •, хп)

О

тогда

Многомерный случай вычисления бесконечных экспоненциальных сумм рассматривался в [37], однако используемая в этой работе процедура не может быть напрямую применена к рассматриваемой в диссертации задаче для конечной суммы Гаусса.

Одним из направлений теории чисел являются исследования по теории моментов арифметических функций и нахождение законов распределения сумм Гаусса, Клоостермана, сумм характеров и т. д. В этом направлении стоит отметить результаты В.Н. Чубарикова и Э.К.Жимбо [12, 13, 14], а также В.Н. Чубарикова и Р.Н. Бояринова [5], И.С. Тимергалиева и Р.Н. Бояринова

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

[26].

Теорема 3.2. Пусть

х+к х+к

х-гп / / , \ \

ад= Е Е х(п+т)е(а-^1),

п=х+\ т=х+1 \ Р /

где р — простое, (а,р) = 1, числа х, И — целые в пределах 0 ^ х < р и

О < Н < р, ах ~ комплексный характер по модулю р.

Тогда при р —> +оо, поскольку Н(р) +оо и —> 0 величина £ =

£(1г,р) = Щг- асимптотически имеет экспоненциальное распределение с ьл

параметром А =

Основные результаты, полученною в настоящей диссертации, опубликованы в работах автора [41, 42, 43, 44, 45].

В заключение автор приносит благодарность научному руководителю профессору В.Н. Чубарикову за постановку задач и внимание к работе.

Глава 1

Распределении значений символов Якоби в последовательностях по системе различны^ модулей

1.1 Вспомогательные лепимы и утверждения

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

Лемма 1.1 (Китайская теорема об остатках) Пусть целые числа 7П1, ттг.2, • • •) тг попарно взаимно щосты и М = 77117712 ... гпг. Тогда система сравнений

a = ai (mod m\) < :

a = ar (mod mr)

к

имеет единственное решение a (mod М), т.е. можно указать ровно один класс вычетов х = a (mod М), удовлетворяющий этой системе сравнений.

Лемма 1.2 (теорема Берджеоса) Пусть Q € N и X - неглавный характер Дирихле по модулю Q. Пцсть е — фиксированное положительное число и г € N. Далее пусть Q — бескубическое число или г = 2, для любых целых N и Н (Н > ОJ

N+X

Sx{N)= £ х(я) «V Х1-1/^!)/^

x=N+1

ЛЕММА 1.3 Для количества бесцвадратных чисел, не превосходящих N имеет место асимптотическая формула

±—' : 7Г

n<N

1.2 Оценки вспомогательных сумм

ТЕОРЕМА 1.1 Пусть т1,га2,..., га/с — попарно взаимно простые бескубические числа, О, = ТП\ТП2 ■. ■ гпк- Далее пусть

X + ai\ / X + <22 \ (X + <2fc

SY v mi / V 1712 / \ mk J

x<X

тогда для любого фиксированного е такого, что 0 < £ < 0,0625, при < X ^ Q, где со = величина l^l -Се XQ~£.

Доказательство. Рассмотрим следующую систему сравнений:

а = а\ (mod mi); < :

а = а£ (mod m^).

х

По китайской теореме об остатках эта система разрешима и =

(inf) ' • • •' (^mf1) = (^nf)' а значИт наша сумма S может быть представлена в следующем виде:

с _ v^ fx + а\ fx + а\ fx + а\ _ ^ fx + а\

=h w Urj • • • UrJ= h ■

Поскольку Q — произведение k попарно взаимно простых бескубических чисел, следовательно, Q — число бескубическое, а значит к S можно применить

утверждение леммы 1.2.

5 <£,г х1~1/гС}{г+1)/Аг2+£.

Для получения нетривиальной оцецки потребуем х1~1/гС}<'г+1УАт2~1г£ < X. Тогда получим

причем, по неравенству Коши, значение

д1/4+^ будет

приниматься только

ПРИ Г =

Поскольку в лемме 1.2 допустимы только натуральные значения г поло-где [гс] — целая часть числа х.

жим г =

Тогда

Ш/О 4Ш

_1_1п X

.мм.

^ "Ш'"0, ад

(3 П57Л = ХЯ

Положив X = и потребовав, чтобы правая часть последнего равен-

ства была меньше получим

1

1 /1 \ 4+Ы +

2у/ё

+ 1

2у/е

Отсюда имеем

ш >

2^/ё

+ 2е

+ 2е

2у/ё \ 2у/е) /

где {ж} — дробная часть числа х.

Поскольку {ж} < 1, при е < \ имеем, 2 — 4у/е > 2 — 4у/е. Следова-

тельно

2 — 4у/ё

>ГеШ ^

<

уГе

2-4уД

+ у/1 + 2е =

Зу/е - 8>£у/ё Зу/е

2 — 4у/ё 2 — 4у/е'

Тогда, если и > |5| < Хд~£.

1 ^ Так как по условию С^* < ], поэтому и < следовательно для получения допустимых значений и должнр быть выполнено следующее неравенство

Зу/ё 3

2 — 4у/ё 4'

Оно выполняется при 0 < е < 0,Р625. Теорема доказана.

ТЕОРЕМА 1.2 Пусть га^гаг,... ,чпк ~~ попарно взаимно простые числа,

ф = т1т2 . • • 777/г, X < причем по крайней мере для одного из чисел Шг найдется такое простое р, что р*\т{. Далее пусть

х + аЛ fх + а2\ (x + CLk

х<Х V т1 / V m2 / V тк

тогда для любого фиксированного е такого, что 0 < е < 0,15625, при д§+" < X < Я, где со = 4е, величина |5| <С£ ХС2~£.

Доказательство. Рассмотрим следующую систему сравнений:

а = a,} (mod mi);

а = (mod rrik).

v

По китайской теореме об остатках эта система разрешима (см. например [10])

и (нё1) = (S2) '' • •' = (Й?)> а значит наша с^мма 5 может быть

представлена в следующем виде:

с _ v-^ (х + а\ (х + а\ (х + а\ _ v^ (х + а\

=h w w''' UrJ=h v^n'

Применим к S утверждение леммь| 1.2.

1 3 Г-Г-.

Для получения нетривиальной оценки потребуем < X. Тогда полу

чим

X > дК

Положим и = 4е,