Уравнение в кольце вычетов систем

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

Алевтина Шахова 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. ИНАЧЕ <обнуляем все элементы i го столбца выше ведущего>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 < di ai, >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. Ноден П., Китте К. Алгебраическая алгоритмика. Пер. с франц. — М.: Мир, с.

О применении теории вычетов при решении диафантовых уравнений

О применении теории вычетов при решении диафантовых уравнений

«Оренбургский государственный университет»,

«Достопочтеннейший Дионисий, зная, что ты ревностно хочешь научиться решению задач, касающихся чисел, я попытался изложить природу их и могуще­ство, начиная с тех оснований, на которых покоится эта наука. Может быть, этот предмет покажется тебе затруднительным, поскольку ты еще с ним незнаком, а начинающие не склонны надеяться на успех. Но он станет тебе удобопонятным благодаря твоему усердию и моим пояснениям, ибо страстная любовь к науке помогает быстро воспринять учение». Таким посвящением открывается «Арифметика» Диофанта Александрий­ского.

В книге “Арифметика” Диофант (3 век) обобщил накопленный до него опыт решения неопределенных алгебраических уравнений в целых или рацио­нальных числах. Решение в целых числах уравнений с целыми коэффициентами более чем с одним переменным представляет собой одну из интереснейших проблем теории чисел. Некоторые виды таких уравнений были рассмотрены еще до Диафанта знаменитым математиком древности Пифагором (6 в. до н. э). В средневековой Европе работы Диофанта о решении уравнений в целых числах получили широкое распространение и развитие. Впоследствии, в память о мыслителе, вложившем в исследование неопределенных алгебраических уравнений в целых числах большой вклад, эти уравнения стали называть диофантовыми. Исследованием диофантовых уравнений занимались такие классики математики как П. Ферма (1601-1655), Л. Эйлер (1707- 1783), (1736-1813), (1777-1855), (1821-1894). И в настоящее время многие математики современности работают в области исследования диафантовых уравнений.

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

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

Построим кольцо классов вычетов по mod n. Пусть ,

Фиксируем , . Определим остатки от деления целых чисел, например, на число три. Получим три класса вычетов: – класс нуля, – класс единицы, – класс двойки.

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

Например, . Эти числа отстоят друг от друга на число, кратное трем:

Введем операции над классами

1)

2)

3)

Очевидно, что (это многократно примененное третье правило).

Пусть

Построим множество класса по mod n

Теперь перейдем непосредственно к решению диафантовых уравнений.

Задача 1.Доказать, что уравнение не имеет решения в целых числах.

Знакомство с p-адическими числами. Часть 1

Изображение с сайта Mathematical Art Galleries

В этой серии из двух статей я приглашаю вас заглянуть в один любопытный и не самый популярный уголок математики, в котором обитают необычные создания — p-адические числа, а попутно хочу рассказать о написанной мной Haskell-библиотеке для работы с ними, а также о двух классных инструментах: о типах-литералах (type literals) и семействах типов (type families), приближающих нас к заветным зависимым типам.

Я люблю язык Haskell и, начиная с какого-то времени, мне стало комфортно думать на нём, особенно, на математические темы. Когда понадобилось освоить новый инструмент, — p-адические числа, оказалось, что в репозитории hackage, основном для Haskell-сообщества, нет инструментов для работы с ними, даже в таких серьёзных теоретико-числовых библиотеках, как arithmetic, arithmoi или factory. В конце концов, я написал и опубликовал свой модуль padic, и во второй части этой серии расскажу о некоторых деталях его реализации. А сейчас речь пойдёт о самих p-адических числах.

