Квадратичные вычеты. Символ Лежандра

    Ранее мы рассматривали сравнения первой степени вида . Были установлены условия, при которых эти сравнения имеют решения, и найдены способы нахождения этих решений. Теперь рассмотрим квадратичные сравнения, то есть сравнения вида . Заметим, что сравнение такого вида можно упростить. Для этого положим  и решим сравнение первой степени  относительно . Получим сравнение вида , или, что то же самое,

                                                      (15.1)

Поэтому далее будем изучать квадратичные сравнения вида (15.1).

    Определение 15.1. Пусть p нечетное простое число, . Число a называется квадратичным вычетом по модулю p, если сравнение имеет решение. Если это сравнение решений не имеет, то число a называется квадратичным невычетом по модулю p.

    Замечания. 1) Очевидно, что число  является квадратичным вычетом по модулю p для любого числа p. Поэтому в дальнейшем число  исключим из рассмотрения.

2) В определении 15.1 простое число p предполагалось нечетным, чтобы исключить тривиальный случай, когда . Действительно, сравнение всегда имеет решение. Легко проверить, что в случае, когда число a четное, любое четное число x является решением данного сравнения, а в случае, когда число a нечетное, любое нечетное число x является решением данного сравнения.

    При изучении квадратичных сравнений выделяют две задачи.

1) Задача распознавания: как узнать, является ли число a квадратичным вычетом по модулю p?

2) Задача поиска решений: как решить квадратичное сравнение?

Мы рассмотрим только задачу распознавания как более легкую, но, при

этом, имеющую практическое применение.

    Теорема 15.1. Пусть p – простое нечетное число. Тогда среди чисел из множества  ровно половина является квадратичными вычетами по модулю p.

Доказательство. 1) Число  – четное, значит,  – целое. Разобьем множество A на пары чисел вида , .

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

 Докажем, что квадраты чисел из разных пар несравнимы по модулю p. Рассмотрим сравнение , при очевидном условии, что . Предположим, что оно выполняется для некоторого k,  где . Тогда . Поскольку число p простое, справедливо . Но , значит . Тогда выполняется . При этом  и , следовательно, . Тогда утверждение  может быть выполнено только в случае, когда , или , что невозможно. Следовательно, сделанное предположение о сравнимости по модулю p квадратов двух чисел из разных пар, неверно.

2) Множество A состоит из всевозможных вычетов по модулю p (за

исключением 0). Мы доказали, что каждой паре ,  соответствует свой квадратичный вычет, а разным парам соответствуют разные квадратичные вычеты. Поскольку число пар равно , то число квадратичных вычетов равно , то есть ровно половина чисел из множества A являются квадратичными вычетами. Теорема доказана.

Пример. Пусть . Рассмотрим множество  и пары чисел из A вида , : . Тогда справедливы сравнения:

, , . При этом , , . Таким образом, числа 1, 2 и 4 являются квадратичными вычетами по модулю 7, а числа 3, 5 и 6 – квадратичными невычетами по модулю 7.

При помощи теоремы 15.1 можно решать задачу распознавания, если числа a и p невелики. Рассмотрим способ решения этой задачи для случая произвольных значений a и p.

Пусть p – простое нечетное число. Рассмотрим некоторые частные случаи для значений a.

Рассмотрим сначала случай, когда . Очевидно, что для любого p число 1 является квадратичным вычетом по модулю p. Действительно, сравнение имеет решения  и .

Рассмотрим теперь случай, когда  и выясним, в каких случаях сравнение  имеет решение.

Если , то . Тогда , а, значит, сравнение  не имеет решений.

 Если , то . Значит, выполняются условия теоремы Ферма, тогда . Пусть x – решение сравнения . Тогда

.

Если число  – четное (т. е. ), то , что верно по теореме Ферма.

    Если число  – нечетное (т. е. , но  ), то . Но по теореме Ферма . Из двух последних сравнений следует, что , что неверно в силу того, что .

