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

• Копьев, Дмитрий Викторович
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Копьев, Дмитрий Викторович

Содержание

Обозначения

Введение

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

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

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

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

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

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

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

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

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

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

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

Литература

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

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

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е, тогда при X > получим

Теорема доказана.

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

'( х + а\\ ( х + аг \ ( х + ак

^У х Ш1 / V ш2 / \ ГПк х<Х 4 ' 4 4

где штрих в сумме означает, что суммирование ведется только по бесквадратным числам, тогда для любого фиксированного е такого, что 0 < £ < 0,0533, при д*+ш+2е < X ^ С), где и = ^д, величина |5| <£ Х€}~£.

Доказательство. Поскольку

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

Ах) =;

0, в противном случае,

имеем

Рассмотрим следующую систему сравнений:

а = а\ (mod mi); < :

а = ajk (mod m^). По китайской теореме об остатках эта система разрешима и

х + а Л _ /х + а\ fх + (ik\ _ fх + а\ , mi ) V т\ ) ' \ тк ) V тк ) '

а значит наша сумма 5 может быть представлена в следующем виде:

+ Е Е р^) = ^ + иь

P<d<y/X к<%

р _ ^0,5

где .Г Q0,125+w/2 •

Сначала оценим вторую сумму, для этого внутреннюю сумму оценим тривиально, а для внешней суммы применим хорошо известную оценку для остатка ряда обратных квадратов:

№1« Е | = 0 (Т) = о(х°'5д°'125+-/2).