В арсенале профессионалов и настоящих мастеров подчас попадаются странные инструменты. Не сразу можно сказать для чего они нужны и как они, вообще, могут быть полезными. Но при решении каких-то особенных задач они оказываются незаменимыми. Начиная с какого-то уровня погружения в теорию чисел, алгебраическую геометрию, квантовую механику или теорию струн, авторы книг и статей зачастую переходят от привычных целых и вещественных чисел к p-адическим числам и при этом удивительным образом чувствуют, что им становится легче. У меня, по крайней мере, первое знакомство с ними ощущения лёгкости не создало. В сети достаточно много вводных материалов по этой теме, как виде книг, статей и блогов, так и в форме видео. Большинство из этих введений начинается либо с введением бесконечноразрядных чисел, либо с определения p-адической нормы, а завершается упоминанием фрактальной (канторовой) топологии, которую эти числа образуют. При этом приводится пара канонических примеров необычности этой числовой системы, таких как сходимость суммы всех положительных степеней двойки к минус единице или возможность получить целочисленные квадратные корни из , или . В более серьёзных книгах всё внезапно становится существенно более сложным, поскольку авторам вдруг становится важно не то как складывать и умножать эти числа, а то что они образуют проективный предел колец вычетов относительно естественных проекций или что образуемое ими метрическое пространство неархимедово. Это похоже на ситуацию с многочисленными введениями в монады, или на известный мем с рисованием совы. Поэтому мы сегодня, отталкиваясь от вполне понятных и несложных вещей, постараемся пройти несколько дальше и понять в чём практический смысл введения этих числовых монстров.

Начинаем с цифр

Что мы имеем в виду, когда записываем число рядом цифр? То, что его можно представить в виде взвешенной суммы степеней некоторого основания, натурального числа, не равного нулю или единице. Как правило, мы работаем с основанием , равным числу пальцев на руках, в «цифровом» мире повсеместно используется самое маленькое из возможных основание , ну, а при записи времени нам оказалось удобным использовать смешанную систему с основаниями и .

В позиционной записи числа цифры выбираются из конечного множества возможных остатков деления на основание, а позиция цифры в ряду, обозначающем число, соответствует степени основания. Это всё привычно и поэтому кажется простым. Более того, в повседневности мы складываем и вычитаем, умножаем и делим, а также сравниваем не числа, а их позиционную запись (расширенную знаком «минус» для отрицательных чисел), а это значит, мы рассчитываем на то, что множество чисел и множество их позиционных представлений «работают» одинаково. Если мы выберем в качестве представления числа не цепочки цифр, а какие-то количественные меры, например, шаги на бесконечной ленте, то результаты сложения «в столбик» и непосредственно шагами на этой ленте будут согласованы между собой. Это же относится и к другим числовым операциям и свойствам. Говоря на языке математики, мы рассчитываем на изоморфизм между двумя числовыми системами: системой целых чисел и системой, которое образуют последовательности цифр вместе со знакомыми нам со школы операциями поразрядного сложения, вычитания и умножения.

Наконец, и сами цифры при выполнении арифметических операций тоже ведут себя как элементы своей числовой системы. Это значит, что цифры тоже можно складывать, вычитать и умножать, но по особым правилам модулярной арифметики, у которой тоже есть хорошо знакомый нам «нецифровой» аналог: шаги по замкнутой ленте.

Далее я буду использовать математические имена и обозначения для этих числовых систем. Система целых чисел (изоморфная шагам по бесконечной в обе стороны ленте) является кольцом и обозначается Цифры, используемые при записи числа в позиционной записи с основанием образуют кольцо вычетов по модулю , которое мы будем обозначать как . Эта система изоморфна шагам по замкнутой ленте, вмещающей ровно ячеек или отметок.

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

Кольца вычетов конечны, и может показаться, что их возможности меньше бесконечного кольца целых чисел, но это не так. В них, даже в совсем небольших, можно обнаружить то, чего нет в целых числах. Например, в кольце из пяти элементов у каждого элемента есть противоположный, то есть такой, что в сумме они дают ноль. То есть, в этом смысле оно включает в себя «отрицательные числа»: . Более того, в этой системе у любого корректного линейного уравнения есть решение, то есть, у каждого ненулевого элемента есть обратный, такой, что их произведение равно еднице. Таким образом, оно содержит в себе все возможные формальные дроби: . Значит, это уже не только кольцо, но и поле. Каждое кольцо вычетов по модулю, являющемуся простым числом, образует поле.

