Квадратные уравнения в кольце вычетов (3 видео)

Алгоритм решения систем линейных уравнений в кольцах вычетов

Алевтина Шахова 6 лет назад Просмотров:

1 Авдошин С.М., Савельева А.А. Алгоритм решения систем линейных уравнений в кольцах вычетов Разработан эффективный алгоритм решения систем линейных уравнений в кольцах вычетов [], эквивалентный по сложности известному алгоритму решения систем в полях Галуа ([2], [4]). Приведены результаты сравнительного анализа предложенного алгоритма и существующих аналогов ([3], [0], [8]) на основе асимптотической оценки их временной сложности. Показано, что разработанный метод является корректным и существенно снижает трудоемкость алгоритмов дискретного логарифмирования. Введение Объектом исследования данной работы являются методы решения систем линейных уравнений в кольцах вычетов. Такие системы возникают в алгоритмах факторизации и дискретного логарифмирования (см., например, метод Диксона, алгоритм Копперсмита-Одлыжко-Шреппеля «COS» и алгоритм решета числового поля в [3]). Частным случаем колец вычетов являются поля Галуа, т.е. кольца вычетов по модулю простых чисел. Методы решения систем в таких полях известны (см., например, метод Гаусса (последовательного исключения) в [2, с.89], [4, с.42]). Модификацией метода Гаусса является метод Жордана. Однако для решения систем линейных уравнений в кольцах вычетов эти методы, вообще говоря, неприменимы. Проиллюстрируем сказанное. Рассмотрим систему линейных уравнений: 26x+ 3y = 4 () 9x+ 34y = в поле Галуа Z 37 и в кольце вычетов Z 36. В соответствии с методом Жордана требуется с помощью элементарных преобразований над строками привести матрицу к единичной. Для получения единичного элемента на диагонали в поле действительных чисел используется деление на число a, равное ведущему элементу; аналогом этой операции в кольце вычетов является умножение на элемент, обратный к a. Обратный элемент по модулю можно найти как решение уравнения: ax (mod ) (2) Для его вычисления используется расширенный алгоритм Евклида (см. [7, с. 744], [0, с.227]). На рис. приведено описание этого алгоритма. Если a и — взаимно простые числа, т.е. НОД( a, ) = = ax + y, то 2 ; в противном случае коэффициент Безу x является решением уравнения ( ) уравнение ( ) 2 не имеет решения и элемент a необратим в кольце Z. Как показано в [7, с.743], время работы алгоритма Евклида при вычислении НОД ( ab, ), где a > b 0, составляет O(log b ). Тогда

2 сложность операции вычисления обратного элемента в кольце Z можно оценить как O(log ). Метод Жордана с учетом алгоритма Евклида имеет временную сложность O( n ( n m+ log ) ) для системы n уравнений с m неизвестными в Z. Евклид( ab, ). d x y a 0 n r s b 0 2. c d / n 3. d x y 0 d x y n r s c n r s 4. ЕСЛИ n > 0 5. ТО перейти к шагу 2; 6. ИНАЧЕ вернуть( d, x, y, r, s ) Рис. В результате вычислений, приведенных ниже, получаем решение системы в поле Галуа Z 37 : x = 6, y = 23. [] [] ( 26 = 0 ) 30 3 [2] [] [2] [] 30 3 [2] ( 23 = 29 ) 30 3 [] [2] [2] Однако в кольце вычетов по модулю = 36 система () не может быть решена ни с помощью метода Жордана, ни с помощью метода Гаусса, поскольку все коэффициенты при неизвестных являются делителями нуля ([9, с.75]) и, следовательно, не является обратимыми. Таким образом, получить единичный элемент на диагонали умножением на какой-либо элемент кольца невозможно. Тем не менее, конечность области определения позволяет убедиться в том, что решение данной системы в Z 36 существует ( x = 7, y = 22), и притом единственно. Для решения систем линейных уравнений в кольцах вычетов необходимы специальные методы. Обзор существующих методов Анализ методов решения систем линейных уравнений в кольцах вычетов, описанных в современной литературе, выявил ряд недостатков, которые затрудняют использование этих алгоритмов на практике. В монографии [3] задача сводится к решению систем линейных уравнений над полями Галуа. Пусть