Таким образом, мы получили, что число  является квадратичным вычетом по модулю p, в случае, когда число  – четное, и квадратичным невычетом, когда число  – нечетное.

    Рассмотрим случай, когда . Примем без доказательства факт, что сравнение имеет решение в случае, когда число  четное (т. е. ), и не имеет решений в противном случае.

    Определение 15.2. Рассмотрим квадратичное сравнение . Символом Лежандра называется величина, обозначаемая , определяемая следующим образом:

если , то ;

если , то , в случае, когда a является квадратичным вычетом по модулю p и , в случае, когда a является квадратичным невычетом по модулю p.

Замечание. Если , то квадратичное сравнение , очевидно, имеет решение. Действительно, . Это утверждение выполняется для любого значения x, кратного числу p. Следовательно, в случае, когда , a является квадратичным вычетом по модулю p.

    Символ Лежандра читается: символ Лежандра a по p, при этом a называется числителем символа, а b – знаменателем.

    Исследуя случаи ,  и , мы установили, что , , .

 

                          Свойства символа Лежандра

Свойство 1. Если , то .

Доказательство. 1) Пусть . Тогда . Но .

2) Пусть . Это означает, что найдется такое число , что . Тогда , следовательно, .

3) Пусть . Докажем, что . Предположим, что это утверждение неверно. Тогда либо и, как следует из пункта 1) доказательства, , что неверно, либо и, как следует из пункта 2) доказательства, , что также неверно. Следовательно, .

Свойство 2. Если , то .

Доказательство. Из условия следует, что . Поскольку символ Лежандра принимает значения равные только 0, 1 или , разность может принимать значения равные , или 0, а из этих чисел только 0 делится на p. Значит, .

Свойство 3 (Критерий Эйлера). Пусть p – простое нечетное число. Тогда .

Доказательство. 1) Пусть . Тогда . По определению символа Лежандра , следовательно, .

2) Далее будем рассматривать случай, когда . Поскольку число p простое, . Тогда по теореме Ферма . При этом выполняется ровно одно из двух последних утверждений. Действительно, если бы выполнялись оба, то разность также делилась бы на p, а поскольку эта разность равна , то на p она не делится.

3) Пусть a – квадратичный вычет по модулю p. Это означает, что найдется такое число , что . При этом , поскольку если бы , то и , что неверно. Значит , следовательно, по теореме Ферма . Тогда . Но поскольку a – квадратичный вычет по модулю p, символ Лежандра . Значит, в рассматриваемом случае .

4) Пусть a – квадратичный невычет по модулю p. Тогда символ Лежандра . Поскольку , по теореме Ферма . В соответствии с пунктом 2) доказательства выполняется ровно одно из двух условий: . Если бы выполнялось первое условие, то по доказанному в пункте 3), число a было бы квадратичным вычетом по модулю p, что неверно. Следовательно, выполняется второе условие, а это значит, что и в данном случае .

Свойство 4 (мультипликативность символа Лежандра).

                                   .                                                    

Доказательство. Для доказательства утверждения воспользуемся критерием Эйлера: ,   и . Cвойство 5 сравнений утверждает, что сравнения по одному модулю можно почленно перемножать, значит , откуда и следует требуемое равенство.

Свойство 5. В числителе символа Лежандра можно отбросить любой квадратичный множитель, не кратный p, то есть  при .

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

    Следующее свойство символа Лежандра примем без доказательства.

Свойство 6 (Квадратичный закон взаимности Гаусса). Для любых простых нечетных чисел p и q справедливо равенство .

     На основании перечисленных свойств можно вычислять символы Лежандра  для любых целых значений a и любых простых нечетных значений q, и тем самым решать задачу распознавания для квадратичного сравнения , то есть давать ответ на вопрос, имеет ли данное сравнение решение.

Примеры. 1) Определить, имеет ли решение сравнение . Вычислим символ Лежандра . Поскольку , по свойству 1 символа Лежандра имеем: , а, как было установлено выше, , следовательно, данное квадратичное сравнение имеет решение.

2) Определить, имеет ли решение сравнение . Вычислим символ Лежандра . По критерию Эйлера . Следовательно, , но , значит , и сравнение решений не имеет.