Но это ещё не все «сокровища». В кольце есть то, чего нет ни в целых, ни в рациональных числах, например, решение уравнения , то есть, , ведь . Это, впрочем, вовсе не значит, что — это мнимая единица, это вполне рядовой элемент конечного поля.

Кольца вычетов разные и у каждого есть свои интересные особенности, например, в кольце привычных нам цифр нет всех возможных дробей, но зато в нём есть делители нуля, то есть, такие ненулевые числа, которые в произведении дают 0 (например, ). А ещё в нём есть числа, равные своим квадратам: это и (помните рифмы в таблице умножения: «пятью-пять — двадцать пять, шестью-шесть — тридцать шесть»?). Таким образом, уравнение имеет в этом кольце целых четыре различных корня из которых два нетривиальны!

Поднимаемся выше

Каждое кольцо вычетов порождает целое семейство «потомков», которым они передают часть своих особенностей, но которые способны пойти дальше своего «родителя». Потомками кольцá можно считать кóльца , и т.д. Рассмотрим, например, кольцо . В нём, как и у его родителя тоже есть все противоположные числа и большая часть дробей (кроме тех, что имеют знаменатель, кратный ). Имеется в нём и , а также появляются корни из и , которых не могло быть в . В ещё большем кольце остаётся всё то же, что было у «предков», но расширяется набор квадратных уравнений, имеющих решения и появляется возможность решать некоторые кубические уравнения.

А интересно, если продолжать наращивать степени и новые возможности, то какими свойствами будет обладать кольцо ? На этот вопрос и ответил Курт Гензель, определив для такого предельного кольца числовую систему и описав его свойства. Система , порождаемая кольцом вычетов называется системой целых p-адических чисел и обозначается . Она включает в себя всех своих родителей, как подкольца и обладает всеми их свойствами сразу!

Получается, что можно построить цепочку числовых систем:

с помощью простой операции вычисления остатка (она показана стрелкой). У этой цепочки есть два предела — прямой: и обратный (или проективный) — . Таким образом, система p-адических чисел является системой, обладающей универсальным свойством: из неё можно построить гомоморфизм в любое конечное кольцо вычетов по модулю .

При устремлении к бесконечности, количество переходит в качество, и мы получаем нечто новое: бесконечное кольцо, которое включает в себя не только конечные подкольца, но и всё целиком, и кроме того, все формальные дроби со знаменателями, не кратными основанию , а также решения широкого класса алгебраических уравнений линейных, квадратных и высших степеней! Не любых, конечно, а только тех, что решаются в кольцах-родителях, но это «не баг, а фича», поскольку позволяет относительно легко ответить на вопрос о существовании решения у заданного алгебраического уравнения, который в целых или рациональных числах представляет крайне сложную задачу. Достаточно вспомнить, Великую теорему Ферма о существовании решения уравнения в целых числах при 2$» data-tex=»inline»/>, на доказательство которой ушло три столетия, и не удивительно, что в том доказательстве, что представил Эндрю Уайлз, используются p-адические числа.

Но это ещё не всё, что можно построить «поднимая» кольца вычетов до предельных колец целых p-адических чисел. Запрет на дроби со знаменателем, кратным основанию , достаточно жестко ограничивает нас в выборе доступных математических инструментов. Его можно изящно обойти, используя приём хорошо знакомый физикам и инженерам: разбить число на мантиссу и экспоненту. Любое рациональное число можно разложить в произведение , в котором число — обратимое целое p-адическое число (для которого всегда можно вычислить ), а — показатель степени при основании . Таким образом, рассматривая числа и , мы всегда сможем найти их отношение . Этот приём позволяет нам дополнить кольцо целых p-адических чисел до поля рациональных p-адических чисел . Если — простое число, то у нас этот трюк точно получится, поскольку в этом случае кольцо не содержит делителей нуля, которые обязаны в случае простого содержать в себе его в качестве множителя. Однако все такие множители мы вынесли в выражение , а значит, любое число будет обратимым.