Для оценки 1Уг разобьем сумму на две: 11\ — сумма по взаимнопростым с (2, С/2 — сумма по (1 таким, что О) =1 ^ 1.

Сначала оценим С/^ применим к внутренней сумме оценку теоремы 1.1.

иг = Е "(<0 Е = Е =

(¿,сг)=1 (¿,д)=1

= £ ^ «

¿<р («¡,д)=1

Для оценки суммы С/2 заметим, чтр, при (с?2, (5) = I Ф 1, ф = Ш\

/Ы2 + а\ /ксР а\ /а\ //с + а((1')2\

I у V у VI) V

где d! — такое, что d'd = 1 (mod d\). Тогда

л2~

* = Е Е м«0Е(^) = Е(т) Е ,

7 17

= Е(у) Е Е ¿-

I |<з сг<р ло

= Е = Е «

с1<Р й<Р

Найдем значения X, при которые выполнено неравенство х0'5^0'12544^2 < додгб-ы/г-к Тогда « ХСГ6, |Ж2| <

а следовательно, и |5| <С Х(^~е.

Так как по условию (¿4+ш+2е < поэтому ш + 2е < следовательно для получения допустимых значений си должно быть выполнено следующее неравенство

4

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

ТЕОРЕМА 1.4 Пусть ГП1,ГП2,... ,\Пк — попарно взаимно простые числа, ф = ТП\ТП2 ... гпк, X < С^, причем по крайней мере для одного из чисел

гп{ найдется такое простое р, что р3\тг. Далее пусть

х + а\\ ( х + а,2

х<Х

ГП\

т2

х + ак , тк .

где штрих в сумме означает, что суммирование ведется только по бесквадратным числам, тогда для любого фиксированного е такого, что 0 < Е < ¿я> пРи < X ^ Я, где р = бе, величина ¡¿Ч ХС}~е.

Доказательство. Как и в теореме 1.3, имеем

5 =£>'(*)(

х<Х ^

х + аА / х + аг

ГП\

т2

х + а/г . тк ,

Рассмотрим следующую систему сравнений:

а = а,} (тос1 т\)]

:

а = а^ (тос! т/с).

( х+а\ \

По китайской теореме об остатках эта система разрешима и ^ (^пГ) ' • • •' (^Й?) = ) > а значат наша сумма 5 может быть представле-

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

2/ N (х + ¿Л (х + а\ (х + а\ 2 (х + а

Я

х + а

х<ХФ\х \ ^ / ¿2]х \ ч /

х<Х

^ ' ИР У * '

+ £ № £ р^) = ^ + ^

Р<й<у/Х к< —

Гле р - х1/2

Сначала оценим вторую сумму, для этого внутреннюю сумму оценим тривиально, а для внешней суммы применим хорошо известную оценку для остатка ряда обратных квадратов:

№ « XI I = ° (т) = 0(*1/203/16П

Р<й<^/Х

Для оценки У/\ разобьем сумму на две: С/х — сумма по с1, взаимнопростым с (5, С/2 — сумма по (1 таким, что (с?2, О) = I ф 1.

Сначала оценим 1/\, применим к внутренней сумме оценку теоремы 1.2.

* = Е мю Е - Е «ф

¿<р 4 4 У а<р а

= £ ^ «

й<Р

—е

Для оценки суммы С/2 заметим, что, при (¿¿2, ф) = I ф 1, Я = Ы\

/Ы2 + а\/Ы2 + а\ /а\ [к + а{(1')2\

\ I J \ ) \l / \ d\

где <i' — такое, что d'd = 1 (mod <¿1). Тогда

kd2 + а\ /а\ ^ fj\ sr^ (к + a(d')

/\2'

= Е(у) Е м^«*^ Е

/10 с/<Р /Ю с/<Р

(<ад=г Ми

= Е ЯУ = Х(3~£ Е ¿Ьге «

(¿<Р £/<Р

Найдем значения X, при которых выполнено неравенство Х1,/2(53^16+1л;//2 ^ дз/1б+^/2+г ^у/х^х^ я1+ы+2£- Тогда 1^1 < |ж2| <

а следовательно, и |5|

Так как по условию (^1+ш+2£ < С}, поэтому р = и 2е = бе < следовательно для получения допустимых значений должно быть выполнено неравенство р < |. Оно выполняется при 0 < е < р/6 = Теорема 1.4 доказана.

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

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

х + аЛ ( х + ап\

- = ..., - = еп.

, ГП1 ) \ тп I

теорема 1.5 Пусть (5 = тхгпг.. .тп, где т\, т2,..., тп — попарно взаимно простые бескубические числц. Тогда для любого фиксированного е такого, что 0 < е < 0,0625, при < X ^ С^, где и = величина

где \УУ(Х)\ Хд-4.

Доказательство. Представим У(Х) в следующем виде:

х<Х

х + а^ \ ( х + £¿¿2 \ ( х + а1к

Е

; \ ГПг2 / \ ГПгк

х<Х

где штрих во второй сумме означает суммирование по всем наборам 1 <

¿1 < ¿2 < ... < %к < п, 1 < к < п. Обозначим вторую сумму за \У(х), а

SU = Z • • ■ ™гда V(X) = £ + W(X), а

По теореме 1 имеем следующую оценку:

\S4,t2, ,J < min (тцтг2 ■ ■ -т^у6 ,тг1тг2...т1к) .

Разобьем сумму со штрихом на две = X^'i + X^» гДе суммирование в первой сумме идет по всем наборам тг1, тг2,..., тгк, для которых тчт%2... mlk < Q*, а во второй — по всем оставшимся. Количество наборов и в первой, и во второй сумме не превосходит 2П. Тогда оценивая первую сумму тривиально, а вторую — с помощью теоремы 1 1, получим

\W(X)\<XQ~l

Тем самым теорема доказана.

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

теорема 1.6 Пусть Q = т\т2 .,. тп, где mi,m2,..., mn — попарно взаимно простые числа, причем по крцйней мере для одного из чиселтг найдется такое простое р, что р3\тг. Торда для любого фиксированного е такого,

что 0 < е < 0,15625, при ф4+ш < X ^ где и> = 4е, величина

где \\¥(Х)\ .

Доказательство. Представим У(Х) в следующем виде:

где штрих во второй сумме означает суммирование по всем наборам 1 < ¿1 < ¿2 < . • • < ü < n, 1 < А; < п. Обозначим вторую сумму за W(x), а s»«.....= Z - тогда П*) = § + W(X), а

,г2, • ,4 I ■

По теореме 2 имеем следующую оценку

|5tl)l2, .,J < min (X (гпг]тг2... mlky£ ,тг1т12... тгк) .

Разобьем сумму со штрихом на две Yl' = ^'г + ^'г' гДе суммирование в первой сумме идет по всем наборам тг1,тг2,... ,тгк, для которых

з

т^тг2... гпгк < Я», а во второй —- по всем оставшимся. Количество наборов и в первой, и во второй сумме не превосходит 2п. Тогда оценивая первую сумму тривиально, а вторую — с помощью теоремы 1.2, получим

Тем самым теорема доказана.

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

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

{х + аА (х + ап\

- = £ь ..., - = £п-

\ гп\ ) \ гпп )

теорема 1.7 Пусть Я = ш1ш2 ... тп, где т\, 777-2,..., тп — попарно взаимно простые бескубические числц. Тогда для любого фиксированного £ такого, что 0 < е < 0,0533, при < X ^ Я, где и> = величина

где \УУ{Х)\

Доказательство. Представим -Р(Х) в следующем виде:

= 4 Е А*) + 4 Е(-1)Ч£г2

2Г

Х<Х

X

1<Л- V тгг / V ™г2 / V / где штрих во второй сумме означает суммирование по всем наборам 1 < < 12 < ... < гь < п, 1 < к < п. Введем обозначения

• Ак ~ Е (

V \

х агЛ ( х + агЛ ( х + а

г*:

X т у V У V Шк

2Г

Тогда, применяя лемму 1.3, получим следующее равенство

ПХ) = + Щ*),

где

По теореме 1.3 имеем следующую оценку, для 5^,12, :1к:

^»ьга, Л|«тт(ХКт12...т1к) £, тчт12... тгк)

Разобьем сумму со штрихом на две :=: + гДе суммирование в первой сумме идет по всем наборам тг1, т%2%..., т1к, для которых тг1тг2... т1к < С^*, а во второй — по всем оставшимся. Количество наборов и в первой, и во второй сумме не превосходит 2п. Тогда оценивая первую сумму тривиально, а вторую — с помощью теоремы 1.1, получим

Тем самым теорема доказана.

ТЕОРЕМА 1.8 Пусть = т\т,2 ... тп, где 777,1, 777,2,..., тп — попарно взаимно простые числа, причем по крайней мере для одного из чиселтг найдется такое простое р, что ръ\тг. Торда для любого фиксированного г такого, что 0 < £ < при < X ^ где р = бе, величина

где \\¥{Х)\ ХСГт.

Доказательство. Представим Р(Х) в следующем виде:

р(х) = к £ Ах) + 4 • • • ^ х

\ ) \ тг2 ) V ГПгк )

где штрих во второй сумме означает суммирование по всем наборам 1 < < < . • • < гк < п, 1 < к < п. Введем обозначения

v \

ОС -j- CLi^ \ / ОС CL12 \ ( ОС -f~ СЬ%к

х W>i J \ т2 J \ тк

х<Х

= к • • • £гЛг,г2„

Тогда, применяя лемму 1.3, получим следующее равенство

nx) = ~ + w(x),

где

По теореме 1.4 имеем следующую оценку для S.{

г\,г2 ,—,ik

\Sn,i2, -,ik\ < min (X (тг]тг2... тгк) £ , тчт%2... т1к) .

Разобьем сумму со штрихом на две Yl' = + Х^'г' гДе суммирование в первой сумме идет по всец' наборам тгх, тг2,..., тгк, для которых

3

тг1тг2 ... т1к < Q*, а во второй — до всем оставшимся. Количество наборов

и в первой, и во второй сумме не превосходит 2п. Тогда оценивая первую сумму тривиально, а вторую — с помощью теоремы 1.2, получим

\\¥(Х)\ <ХЯ~т.

Тем самым теорема доказана.

Глава 2

Уязвимость протокола „Ментальный покер"

В данной главе изучаются возможности атаки и обмана для игрока начинающего игру в известном криптографическом протоколе, называемом "Ментальный покер "[40].

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

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

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

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

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

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

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

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

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

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

Перейдем к атакам криптолога на данный протокол. Помимо очевидных предосторожностей при выборе простого р (оно должно быть достаточно большим, чтобы задачу дискретногр логарифмирования нельзя было решить быстро) следует соблюдать аккуратность и при выборе чисел cvi, и 71. Ясно, что ср(р) = р — 1 может довольно легко разлагаться на множители, по крайней мере 2\<р(р). Предположи^, что среди сх\, /3\ и 71 первые два числа являются квадратичными вычетами по модулю р, а последнее — квадратичным невычетом. Так как са, св , d,A и ds взаимно просты с то они нечетны, а возведение в нечетнук} степень оставляет квадратичный вычет квадратичным вычетом, а квадратичный невычет — квадратичным невычетом. Следовательно, 71 будет единдтвенным числом, которое при возведении в степень ^тр выдаст в качестве результата —1 , следовательно, 8 легко отслеживает перемещения карты 7.

s s л

Пусть теперь (р(р) = Р\Р\ ■■•Рп ■ -Наблюдатель £ проверяет, сколько будет вычетов степени рг среди а\, /3\ и 71; если такой вычет единственный или их

Список литературы диссертационного исследования кандидат наук Копьев, Дмитрий Викторович, 2013 год

Список литературы

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

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

4

[3] П.Г. Л Дирихле Лекции по теории чисел: В обработке и с добавлениями Р Дедекинда. Пер. с нем./Под ред. Б.И. Сегала. Изд. 3-е —М.: Книжный дом «Либроком». — 2009. — 3(38 с.

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

[5] Р.Н. Бояринов, В.Н. Чубариков О распределении значений функций на

последовательности Фибоначчи // Доклады академии наук. Т. 379, №1,

»

2001. С. 9-11.

[6] А.А. Бухштаб Теория чисел. Изд. 2-е, испр. —М.: Просвещение. — 1966. - 384 с.

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

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

[9] И.М. Виноградов Основы теории чисел. М.: Наука, 1972.

[10] И.М. Виноградов Метод тригонометрических сумм в теории чисел. М.: Наука, 1971.

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

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

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

»

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

[15] A.A. Карацуба Основы аналитической теории чисел. Изд. 2-е, испр. — М.: Едиториал УРСС. - 2004- - 184 с.

[16] A.A. Карацуба Суммы характеров и первообразные корни в конечных полях // Докл. АН СССР. 1908. Т. 180. №6. С. 1287-1289.

[17] A.A. Карацуба О суммах характеров с простыми числами // Докл. АН СССР. 1970. Т. 190. т. С.517-518.

[18] A.A. Карацуба Об оценках сумм характеров // Изв. АН СССР. 1970. Т.34. №1. С.20-30.

[19] A.A. Карацуба Распределение степенных вычетов и невычетов в аддитивных последовательностях // Докл. АН СССР. 1971. Т.196. №4.

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

я

[21] М.А. Лаврентьев, Б. В. Шабахр Методы теории функций комплексного переменного:Учеб. пособие ддя ун-тов.— 5-е изд., испр.— М.: Наука. Гл. ред.физ.-мат. лит., 1987.— 68§с.

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

[23] Х.Л. Монтгомери Мультипликативная теория чисел. —• М.: Мир, 1974.

[24] О. В. Попов О квадратичных вычетах и невычетах в последовательности бесквадратных чисел // Вестник Моск. ун-та. Серия 1. Математика. Механика. 1989. №5. С. 81-83',

[25] А.Г. Постников Введение в аналитическую теорию чисел. — М.: Наука. Гл. ред. физ.-мат. лит. — 1971. — 416 с.

[26] И. С. Тимергалиев, Р.П. Боярцнов О распределении значений неполных

сумм Гаусса // Чебышевский сб. 2013. 14:3. С. 127-133.

»

[27] К. Хооли Применение методов решета в теории чисел / Пер. с англ. В.Н. Чубарикова. — М.: Наукр,. Гл. ред. физ.-мат. лит. — 1987. — 136 с.

[28] А.Н. Ширяев Вероятность. ]В 2-х кн.— 3-е изд., перераб. и доп.—

М.:МЦНМО, 2004,- 928 с. '

1

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

[30] D.A. Burgess The destribution of quadratic residues and nonresidues. // Math. 1957. 4, №8, P. 106-112^

[31] D.A. Burgess On character sums and primitive roots, // Proc. London Math. Soc. (3) 1962. 12, P. 179-192.

[32] D.A. Burgess On character sums and L-series. // Proc. London Math. Soc. (3) 1962. 12, P. 193-206.

[33] D.A. Burgess On character suips and L-series, II. // Proc. London Math. Soc. (3) 1963. 13, P. 524-536.

[34] H. Davenport, P. Erdös The distribution of quadratic and higher residues // Publ. Math., Debrecen. 1952. 2, №3-4, P. 252-265.

[35] G.H. Hardy, E.M. Wright An Introduction to the Theory of Numbers // Oxford University Press. 1975. 421 p.

[36] M.E. Hellman, W.Diffie Ne^y directions in cryptography // IEEE Transaction on Information Theory, vol. 22, 1976, p. 644-654.

[37] E. Landau Handbuch der Lehre von der Verteilung der Primzahlen. Teubner. 1909. 961 p.

[38] G. Pölya Uber die Verteelung (1er quadratischen Reste und Nichtreste // Gött. Nachr. 1918. P.21-29.

[39] R.L. Rivest, A.Shamir, L. Adleman. A method for obtaining digital signatures and public-key cryptosystems // Communications of the ACM. New York, NY, USA: ACM, 1978. V. 21. №2. 1978. P. 120-126.

[40 ] R.L. Rivest, A.Shamir, L. Adleman. Mental poker // Mathematical Gardner. 1981. P. 37-43.

Работы автора по теме диссертации

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

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

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

[44] Д.В. Копьев О "Ментальном покере". Материалы VII Международной

научной конференции "Алгебра и теория чисел: современные проблемы

и приложения посвящцнная памяти профессора Анатолия Алексеевича

Карацубы. Тула: Изд-во ТГПУ имени Л.Н. Толстого. С. 104.

i

' 70

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