3) Определить, имеет ли решение сравнение . Вычислим символ Лежандра . По мультипликативному свойству символа Лежандра . Поскольку , а, как было установлено в примере 2, , следовательно, . Значит, данное квадратичное сравнение решений не имеет.

4) Определить, имеет ли решение сравнение . Вычислим символ Лежандра . По свойству 5 символа Лежандра . Следовательно, данное сравнение имеет решение.

5) Определить, имеет ли решение сравнение ? Вычислим символ Лежандра . По квадратичному закону взаимности Гаусса . Воспользуемся свойством 1 символа Лежандра, получим , и, как было отмечено выше, . Значит, данное квадратичное сравнение решений не имеет.

 

Символ Якоби

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

    Определение 16.1. Пусть , а n – нечетное число, большее единицы. Рассмотрим каноническое разложение числа n: , где  – простые числа, а . Символом Якоби называется величина, обозначаемая , определяемая следующим образом: .

Замечание. Если число n – простое, то, очевидно, .                   В дальнейшем иногда при записи символа будем опускать индексы  и , если из контекста понятно, о каком символе идет речь. А именно, если в знаменателе символа стоит составное число, то имеется в виду символ Якоби, если же в знаменателе символа стоит простое число, то имеется в виду символ Лежандра, который в данном случае совпадает с символом Якоби.

    Символ Якоби можно вычислять, пользуясь его определением и свойствами символа Лежандра.

Пример. Найти . Заметим, что  – символ Якоби, так как в знаменателе символа стоит составное число. По определению символа Якоби

. В правой части последнего равенства стоит произведение символов Лежандра, поскольку знаменатели символов – простые числа. Тогда , . Следовательно .

Символ Якоби обладает многими свойствами символа Лежандра, доказательство их справедливости следует из определения символа Якоби и свойств символа Лежандра.

Свойство 1. Если , то .

Свойство 2. Если , то .

Свойство 3. (мультипликативность символа Якоби).

                                   .    

 Свойство 4. В числителе символа Якоби можно отбросить любой квадратичный множитель, не кратный n, то есть  при .

Свойство 5 (Квадратичный закон взаимности Гаусса). Для любых положительных нечетных взаимно простых чисел a и n справедливо равенство .

    Для частных случаев, когда  и  для символа Якоби справедливы утверждения:

 и .

    Заметим, что критерий Эйлера для символа Якоби, вообще говоря, не выполняется.

 

Пример. Проверим верно ли сравнение . Заметим, что в левой части сравнения стоит символ Якоби, так как в знаменателе символа стоит составное число 135. Рассмотрим каноническое разложение числа в знаменателе символа Якоби: . Вычислим по определению символа Якоби . В правой части этого равенства стоит произведение символов Лежандра. Тогда, по свойствам символа Лежандра получим , следовательно, .

С другой стороны, можно установить что . Следовательно, данное сравнение не верно, что означает, что критерий Эйлера для символа Якоби, вообще говоря, не выполняется.

              

Использование символа Якоби.

 

1) Рассматривая символ Лежандра как частный случай символа Якоби и пользуясь свойствами последнего, можно упростить вычисление символа Лежандра.

Пример. Имеет ли решение квадратичное сравнение ?

Число 219 – составное, , а число 383 – простое, поэтому  – символ Лежандра, и при этом  является также и символом Якоби. По свойству 5 для символа Якоби (квадратичному закону взаимности Гаусса) получим:

. По свойствам символа Якоби:

.

Следовательно, квадратичное сравнение имеет решение.

    Если бы мы стали вычислять символ Лежандра , не используя символа Якоби, то нам пришлось бы применить критерий Эйлера и вычислять остаток от деления на 383, что было бы более трудоемко, чем способ, который мы использовали.

2) Символ Якоби можно также использовать для решения задачи распознавания для натурального нечетного модуля n, а именно для получения ответа на вопрос: имеет ли квадратичное сравнение решение? Ответ на этот вопрос дает следующая теорема.