При работе с позиционными системами счисления выгодно в качестве основания выбирать число с большим количеством множителей, это упрощает таблицу умножения. Число в этом отношении не оптимальное, основания , или существенно выгоднее и все они используются человечеством, как основания с древнейших времён. Однако для работы с p-адическими числами составные основания хуже простых, поскольку не дают преимуществ поля. Так что часто в самом начале статей и книг сразу оговаривают, что число в p-адической системе — простое.

Итак, несложный трюк помог нам повысить статус p-адических чисел до полноценного поля, которое теперь включает в себя в качестве подкольца целиком всё кольцо целых чисел , а в качесте подполя целиком всё поле рациональных чисел , а помимо них бесконечное множество других элементов, решающих алгебраические уравнения!

Конечные поля вычетов (алгебра простых цифр), которые лежат в основе p-адических чисел, существенно проще для анализа чем натуральные числа. Там, конечно, тоже хватает технических трудностей, но к ним проще подступиться потому, хотя бы, что поля эти конечны. Очень многие общие результаты теории чисел и алгебраической геометрии могут быть получены переходом к 2-адическим числам, которые, как мы теперь понимаем, можно рассматривать как бесконечноразрядные двоичные дроби.

Но, возникает вопрос: откуда же взялись все эти дополнительные числа? Описанный нами процесс повышения степени колец вычетов всё время расширял кольца новыми целыми числами, принадлежащими кольцам . Все наши формальные дроби и квадратные корни всегда совпадали с какими-то целыми числами и были от них неотличимы. Значит ли это, что и в дроби и алгебраические корни тоже будут какими-то целыми числами, совпадающими с «нормальными». И да и нет. Да — они все будут целыми, нет — они все будут отличаться и друг от друга и от элементов подкольца . Тут работает магия предельного перехода.

Возвращаемся к цифрам

Что мы делаем, когда хотим выразить сложную мысль? — используем много букв. А если нужно выразить большое целое число? — тогда нужно использовать много цифр и позиционную запись. С помощью привычной нам позиционной системы счисления можно выражать и p-адические числа.

Начём опять с маленького кольца . Все его элементы принадлежат множеству цифр . Поднимемся на ступень выше и перейдём в кольцо . Можно каждому элементу этого кольца назначить свой символ, скажем, из английского алфавита, а можно воспользоваться тем, что в этом кольце ровно элементов, ни больше ни меньше, а значит каждому из них можно поставить в соответствие пару цифр, и таких пар будет в точности . Это соответствие можно сделать не каким попало, а естественным, то есть таким, которое сможет сохранить числовые свойства цифр и элементов . Для этого достаточно использовать принципы позиционной записи, представив числа из как сумму используя цифры . Получим хорошо знакомую пятиричную систему счисления, которая позволяет подниматься по степеням основания, повышая разрядность записи числа. Так для записи любого числа из потребуется цепочка из пятиричных цифр.

Самое главное достоинство такого представления состоит в изоморфизме между числами и их позиционном представлении, о котором говорилось в самом начале статьи. Благодаря ему арифметические операции, производимые поразрядно (сложение с переносом, вычитание с «заниманием», умножение «в столбик» и деление «уголком») согласуются с арифметикой чисел, представляемых цепочкой цифр. А это значит, что совершая предельный переход от конечных колец к бесконечному, мы получаем возможность записывать 5-адическое число с помощью бесконечной цепочки пятиричных цифр:

и автоматом получаем практическую арифметику для p-адических чисел, знакомую со школьной скамьи! Такая запись называется каноническим разложением p-адического числа. И как только число разрядов устремляется к бесконечности, у нас и появляется куча свободного места для дополнительных чисел.