3 где систем t q α = m = ( ) ax b(mod ), i=, n 3 i i =, тогда решение системы ( ) m = 3 сводится к решению семейства ( ) ax b(mod q α ), i=, n, =, t 4 i i где неизвестные значения x (mod q α ) для фиксированного представляются в виде α α x x + x q x q (mod q ), 5 0, α Здесь 0 xl q, l = 0, α. Редуцируя систему ( 4 ) к модулю q, получаем систему уравнений: над полем Галуа виде ( ) q m = 5 с известными i0 поделив на i 0 ax b(mod q), i=, n ( ) Z. Если мы найдем все x,, 0 = m, то, подставляя x в x в систему ( ) 4, редуцируя ее к модулю q, мы получим систему линейных уравнений над полем 2 q и затем относительно неизвестных x,, = m, и т.д. В конечном счете, найдя значение x (mod q α ) для всех, мы восстановим x (mod ) по китайской теореме об остатках (см. [0, с.420]). 2 2 В нашем примере = 36 = 2 3, т.е. для решения одной системы в кольце вычетов придется решить 4 системы над полями Галуа. Но основным недостатком метода является необходимость разложения на множители числа : вопрос о существовании алгоритма факторизации с полиномиальной сложностью является одной из открытых проблем современной теории чисел. Другой метод предполагает сведение системы линейных уравнений в кольце вычетов к системе линейных диофантовых уравнений. При помощи одного из известных алгоритмов (см. [3] или [0]) расширенная матрица системы ( A b ) приводится к ступенчатому виду ( A b ) и вычисляется правая матрица перехода R размером ( m+ ) ( m+ ), такая, что: ( A b) R = ( A b ). На основании матрицы R можно получить общее решение системы. Проиллюстрируем применение данного способа на примере. Система линейных диофантовых уравнений, соответствующая системе ( ) в Z 36, имеет вид: 26x+ 3y+ 36v = 4. 9x+ 34y + 36v2 = Ее общее решение в кольце целых чисел: Z q

4 x = t t (-2492) y = t0 (-324) + t 5688, t0, t Z v = t0 (-857) + t 5048 v2 = 0 + t0 0 + t Редуцируя результат к модулю 36, получаем: x = 7, y = 22. Однако при решении систем линейных уравнений в кольцах вычетов наблюдается экспоненциальный рост длины коэффициентов. Так, в нашем примере коэффициенты исходной матрицы ограничены числом 36, тогда как в 6 целых числах мы получили общее решение с коэффициентами

0. Заметим, что этот результат соответствует системе в кольце вычетов, состоящей всего лишь из двух уравнений с двумя неизвестными. Для того, чтобы избежать экспоненциального роста длины коэффициентов, разработаны специальные методы решения систем линейных алгебраических уравнений над кольцом целых чисел, такие как модификация метода Гаусса и построение нормальной диагональной формы Смита (см. [8, с. 8]). Несмотря на то, что эти алгоритмы являются полиномиальными, их сложность существенно превышает сложность алгоритма Гаусса при решении систем в полях Галуа. Так, для системы из n уравнений с n неизвестными, коэффициенты которой по абсолютной величине не превосходят α, временная сложность модифицированного алгоритма Гаусса при использовании самого быстрого алгоритма умножения составляет O( n 4 (log α + log n ) ). Трудоемкость построения нормальной диагональной формы Смита матрицы 2 O n m 2 logα. A, где a α, i, n,, m n m i = =, ограничена величиной ( ) Метод решения систем линейных уравнений в кольцах вычетов, предлагаемый в данной работе, лишен недостатков вышеописанных алгоритмов и показал свою эффективность при программной реализации. Описание метода В основе разработанного метода лежит преобразование строк матрицы с использованием коэффициентов Безу, которые позволяет вычислить расширенный алгоритм Евклида (см. рис.). В результате работы алгоритма получаем: НОД ( ab, ) = d= a x+ b y, 0 = n = a r+ b s. a = 26 = a, b= 9 = a : НОД (26, 9) = = 26 ( ) + 9 (3), 0= 26 (9) + 9 ( 26). При 2 Применяя к -й и 2-й строке расширенной матрицы системы () преобразования, соответствующие преобразованиям алгоритма Евклида над поступающими на его вход коэффициентами a = 26 и a 2 = 9, в результате мы получаем матрицу, строчно эквивалентную исходной (см. [5, с.27]):