Теорема 16.1. Рассмотрим квадратичное сравнение

                      ,                                (16.1)

 где n – нечетное натуральное число. Если символ Якоби , то сравнение (16.1) не имеет решений, если же символ Якоби , то сравнение (16.1) может иметь решения, а может и не иметь решений.

Доказательство. Рассмотрим каноническое разложение числа n: , где числа  – простые.

 Если сравнение (16.1) имеет решение, то это означает, что найдется такое целое число x, для которого справедливо . Тогда , для всех . Если же сравнение (16.1) не имеет решений, то для любого целого числа x выполняется  для некоторого i.

По определению символ Якоби равен произведению символов Лежандра:

.

Следовательно, символ Якоби может быть равен , только в случае, когда хотя бы один из символов Лежандра равен . А это значит, что для любого целого числа x выполняется  для некоторого i. Следовательно, , значит квадратичное сравнение (16.1) решений не имеет.

Если же символ Якоби равен 1, то это может быть в случае, когда все символы Лежандра равны 1. Тогда найдется такое целое число x, что , для всех , следовательно,  , что означает, что сравнение (16.1) имеет решение.

Но символ Якоби может быть равен 1 также в случае, когда среди составляющих его символов Лежандра имеются равные , но таких сомножителей четное число. Тогда, очевидно, квадратичное сравнение решений не имеет. Теорема доказана.

Пример. Выше было установлено, что . По теореме 16.1 этот факт не означает, что сравнение  имеет решение. Действительно, если бы данное сравнение имело решение, то для некоторого значения x выполнялось бы . Если число делится на 5, то его последняя цифра – либо 0, либо 5. Но тогда число оканчивается либо на 2, либо на 7, а такого быть не может, так как квадраты целых чисел ни на 2, ни на 7 не оканчиваются.

 

Проверка чисел на простоту

Простые числа играют исключительно важную роль в жизни людей. На основе свойств простых чисел создаются различные способы шифрования, которые обеспечивают безопасность банковских операций, электронной почты, мобильной телефонной связи и многого другого. Поэтому задача поиска простых чисел чрезвычайно важна, однако пока еще никому не удалось найти формулу или алгоритм, позволяющий генерировать простые числа. Чтобы объявить найденное тем или иным способом число простым, требуется доказать его простоту. Существует большое количество способов проверки чисел на простоту. Среди них есть детерминированные, то есть дающие определенный ответ на вопрос, является ли число простым или нет. Есть также вероятностные способы проверки чисел на простоту, то есть объявляющие число простым только с некоторой вероятностью.

Напомним определение простого числа (см. определение 8.1).  

Натуральное число называется простым, если оно имеет ровно два различных делителя. Если натуральное число имеет больше двух различных делителей, то оно называется составным.

Одним из детерминированных способов проверки чисел на простоту является решето Эратосфена. Этот способ состоит в следующем.

Мы хотим составить ряд простых чисел, не превосходящих натуральное число n. Для этого выпишем числа

                     1, 2, …, n.              (17.1)                 

Первое большее 1 число из этого ряда есть 2. Оно имеет ровно два различных делителя – числа 1 и 2, следовательно, оно является простым.

Далее вычеркнем из ряда (17.1) все числа, кратные 2, кроме самого числа 2, так как они являются составными.

Первым, следующим за числом 2, невычеркнутым числом является 3. Оно не делится на 2 (иначе оно оказалось бы вычеркнутым). Следовательно число 3 является простым.

Вычеркнем из оставшихся чисел ряда (17.1) все числа, кратные 3, кроме самого числа 3.

Первым, следующим за числом 3, невычеркнутым числом является 5, которое также является простым.

Продолжая этот процесс и отбросив число 1, получим, что “высеянными” из ряда (17.1) числами оказались простые числа.

Заметим, что составление ряда простых чисел, не превосходящих n, заканчивается после вычеркивания всех чисел, кратных простым, не превосходящим  (см. следствие к теореме 8.3).

Этот древний способ (III-II в. до н. э.) дожил до наших дней, претерпев немало превращений и послужив основой для получения важных результатов теории чисел.