Все целые числа записываются конечным числом цифр. Задумайтесь над этим, множество целых чисел не ограничено сверху, однако сколь бы большое число вы ни выбрали (хоть знаменитое число Грэма, хоть его факториал) оно всегда может быть представлено конечным числом цифр. Таким образом, любое целое число можно представить как p-адическое, добавив бесконечную цепочку нулей после старшего разряда. Но p-адические числа могут иметь и любые ненулевые числа в своём бесконечном хвосте, который, по нашему определению, бесконечно длинее любой конечной цепочки цифр в начале. Таким образом, множество p-адических чисел много больше множества целых! Настолько же, насколько множество иррациональных чисел больше множества рациональных. Бесконечное разнообразие бесконечных последовательностей из конечного набора цифр образует континуум!

При переходе к рациональным p-адическим числам, мы вводим аналог десятичной точки, которая разделяет p-адическое число в каноническом разложении на конечную дробную и бесконечную целую части. Так что число можно записать как , в полном согласии с нашей интуицией.

Давайте посмотрим на примеры некоторых p-адических чисел:

В каноническом p-адическом разложении целые числа записываются в виде конечной последовательности цифр (бесконечную цепочку нулей, уходящую налево при записи опускают). Отрицательные целые числа вместо бесконечной цепочки нулей слева имеют бесконечную последовательность наибольшей из цифр (сравните с тем, как в двоичной системе представляются отрицательные числа). В p-адическом разложении цифры рациональных чисел после какой-то конечной цепочки всегда приходят к периодической последовательности. Обратите внимание на то, что запись числа в десятичной дроби и в виде 10-адического числа совпадают, это не случайно и достаточно удобно: положительные целые и дробные числа с конечным числом цифр имеют одинаковые десятичное и 10-адическое представление.

Какая от них польза?

Если долго смотреть на бесконечный хвост, уходящий влево, становится не по себе, ведь чем левее цифра, тем старше разряд, то есть, тем больше число. Получается, что почти все p-адические числа в обиходном смысле «бесконечны». Впрочем, «бесконечных» чисел в математике не существует, смысла в них немного. Как же вопринимать числа, записываемые заведомо бесконечным числом разрядов? В некотором смысле, так же, как и числа с бесконечным числом разрядов, но только уходящих направо от десятичной запятой, как в десятичных дробях, к ним-то мы привыкли! Вполне безобидное конечное число имеет в десятичной позиционной системе бесконечную последовательность цифр , так же как и в 10-адической: . Множество рациональных чисел в десятичной записи тоже включает в себя все натуральные числа, как такое подмножество, у которого справа от десятичной точки начинается бесконечная цепочка нулей. При этом большая часть вещественных чисел, образующих континуум, может быть записана только в виде бесконечной последовательности ненулевых цифр. Так что же, p-адические числа это как p-ричные дроби, записанные наоборот? Простая формальность? Нет, это не так, они круче!

В некоторых популярных введениях p-адические числа презентуют, как «бесконечноразрядные числа», или как оригинальный способ записывать числа «в обратном порядке» относительно привычно дробной десятичной нотации. Но надо понимать, что цепочки цифр — это не числа, они образуют вполне самостоятельную алгебраическую структуру, изоморфную (при определённых условиях) той или иной числовой системе. Большую часть вещественных чисел составляют невычислимые числа, для которых неизвестен способ их представления в форме цепочки цифр или даже в форме комбинации из вычислимых чисел. Каноническое разложение p-адического числа — это не p-адические число, а одно из его представлений, причём, только для вычислимых чисел и, к тому же, не самое удобное или эффективное, просто оно интуитивно понятно в силу нашей привычки оперировать позиционной нотацией. Самое главное, p-адические числа не являются представлением привычных нам целых, рациональных или вещественных чисел, они образуют самостоятельную алгебраическую систему, в которой есть образы инъективных гомоморфизмов (однозначных отображений) из систем вещественных чисел, но есть и иные объекты, у которых нет никаких вещественных аналогов.