5 [] [] [2] [] [2] 9 34 [2] [] 9 34 [] [2] [] [2] [2] [] [] [2] [] [2] [2] В полученной матрице: A(, ) x y A(, ) = A(2, ) r s A(2, ), где x, y, r, s удовлетворяют условию: НОД ( a, a2) = a x + a2 y, 0 = a r + a2 s (запись A(, ) используется для обозначения -й строки расширенной матрицы A). Коэффициенты Безу x =, y = 3, r = 9, s = 26 можно получить, оперируя лишь коэффициентами a и a 2. Тогда цепь преобразований ( 6 ) сводится к одному преобразованию следующего вида: [] [] =[] 35 + [2] [2] =[] 9 + [2] 0 [2] С учетом того, что коэффициент a 22 = 7 обратим в Z 36 : 7 3(mod36), преобразуем матрицу к единичной и получаем решение: [] [] =[] + [2] [2] =[2] 3 [2] В общем виде алгоритм решения систем линейных уравнений в кольцах вычетов, представляющий собой модификацию метода Жордана, описан на рис.2. Доказательство корректности Предложенный алгоритм является корректным, т.е. полученная в результате преобразований система равносильна исходной (иначе говоря, решения системы не теряются и новые решения не появляются). 3 в матричном виде: Запишем систему уравнений ( ) Ax = b ( 7) Тогда по теореме о равносильности систем линейных уравнений: Если U — обратимая ( n n) коммутативное кольцо с единицей), тогда система уравнений ( ) системе ( UA) x = Ub. (Доказательство см. в [5, с.58]). Следствие из этой теоремы: ( 6) -матрица над R (R — произвольное 7 равносильна Если матрицы ( A, b ) и ( C, δ ) строчно эквивалентны, то система уравнений ( 7 ) равносильна системе Cx = δ.

6 Поскольку преобразования матрицы в описанном модифицированном методе Жордана базируются на элементарных преобразованиях строк (элементарными преобразованиями строк матрицы с элементами из коммутативного кольца с единицей называют (см. [6, с.85]) умножение любой ее строки на обратимый элемент кольца; прибавление к любой ее строке другой строки, умноженной на произвольный элемент кольца; транспозицию строк), то полученная на выходе алгоритма матрица строчно эквивалентна исходной (см. Модиф _ Жордан( A ). n Число _ Строк( A) 2. i 3. ДЛЯ = i+, n ЦИКЛ 4. НОД ( aii, ai ) = aii x + ai y ВЫЧИСЛИТЬ x, y, r, s : 0 = aii r + ai s 5. Ai (, ) x y Ai (, ) A(, ) r s A(, ) 6. ЕСЛИ коэффициент a ii необратим в Z 7. ТО выйти из алгоритма 8. ИНАЧЕ 9. A(, i ) A(, i ) a ii 0. A(, ) A(, ) A( i, ) ai, =, i. i i+ 2. ЕСЛИ i n 3. ТО перейти к шагу 2; 4. ИНАЧЕ вернуть( A) [5, с.27]). Тогда приведенному выше следствию соответствующие системы уравнений являются равносильными. Что и требовалось доказать. Оценка сложности Предложенный алгоритм обладает временной сложностью ( ( log )) Рис.2 O n nm+ для системы в кольце вычетов по модулю, в которой n — число уравнений системы, m — число неизвестных. Для получения этой формулы воспользуемся оценкой временной b сложности алгоритма Евклида T( a, b) = O + logϕ НОД ( a, b), где a > b 0, ϕ = ( + 5) 2 (доказательство этой оценки предлагается в [7, с.745], в качестве упражнения). На каждом -м шаге процедура, реализующая алгоритм Евклида, вызывается раз: первым параметром является текущее значение ведущего

7 элемента, в качестве второго на вход последовательно подаются ai ( i = +, n) и. Пусть di — значение ведущего элемента на i -й итерации цикла: d0 = a, d = НОД ( a, a+, ) = НОД ( d0, a+, ). d = НОД ( d, a ). d = НОД ( d, a ). +, n n n, Тогда число операций оценивается неравенством: n min, + log ( n ) + log НОД ( d, a ). i= i i, Помимо этого, на каждом -м шаге над элементами матрицы производится порядка 2( n )( m+ ) 2nm операций. Число шагов алгоритма для системы равно n. Получаем временную сложность алгоритма: n ( ) ( ). Tn (, ) = 2 nm+ ( n ) + log On ( nm+ log ) = Заключение В заключение приведем сравнительный анализ временной сложности предложенного алгоритма и алгоритмов, описанных в современной литературе, для системы n уравнений с m неизвестными в кольце вычетов Z ( t q α = = ). Алгоритм Модифицированный метод Жордана Метод сведения к полям Галуа* Метод сведения к диофантовым уравнениям (с построением матрицы Смита) Временная сложность ( ( + log )) O n nm t O n ( n m α + log ) + ln lnln e = 2 O n m 2 log р ( ) ln ln ln *Оценка временной сложности этого метода дана при условии использования для разложения на множители числа наиболее эффективного на сегодняшний день (см. [7, c.779]) алгоритма «квадратичного решета» () Померанца, имеющего временную сложность L ( ) + o ln ln ln, где L ( ) e =.

8 Список литературы. Авдошин С.М., Савельева А.А. Свидетельство об официальной регистрации программы для ЭВМ : «Программа решения систем линейных уравнений в кольцах вычетов». Зарегистрировано в Реестре программ для ЭВМ Ван дер Варден Б.Л. Алгебра. — М.: Наука, с. 3. Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. М.: МЦНМО, с. 4. Гантмахер Ф.Р. Теория матриц. Гостехиздат, с. 5. Глухов М.М., Елизаров В.П., Нечаев А.А. Алгебра: Учебник. В 2-х т. Т. I — М.: Гелиос АРВ, с. 6. Джекобсон Н. Теория колец (Перевод с английского Н. Я. Виленкина). М.: Государственное издательство иностранной литературы, с. 7. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, с. 8. Кузнецов М.И., Бурланков Д.Е., Чирков А.Ю., Яковлев В.А. Компьютерная алгебра: Учебник. Нижегородский Государственный Университет им. Н.И. Лобачевского. htt:// с. 9. Курош А.Г. Теория групп (Издание третье, дополненное). М.: «НАУКА», Главная редакция физико-математической литературы, с. 0. Ноден П., Китте К. Алгебраическая алгоритмика. Пер. с франц. — М.: Мир, с.

Содержание

Представление чисел суммой двух квадратов и эллиптические кривые
Вычеты
Чуть-чуть про эллиптические кривые
Квадратичные вычеты и невычеты
Доказательство
Причём здесь криптография?
📽️ Видео

Видео:Квадратные уравнения от «А» до «Я». Классификация, решение и теорема Виета | МатематикаСкачать

Представление чисел суммой двух квадратов и эллиптические кривые

Пусть p — нечётное простое число. Довольно широко известно, что p представимо в виде суммы двух квадратов целых чисел p=a 2 +b 2 тогда и только тогда, когда p при делении на 4 даёт остаток 1: 5=1 2 +2 2 , 13=3 2 +2 2 , 17=1 2 +4 2 , . ; 3, 7, 11,… непредставимы. Куда менее известно, что a и b можно записать красивой формулой, имеющей непосредственное отношение к одной эллиптической кривой. Об этом результате 1907 года за авторством немца по фамилии Jacobsthal и о связанных вещах мы сегодня и поговорим.

Совсем легко понять, почему 3, 7, 11 и прочие числа, дающие при делении на 4 остаток 3, непредставимы в виде a 2 +b 2 : квадрат чётного числа всегда делится на 4, квадрат нечётного числа всегда даёт остаток 1 при делении на 4, сумма двух квадратов при делении на 4 может давать остатки 0, 1 или 2, но никак не 3. Представимость простых чисел вида 4k+1 неочевидна (особенно если заметить, что простота существенна: число 21 хотя и имеет нужный остаток, но суммой двух квадратов не представляется).

Видео:Алгебраические уравнения в кольце вычетовСкачать

Вычеты

Натуральных чисел бесконечно много. Бывает полезно объединять их в классы по каким-нибудь признакам. В частности, объединение по остатку от деления на какое-нибудь число n приводит к вычетам по модулю n: вычет x̅ — это класс всех чисел, которые при делении на n дают тот же остаток, что и x. Что эквивалентно, вычет x̅ состоит из всех чисел вида x+n∙k, где k целое. В рамках данного поста все вычеты будут по модулю p (того самого нечётного простого числа из введения). Естественно, различных вычетов столько же, сколько может быть остатков от деления на p, то есть ровно p. По сравнению с бесконечностью натуральных чисел переход к вычетам сильно сокращает число вариантов.
Операции над классами далеко не всегда имеют смысл. Например, попытка сложить класс простых чисел с классом составных чисел не очень осмысленна: мы умеем складывать только числа, а у суммы простого числа и составного числа не видно свойств, общих для класса. Хотя члены клуба тавтологии и могут сказать, что сложение класса простых чисел и класса составных чисел даёт класс чисел, раскладывающихся в сумму простого числа и составного числа.

Для вычетов, тем не менее, сложение, вычитание и умножение, «унаследованные» от натуральных чисел, дают другие вычеты. Например, 2̅+3̅=5̅: возьмём любое число с остатком 2, любое число с остатком 3, и их сумма обязательно даст остаток 5. Вообще говоря, произведение двух ненулевых вычетов по произвольному модулю может внезапно оказаться нулём, 2̅∙3̅=0̅ по модулю 6, что неприятно. Но в случае простого модуля, очевидно, такого не бывает, как говорят, нет делителей нуля. Кроме того, можно решить уравнение a̅∙x̅=b̅ (операция деления) для любых двух вычетов, кроме случая a̅=0̅, и результат будет однозначно определён. Однозначность следует из того, что произведение ненулевых вычетов ненулевое. Поскольку a̅≠0̅, то наибольший общий делитель a и p равен 1 (здесь тоже нужна простота p), расширенный алгоритм Евклида найдёт x и y такие, что a∙x+p∙y=1, откуда следует a̅∙x̅=1̅, а значит, a̅∙(b̅∙x̅)=b̅.

Важное следствие из отсутствия делителей нуля: ненулевой многочлен от одной переменной степени n не может иметь более n корней. (Это хорошо известно для обычных целых чисел, но при использовании операций над вычетами требует дополнительного обоснования: уравнение 3̅∙x̅=0̅ по модулю 6 имеет три решения 0̅, 2̅, 4̅.) Действительно, обычное деление «в столбик» показывает, что любой многочлен f(x) можно представить в виде f(x)=(x-с)g(x)+(некоторая константа), где многочлен g(x) имеет степень на единицу меньше; если c — это корень f(x), то константа равна нулю (подставим x=c); если c’ — другой корень f(x), то он будет корнем g(x) (здесь важно отсутствие делителей нуля), так что процесс можно продолжить. Если уже набралось n корней, то оставшийся g(x) будет константой, причём ненулевой (иначе f(x)=0) и больше корней не имеет.

Вычеты по простому модулю можно складывать, вычитать, умножать. На ненулевые вычеты можно делить. Все эти операции обладают обычными свойствами типа a̅∙b̅=b̅∙a̅. В умных книгах говорят, что вычеты по простому модулю образуют поле (а вычеты по составному модулю, где делить нельзя, а всё остальное такое же, — коммутативное кольцо). И не надо быть умной книгой, чтобы назвать это поле конечным. Поле вычетов — не единственное конечное поле, но другие конечные поля нам не понадобятся.

Видео:40 Многочлены над кольцами вычетовСкачать

Чуть-чуть про эллиптические кривые

Эллиптическую кривую по модулю p (тому самому нечётному простому числу) можно рассматривать как набор решений уравнения y 2 =x 3 +a₂x 2 +a₄x+a₆, где x, y и все a — вычеты (каждое решение называется одной точкой), плюс одна специальная точка O, не имеющая пары x, y. Правая часть уравнения не должна делиться на квадрат, иначе это будет не эллиптическая кривая: в уравнении типа y 2 =(x-1̅) 2 (x+2̅) можно переменную y заменить на z=y/(x-1̅) и получить зависимость второй степени, а не третьей.
Если p≠3, то вместо переменной x можно взять x+a₂/3̅, избавившись от члена с x 2 .

Ясно, что раз x, y принадлежат конечному множеству, то число точек на эллиптической кривой тоже конечно. Сколько их? Это сложный в общем случае вопрос. Мы ограничимся кривыми вида y 2 =x 3 -k∙x. Для таких кривых полное доказательство можно уложить в один пост Хабра (хотя и довольно длинный).

Видео:Решение задач с помощью квадратных уравнений. Алгебра, 8 классСкачать

Квадратичные вычеты и невычеты

Зададимся сначала более простым вопросом. Сколько решений есть у уравнения y 2 =c, где y, c — вычеты? Пример для p=7:

y	0̅	1̅	2̅	3̅	4̅	5̅	6̅
y 2	0̅	1̅	4̅	2̅	2̅	4̅	1̅

Если c=0̅, то решение одно, y=0̅. Остальные значения y разбиваются на две половины, от 1̅ до вычета, соответствующего (p-1)/2, и от вычета, соответствующего (p+1)/2, до -1̅. Раз y 2 =(-y) 2 , вторая половина строки значений y 2 зеркально-симметрична первой половине. С другой стороны, в каждой половине повторений нет, поскольку иначе у уравнения было бы как минимум 4 решения, что невозможно для многочлена степени 2. Значит, есть (p-1)/2 вычетов c, для которых решений ровно 2, и столько же вычетов c, для которых решений нет совсем.

Ненулевые вычеты c, для которых есть решение, называются квадратичными вычетами. Вычеты c, для которых решения нет, называются квадратичными невычетами. Стоит отметить, что квадратичный невычет — это таки вычет, просто ему не повезло быть квадратичным. Символ Лежандра показывает отношение c к квадратам: 1, если относится (то есть c — квадратичный вычет), -1, если не относится (то есть c — квадратичный невычет), 0, если c=0̅. Число решений уравнения y 2 =c равно .

Вернёмся к эллиптическим кривым. Число вариантов y для фиксированного x мы знаем, общее число точек на кривой y 2 =x 3 -k∙x можно записать, просуммировав по всем x и не забыв про специальную точку: . Символом F_p, который раньше не появлялся, принято обозначать поле (field) вычетов по модулю p.

Теперь мы готовы предъявить обещанные формулы для компонентов разложения p в сумму двух квадратов. Теорема. Пусть g — любой квадратичный невычет. Если p при делении на 4 даёт остаток 1, то

причём число в первой скобке целое нечётное, число во второй скобке целое чётное. Если же p при делении на 4 даёт остаток 3, то обе суммы в скобках нулевые (а значит, число точек на эллиптических кривых равно p+1).

Видео:Быстрый способ решения квадратного уравненияСкачать

Доказательство

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

Если взять ненулевой вычет c и умножить его на все вычеты от 1̅ до p̅-1̅, все произведения будут ненулевыми и попарно различными (если c∙x=c∙y, то c∙(x-y)=0̅, что при ненулевом c может быть только если x=y), а значит, это будет просто какая-то перестановка всех вычетов от 1̅ до p̅-1̅. Следовательно, 1̅∙2̅∙. ∙(p̅-1̅)=(c∙1̅)∙(c∙2̅)∙. ∙(c∙(p̅-1̅))=c p-1 ∙1̅∙2̅∙. ∙(p̅-1̅) и c p-1 =1̅ для любого ненулевого вычета c. (Это было доказательство малой теоремы Ферма.)

Значит, многочлен x p-1 -1=(x (p-1)/2 -1)(x (p-1)/2 +1) имеет p-1 корней. Значит, каждая скобка имеет (p-1)/2 корней (максимально возможное количество для степени скобок). Каждый квадратичный вычет — корень первой скобки (если x=c 2 , то x (p-1)/2 =c p-1 =1̅), их (p-1)/2, значит, всем квадратичным невычетам остаётся вторая скобка. Итак, символ Лежандра от c принадлежит тому же вычету, что и c (p-1)/2 . (Это было доказательство критерия Эйлера).

Как следствие, получаем .

Является ли -1̅ квадратичным вычетом? Зависит от знака (-1) (p-1)/2 . Если p при делении на 4 даёт остаток 1, то (p-1)/2 чётно, (-1) (p-1)/2 =1, -1̅ — квадратичный вычет. Если p при делении на 4 даёт остаток 3, то всё наоборот и -1̅ — квадратичный невычет.

Простая часть теоремы: p даёт остаток 3 при делении на 4. Тогда в каждой скобке слагаемые с x и -x отличаются друг от друга умножением на символ Лежандра от -1̅, то есть противоположны по знаку и в сумме дают 0. Поскольку все слагаемые, кроме x=0̅, разбиваются на пары с нулевой суммой, а слагаемое с x=0̅, нулевое, вся сумма равна 0.

Если p даёт остаток 1 при делении на 4, то слагаемые с x и -x равны и их сумма четна. Значит, вся сумма также четна и числа в скобках действительно целые. Чётность/нечётность после деления пополам ненамного сложнее: в первой скобке теоремы есть три нулевых слагаемых, остальные слагаемые разбиваются на (p-3)/2 пар с суммой ±2 в каждой паре; при любом знаке при делении на 4 получается остаток 2, вся сумма при делении на 4 даёт остаток такой же, как p-3, то есть 2. После деления пополам получим нечётное число. Во второй скобке теоремы всего одно нулевое слагаемое и (p-1)/2 пар с ±2, итоговый остаток от деления на 4 получается 0, после деления пополам остаётся чётное число.

Пусть p при делении на 4 даёт остаток 1. Обозначим первую скобку теоремы через a, вторую через b. Мы уже знаем, что a и b целые.

Для доказательства посчитаем двумя способами следующую странную величину N: число пятёрок вычетов (x₁, y₁, x₂, y₂, t) таких, что выполнены сразу два уравнения: y₁ 2 =x₁ 3 -t∙x₁ и y₂ 2 =x₂ 3 -t∙x₂.

В первом способе сначала зафиксируем t и посчитаем число четвёрок из x, y, после чего сложим результаты для всех t. Ясно, что при фиксированном t пара (x₁, y₁) может быть любой неспециальной точкой кривой y 2 =x 3 -t∙x, вторая пара (x₁, y₁) — столь же любой неспециальной точкой той же кривой, а общее число таких пар равно квадрату числа неспециальных точек. (Собственно, поэтому мы и рассматриваем странную величину, она позволяет подобраться к a 2 и b 2 .) Если t=0, то уравнение y 2 =x 3 , как уже говорилось, не задаёт эллиптическую кривую и имеет столько же решений, сколько уравнение z 2 =x (где y=z∙x), то есть ровно p. При t=1 получается p+2a решений, при t=g — p+2b решений. Что насчёт остальных значений t?

Если y 2 =x 3 -t∙x и c — какой-то ненулевой вычет, то c 6 y 2 =c 6 x 3 -c 6 t∙x, что эквивалентно (c 3 y) 2 =(c 2 x) 3 -c 4 t∙(c 2 x). Иными словами, если (x,y) — решение уравнения с t, то (c 2 x,c 3 y) — решение уравнения с c 4 t, так что число решений с t и с c 4 t совпадает. Сколько есть разных ненулевых вычетов вида c 4 ? С одной стороны, не менее (p-1)/4: (p-1) значений c могут «склеиваться» в группы размером не более 4. С другой стороны, если (p-1)/4 — целое число, то все такие вычеты — корни многочлена x (p-1)/4 -1, так что их не может быть больше (p-1)/4. Значит, их ровно (p-1)/4.
Итак, (p-1)/4 кривых имеют p+2a неспециальных точек, ещё (p-1)/4 кривых имеют p+2b неспециальных точек. Это уже половина всего, что надо.

Если y 2 =x 3 -t∙x, то g 3 y 2 =(g∙x) 3 -(g 2 t)(g∙x). При фиксированном x число решений уравнения g 3 y 2 =. равно 2 — число решений уравнения y 2 =. . Значит, число неспециальных точек на кривой с t=g 2 (а следовательно, на (p-1)/4 подобных кривых) равно 2p-(p+2a)=p-2a. Аналогично число неспециальных точек на кривой с t=g 3 равно 2p-(p+2b)=p-2b.

Итак, первый способ вычисления даёт

Во втором способе вычисления N сначала зафиксируем x₁ и x₂ и посчитаем число троек t и y, после чего сложим результаты для всех пар x. При x₁=x₂=0̅ есть ровно p вариантов: оба y должны быть нулями, t может быть любым. При x₁=0̅ и ненулевом x₂ должно быть y₁=0, y₂ может быть любым, t вычисляется однозначно, получается снова p вариантов. Ситуация с нулевым x₂ и ненулевым x₁ симметрична. Наконец, пусть оба x ненулевые. Тогда t=x₁ 2 -(y₁ 2 /x₁) и нужно посчитать число пар y с условием (x₂/x₁)y₁ 2 =y₂ 2 +x₂(x₁ 2 -x₂ 2 ).

Если x₁=x₂, то уравнение превращается в условие совпадения квадратов y, и различных пар y получается 1+2(p-1): нулевая и по два варианта y₂ для каждого ненулевого y₁. Если x₁=-x₂, ситуация аналогичная, поскольку p даёт остаток 1 при делении на 4 и -1̅ — квадратичный вычет.

Если x₂/x₁ — квадратичный вычет, не равный ±1̅, то существует какое-то ненулевое c такое, что c 2 =x₂/x₁. Тогда (c 2 y₁ 2 -y₂ 2 )=(c∙y₁-y₂)(c∙y₁+y₂)=x₂(x₁ 2 -x₂ 2 ), выражение c∙y₁-y₂ может быть любым ненулевым вычетом, по нему однозначно определяется c∙y₁+y₂ и, следовательно, y₁ и y₂. Итого p-1 вариантов.

Если x₂/x₁ — квадратичный невычет, то аналогично эллиптическим кривым число решений равно 2p минус число решений в случае квадратичного вычета, то есть 2p-(p-1)=p+1.

Суммируем. Есть один вариант с x₁=x₂=0, дающий p решений. Есть 2(p-1) вариантов, где один из x нулевой, а другой ненулевой, каждый из вариантов даёт p решений. Есть 2(p-1) вариантов с x₂=±x₁, каждый из которых даёт 2p-1 решений. Есть (p-1)((p-1)/2-2) вариантов, где x₁ — произвольный ненулевой вычет, а x₂/x₁ — квадратичный вычет, отличный от ±1̅, каждый из этих вариантов даёт p-1 решений. Наконец, остаётся (p-1) 2 /2 вариантов, где x₁ — произвольный ненулевой вычет, а x₂/x₁ — квадратичный невычет, в каждом из этих вариантов p+1 решений. Итого .

Сравнение двух выражений для N завершает доказательство.

Видео:5 способов решения квадратного уравнения ➜ Как решать квадратные уравнения?Скачать

Причём здесь криптография?

Вычислять a и b, подсчитывая p раз символы Лежандра, непрактично. Куда быстрее с этим справится алгоритм Cornacchia. Практическая польза — использовать формулу для a, b в обратную сторону: можно доказать, что разложение p=a 2 +b 2 единственно с точностью до перестановки a и b и смены знаков, так что нахождение a и b влечёт знание числа точек на кривых y 2 =x 3 -t∙x для любого ненулевого t, это будет p+1±2a и p+1±2b.

Знание числа точек на кривой важно для криптографии на этой кривой. На эллиптической кривой можно ввести операцию сложения точек (о чём слышали, наверное, все, кто хоть что-то знает о криптографии) со специальной точкой O в роли нуля. На основе операции сложения можно определить умножение на натуральное число: 2P=P+P, 3P=P+P+P и так далее. Так вот, можно доказать, что если n — порядок кривой, то nP=O для любой точки P. Зная n, c, d, можно решать уравнения вида x∙(cP)=dP полностью аналогично делению вычетов: расширенный алгоритм Евклида найдёт x, y такие, что c∙x+n∙y=1, откуда x∙(cP)+y∙(nP)=P, то есть x∙(cP)=P. При этом, если c, d неизвестны, а cP и dP заданы координатами, то эффективных методов деления в общем случае неизвестно.

Вычислить число точек на заданной кривой довольно сложно (полиномиальный алгоритм существует, но на практике довольно медленный). Чтобы построить кривую с какими-нибудь свойствами на число точек, можно пытаться взять случайные коэффициенты и вычислять число точек в цикле, пока не получится то, что надо, но придётся подождать. К счастью, есть другой способ.

Если нас устраивает простое число вида 4k+1 и кривая специального вида y 2 =x 3 -t∙x (в некотором смысле это одна и та же кривая при любом ненулевом t) с числом точек p+1±2a или p+1±2b, можно её и взять. Что насчёт других кривых?

Немного позднее, в 1911 году, уже другой автор von Schrutka получил аналогичный результат для кривых вида y 2 =x 3 -t, простых вида 6k+1, представления p=a 2 +3b 2 . Значит, найти число точек на кривой y 2 =x 3 -t опять же позволяет алгоритм Cornacchia.

Позднее, по мере развития теории эллиптических кривых, выяснилось, что если есть какое-то представление 4p=a’ 2 +d∙b’ 2 , где d натуральное, при делении на 4 даёт остаток 0 или 3, взаимно простое с p и не слишком большое, то можно эффективно (даже если p очень большое) построить кривую, которая будет иметь ровно p+1±a’ точек. Два наименьших значения d=3 и d=4 соответствуют кривым y 2 =x 3 -t и y 2 =x 3 -t∙x. Пример для d=163:

При нечётном p≠163 это уравнение задаёт эллиптическую кривую. Если 4p представимо в виде a’ 2 +163b’ 2 с целыми a’, b’, то число точек на эллиптической кривой равно p+1±a’. Если нет, то p+1. К сожалению, доказательство использует «тяжёлую» теорию, поэтому здесь не будет даже намёков.
Обычно, впрочем, будут получаться радикалы. Например, для d=15: . Если 4p раскладывается в сумму a’ 2 +d∙b’ 2 и p взаимно просто с d, то все радикалы обязательно извлекутся (например, для d=15 обязательно найдётся вычет c, для которого c 2 =5̅ ) и получится эллиптическая кривая с нужным числом точек.