Пример. Найдем простые числа из ряда 1, 2, …, 100. Для этого составим список всех натуральных чисел от 1 до 100. Затем вычеркнем из списка все числа, кратные числу 2, кроме самого числа 2: 4, 6,8,…. Затем из оставшихся чисел вычеркнем все числа, кратные 3, кроме самого числа 3: 9, 15, 21,…. Затем проделаем то же самое для чисел, кратных 5 и 7. После этого процесс будет окончен, поскольку следующее первое число из невычеркнутых будет число 11, превосходящее . Вычеркнем также число 1. В результате получим числа:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 – это все простые числа из первой сотни.

 

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

Вероятностный тест Соловея-Штрассена

Тест Соловея-Штрассена основан на том факте, что символ Якоби , вообще говоря, не удовлетворяет критерию Эйлера для составных чисел n.

Введем следующее определение.

Определение 17.1. Пусть , . Если для чисел n и a выполняется критерий Эйлера:

                  ,

то число a называется Эйлеровым свидетелем простоты числа n.

    Определение 17.2. Составные числа n, удовлетворяющие критерию Эйлера называются псевдопростыми числами Эйлера-Якоби.

Рассмотрим натуральное число n. Проверка числа n на простоту методом Соловея-Штрассена опирается на следующую теорему, которую примем без доказательства.

Теорема 17.1. Если n – нечетное составное число, то количество целых чисел a, взаимно простых с n, не превосходящих n и при этом удовлетворяющих критерию Эйлера (т. е. количество Эйлеровых свидетелей простоты числа n, не превосходящих n), не превосходит .

Алгоритм теста Соловея-Штрассена

Алгоритм параметризуется количеством раундов k. В каждом раунде случайным образом выбирается число a: . Если оказывается, что , то, очевидно, число n – составное. В противном случае проверяется справедливость сравнения

                    ,                         (17.2)

Если (17.2) не выполняется, то выносится решение, что число n составное. Если же (17.2) выполняется, то число n может быть как простым, так и составным. В этом случае число a является Эйлеровым свидетелем простоты числа n. По теореме 17.2 свидетелей простоты числа n не более, чем . Значит, если число a оказалось Эйлеровым свидетелем простоты числа n, то можно утверждать, что число n – составное с вероятностью не более, чем .

    Поскольку число n, как правило, достаточно велико, можно считать, что случайные события, состоящие в выборе числа a в каждом раунде, являются независимыми. Поэтому если в k раундах, выбранные числа a оказались Эйлеровыми свидетелями простоты, то вероятность того, что число n – составное, не превосходит . Тогда число n оказывается простым с вероятностью не менее, чем .

Пример. Пусть . Проверим число n на простоту при помощи теста Соловея-Штрассена.

Раунд 1. Положим . Тогда  и . Следовательно, (17.2) выполняется, значит число n – простое с вероятностью не менее, чем .

Раунд 2. Положим . Тогда

 

и . Следовательно, (17.2) выполняется, значит число n – простое с вероятностью не менее, чем .

Раунд 3. Положим . Тогда

и . Следовательно, (17.2) не выполняется, значит число 45 является составным.

 

Теория чисел в криптографии

 

    Рассмотрим пример использования результатов теории чисел в криптографии.

    В 1977 году трое ученых Рональд Ривест, Ади Шамир и Леонард Адельман из Массачусетского технологического института (MIT) опубликовали алгоритм, названный RSA.

    Алгоритм основан на том, что некоторые вычислительные операции совершить относительно просто, а обратные – сложно.

 

Описание алгоритма. Предположим, что два человека А (Алиса) и B (Боб) договорились об использовании алгоритма RSA. Предположим, что B хочет отправить А секретное сообщение. Под сообщением будем понимать число. Действительно, любой текст, состоящий из слов, можно представить в виде упорядоченного набора цифр. Например, букве А можно поставить в соответствие цифру 1, букве Б – цифру 2 и т. д. Буквы в слове можно отделять друг от друга цифрой 0.

Действия A и B состоят в следующем.

1) А выбирает два простых числа p и q и вычисляет их произведение .

2) А вычисляет значение функции Эйлера от числа n: .

3) А выбирает чи