Это важное замечание. Существование однозначного отображения любого рационального и многих алгебраических чисел в p-адическое поле, не гарантирует, что результат вычислений, произведённых с образами этих чисел, имеет вещественный аналог. Например, в кольцах с делителями нуля существуют нетривиальные автоморфные числа (числа, которые не меняются при возведении в произвольную натуральную степень). В вещественных и комплексных числах этими свойствами обладают только и , а, например, в есть ещё два таких числа: и , мы встречали их «родителей» ( и ) в базовой модулярной арифметике . А в таких чисел уже шесть! И ни одному из них не удастся найти прообраза ни в ни в . Впрочем, если основание простое и мы имеем дело с p-адическим полем и нормальной арифметикой, то нетривиальных автоморфных чисел уже не будет, но там будут иные диковинные звери, обитающие только в этих полях.

В общем, перейти p-адический мир не трудно, а вот вернуться оттуда можно не всегда. Это не так уж и необычно, для числовых систем. Множество вещественных чисел включает в себя множество рациональных , но кроме него содержит в себя все пределы фундаментальных последовательностей, сходящихся в , но не ему принадлежащих. Классические примеры таких пределов: . Первое можно получить как предел последовательности конечных цепных дробей или шагов метода Ньютона, а второе и третье — в виде последовательности частичных сумм рядов Тэйлора и Лейбница. Все без исключения элементы этих последовательностей рациональны, а их пределы — нет. И рациональных аналогов этим числам найти не удастся. Таким образом, добавляя к все возможные пределы сходящихся последовательностей из элементов , мы пополняем его до чего-то принципиально большего.

Такое же ключевое свойство, отличает множество от сколь угодно больших, но конечных колец , породивших его. Оно включает в себя все пределы сходящихся последовательностей из своих элементов (сходящихся в особом, p-адическом смысле). Это позволяет рассуждать о непрерывности и задействовать ряд методов анализа, основанных на понятиях пределов и производных: метод Ньютона, ряды Тэйлора, а вслед за этим экспоненты, логарифмы, тригонометрию, гамма- и дзета-функцию и прочие инструменты! Все они будут заметно отличаться от своих вещественных аналогов, сохраняя, впрочем, свои главные свойства, и работать смогут не всегда, но их наличие очень важно, когда речь заходит о серьёзной работе с числовыми системами.

Наконец, поле можно алгебраически замкнуть, расширив его корнями алгебраических уравнений и превратив в поле p-адических комплексных чисел , а оно уже оказывается изоморфным полю комплексных чисел, построенному на основе вещественных чисел. То есть, наряду со стандартной цепочкой вложений числовых систем:

можно строить альтернативные цепочки

которые начинаются с конечных полей вычетов, и достигают алгебраического замыкания, минуя поле . Между этими цепочками есть сложные родственные связи: любое кольцо включает в себя кольцо , а поле имеет подполем . Однако если мы устремим к бесконечности, то и и станут изоморфны — множеству натуральных чисел, то есть, множеству цифр в -ичной системе счисления (до второй цифры в каноническом разложении дело так и не дойдёт).

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

Есть ещё один практический аспект, делающий p-адические числа полезным инструментом и за пределами чистой теории чисел. Одна из досадных неприятностей при вычислении чисел в позиционной записи состоит в несимметричности операции переноса — он всегда делается от младшего разряда к старшему, то есть, справа налево. В этом отношении бесконечный «хвост» цифр, уходящий налево принципиально лучше бесконечного «хвоста», уходящего направо. Ведь переносы приходят именно справа, так что переполнение разряда где-то далеко в бесконечном ряду цифр при любой арифметической операции, может, в принципе, передаваясь по цепочке, повлиять на сколь угодно большой разряд. По существу, каждая цифра, действительного числа, вычислимого в позиционной записи, хранит потенциально бесконечную информацию о всех своих соседях справа. С этим связаны проблемы округления и вытекающая из них неустойчивость вычислительных алгоритмов, а также то, что дробные числа могут иметь два различных позиционнных представления, например, . Это значит, что отображение между рациональными числами и их позиционным представлением не биективно, и дело тут уже не в округлении, а гораздо глубже. Это нарушение биективности до сих пор не даёт некоторым математикам (например, Норберту Уайлдбергеру) покоя и они ищут возможность избавиться от него.

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

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

Знакомо? При этом неважно с какими числами мы работаем, с большими или маленькими, ошибки округления неизбежны, и, если можно так выразиться, плотно обступают любые числа. В то же самое время, конечность разрядов в целочисленных типах никак не влияет на точность вычислений для чисел, далёких от верхней границы, которая для или даже разрядной арифметики уже весьма и весьма велика! Потому так ценятся целочисленные алгоритмы, могущие заменить возню с плавающей точкой. Превращая рациональные числа в p-адические, мы переводим их в область целых чисел, в которой обрывание бесконечной цепочки цифр слева, не затрагивает цифры, уже полученные в более младших разрядах.

В этой основательной статье, которую я рекомендую всем заинтересовавшимся данной темой, приводится пример вычислительной устойчивости стандартных матричных операций в действительных и в p-адических числах. Вот, например как меняется число верных цифр при обращении матрицы Гильберта, простой, но неприятной матрицы, содержащей простые дроби. В обоих случаях использовалось одинаковое число бит для конечного представления числа.

Всё это выглядит впечатляюще, но отчего мы до сих пор не отказались от чисел с плавающей точкой и не перешли на p-адические числа, раз уж мы всё равно используем похожие на них двоичные числа для оцифровывания всего на свете? Всё дело в топологии.

Почему мы не проходим p-адические числа в школе?

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

Так вот с топологическими свойствами у системы p-адических чисел беда! Их нельзя выстроить по порядку вдоль прямой, как мы привыкли это делать с целыми, рациональными или вещественными числами. Расстояние между двумя p-адическими числами, то есть, абсолютное значение их разности, которое позволяет рассуждать о точности вычислений и о сходимости последовательностей, может быть вычислено единственным способом и он абсолютно не согласуется каким-либо порядком в . Более того, «между» любыми двумя целыми p-адическими числами можно отыскать сколько угодно других целых p-адических чисел, которые в привычной метрике оказались бы не просто далеко, а бесконечно далеко друг от друга! Впрочем, я взял слово «между» в кавычки, потому что и оно не совсем корректно, ибо p-адические числа топологически размещаются не на каком-то гладком многообразии, а на древо-подобной структуре. При этом пересечение всех открытых интервалов (шаров) образует не континуум, как в топологии действительных чисел, а фрактальное несвязное канторово множество. Впрочем, и сами шары в топологическом p-адическом пространстве весьма странные: любая точка шара, в том числе и граничная, является его центром. Так что мыслить шагами или отрезками на числовой прямой, любо непрерывными перемещениями в пространстве никак не получится, а это очень важная деталь в математической картине физического мира, в котором малому относительному смещению двух точек в пространстве или времени соответствует малое изменение расстояния между ними. В p-адическом мире на это рассчитывать не приходится.

С чем же связана такая оригинальная топология? Нельзя ли было построить её как-нибудь иначе? Увы, теорема Островского утверждает, что существует только два способа построения нетривиального самосогласованного нормирования для числовых систем, один — привычный для нас вещественный, а другой — p-адический. Так что, говоря о p-адических числах совершенно необходимо разобраться как устроено p-адическое метрическое пространство. И в этом нам опять поможет позиционная запись.

Каким образом мы выясняем близки ли два вещественных числа друг к другу, если они представлены не кучками фасолин или отрезками на прямой, а цифрами? Начиная со старшего разряда, мы сравниваем между собой цифры этих двух чисел, и чем длиннее оказывается непрерывная цепочка совпадающих цифр, тем ближе друг к другу наши числа. Разница между двумя числами 123.456789 и 123.456689 существенно меньше, чем между 123.456789 и 113.456789, хотя в обоих случаях отличие состоит в единственной цифре. Всё дело в позиции отличающихся цифр. Разговор о расстоянии между числами проще вести если одно число равно нулю, тогда можно рассуждать об абсолютном значении и нормировании числа (англ. valuation), а для сравнения ненулевых чисел использовать абсолютное значение их разности. В мире вещественных чисел абсолютное значение совпадает с модулем числа. Так, разница между 123.456789 и 123.456689 составляет 0.0001, а между 123.456789 и 113.456789 — 10. Число 0.0001 ближе к нулю чем 10.00. По этой причине в сходящихся последовательностях вещественных чисел, выраженных в позиционной системе счисления, увеличивается число цифр, совпадающих в левой части числа. Вот, например, как выглядит приближение к числу методом Ньютона в вещественных числах:

1.0000000000000000
1.5000000000000000
1.4166666666666665
1.4142156862745097
1.4142135623746899
1.4142135623730950

А теперь перейдём в p-адический мир и перевернём всё задом-наперёд. Числа в каноническом представлении у нас имеют бесконечный хвост уходящий налево, при этом степень основания продолжает расти как росла, справа налево. Как же сравнивать такие числа? На первом курсе Университета ходила шутка: «Какое число больше или , если читать их с конца?» Так вот, теперь это не шутка, а серьёзный вопрос.

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

…00000000000000000000000000000000000004
…51515151515151515151515151515151515154
…52300452300452300452300452300452300454
…02010030046244242322523014664645450454
…55641253041334120254404655400245450454
…16163312301130043502554655400245450454
…26305612301130043502554655400245450454

Последовательность, и правда, сходится, но в p-адическом смысле: с каждым шагом число не меняющихся цифр растёт, но в старших разрядах царит хаос. В пределе мы получим то самое целое число, которое при возведении в квадрат будет в точности равно 2, но путь к нему с точки зрения вещественного порядка будет выглядеть бешеным метанием по числовой оси. Если мы будем рассматривать разности между последовательными членами нашей приближений, то цепочки совпадающих цифры (выделенные жирным), превратятся в постоянно увеличивающуюся цепочку нулей. Именно так выглядит последовательность p-адических чисел, монотонно убывающая по их абсолютному значению. Формально абсолютное значение на определяют так: , где — это число нулей в правой части числа, то есть, позиция младшего ненулевого разряда числа. Например:

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

Округление p-адических чисел, таким образом, состоит в обрывании цепочки цифр слева. А благодаря тому, что при арифметических операциях перенос происходит от младшего разряда к старшему, при таком округлении мы не теряем никакой информации. Так что мы можем проводить вычисления с конечными округлёнными представлениями p-адических чисел, но, увы, из-за их патологической топологии мы не сможем ни построить график, ни, как-то вразумительно изобразить эти числа геометрически.

Эта диаграмма, показывает степень близости нескольких целых 3-адических чисел друг к другу. Если вы мысленно соедините стрелками числа, следующие по порядку, то получите представление о том, как действует на множество p-адических целых простейшая арифметическая операция: прибавления единицы. Как видите, даже такая элементарная операция катастрофически перемешивает точки в 3-адическом топологическом пространстве. На картинке в заголовке статьи показан пример визуализации прибавления единицы для 2-адических и 3-адических чисел. Промежуточное значение здесь имеет чисто демонстрационное значение, показывающее как одни целочисленные точки переходят в другие. А если мы вспомним, что кроме целых чисел в этом топологическом пространстве прячется целый континуум точек, образующих канторово множество, то станет понятно, что каким-либо внятным образом это множество и функции на нём изобразить не удастся.

Эти очень мощные, но очень специфические инструменты на практике используются, в основном, в теории чисел и абстрактной алгебре, но вот уже более полувека они стали рабочими лошадками в физике (квантовой механике, теории струн), в теории динамических систем и в методах генерации псевдослучайных чисел, в которых корявая p-адическая топология превратилась из неприятности в преимущество.

В следующей статье я расскажу о некоторых деталях реализации библиотеки для работы с p-адическими числами на языке Haskell и покажу ряд примеров работы с ними (тизер: мы вычислим число Грэма).