Содержание к диссертации
Введение
I. Анализ моделей и методов решений np-полных задач 24
1.1. Анализ алгоричмов построения полиномов с заданными свойствами в полях Гапуа 27
1.2. Анализ шлоритмов факторизации полиномов в полях Гапуа 33
1.3. Труднорешаемые задачи и модели систем защиты информации 39
1.4. Моделирование труднорешаемых задач с помощью диофантовых уравнений 44
II. Моделирование циклических кодов на основе Хп(х) 51
2.1. Рекуррентный метод моделирования полинома Хп(х) 53
2.2. Численный алгоритм построения Хп(х) 57
2.3. Вычисление коэффициентов полиномаХп(х) 60
2.4. Моделирование неприводимых полиномов с помощью подстановок 65
2.5. Метод циклотомических классов моделирования Хп(х) 70
2.6. Моделирование циклических кодове порождающим полиномом Х(|(х) 73
2.7. Математические модели циклических ЛМ-кодов 16
III. Методы факторизации полиномов в полях галуа 82
3.1. Алгоритм факторизации полиномов над Fp с помощью функциональных цепных дробей 84
3.2. Операторный метод факторизации полиномов и смежные с ним задачи 90
3.3. Факторизация полиномов с заданным периодом 96
3.4. Метод перестановочных целых функций 99
3.5. Моделирование неприводимых полиномов методом аналича 103
IV. Модели и методы параметрических решений многостепенных систем диофантовых уравнений 108
4.1. Основные модели и методы многопараметрических решений IIІ
4.2. Метод решений нормальных многостепенных систем 120
4.3. Метод решения с помощью понижения степени 125
4.4. Метод решения на основе введения цедо'шачных функций 136
4.6. Метод общих решений уравнений n-ой степени 155
4.7. Модели и методы решений в целых комплексных числах 163
4.7.1. Решение систем второго порядка в целых комплексных числах 164
4.7.2. Метод решения нормальной системы-третьего порядка 171
4.7.3. Метод решения нормальной системы че спертої о порядка 179
4.7.4. МСЇОД решения нормальной системы пятого порядка 188
4.7.5, Метод общих решений в целых и комплексных числах 197
V. Математические модели систем защиты информации на основе np-полных задач 206
5.1. Модель на основе обобщенного рюкзака 210
5.2. Модель на основе кода Варшамова 223
5.3. Моделирование с помощью универсального рюкзака 228
5.4. Моделирование с помощью функционального рюкзака 238
5.5. Модели полиалфавитных систем защиты информации 242
5.6. Моделирование систем, содержащих диофантовую трудность 246
5.6-1. Модель защиты информации на основе конструктивного рюкзака 253
5.6.2. Модель защиты информации на основе закрытого рюкзака 254
5.6.3. Модель с обнаружением и исправлением ошибок 256
5.7. Моделирование асимметричных систем на основе задачи факторизации 260
5.7.1. Модель многопользовательского варианта RSA 260
5.7.2, Модель полиномиального варианта RSA 263
5.8. Моделирование перестановок на основе перестановочных целых функций 264
5.9. Метод композиции различных моделей 268
5.10. Модель преобразования на основе теоремы Эйлера-Ферма 269
VI. Алгоритмы и оценки на основе предложенных математических моделей 273
6.1. Оценка значений коэффищшгтов Хм(х) и гипотеза Н.Г.Чеботарёва 274
6.2. Алгоритм защиты информации на основе модели плотного обобщённого рюкзака и ею реализация на ЭВМ 278
6.3. Алгоритм зашиты информации па основе модели плотного универсального рюкзака и его реализация на ЭВМ 286
6.4. Алгорш ,vi защиты информации на основе модели функционального рюкзака 294
Заключение 297
Литература
- Анализ шлоритмов факторизации полиномов в полях Гапуа
- Моделирование неприводимых полиномов с помощью подстановок
- Операторный метод факторизации полиномов и смежные с ним задачи
- Метод решения с помощью понижения степени
Введение к работе
В условиях стремительно возрастающих потребностей общества в информационных ресурсах персональных и сетевых компьютеров с одной стороны и необходимостью в контроле от случайных канальных и преднамеренных изменений извне в системах передачи, хранении и обработки информации с другой стороны так велики, а возможности программно-аппаратных средств столь развиты, что интерес к проблемам теории и практики передачи, обработки и защиты информации непрерывно растёт.
Значительные успехи, достигнутые в различных сферах деятельности человека с появлением компьютерных технологий, стимулируют научно-исследовательские работы, направленные на совершенствование существующих, разработку и создание новых безопасных информационных систем. При этом общеизвестно [8,10,12,60,61,134,137,151,165], что в процессе хранения, передачи и обработки информации (в дальнейшем хранение информации будем рассматривать как передачу информации во времени) могут произойти как внутриканальные преобразования (ошибки), так и в целом, по отношению к каналу внешние несанкционированные воздействия на канал. Поэтому для того, чтобы уменьшить или исключить эти нежелательные события вовсе, необходимо представить информацию в таком виде, чтобы она была устойчивой к указанным воздействиям. Другими словами, необходимо на основании характеристик канала выбрать такой способ преобразования исходных данных, чтобы вероятность случайного или преднамеренного искажения передаваемой и обрабатываемой информации была меньше любой-наперёд заданной величины.
Подчеркнём, что если проблема защиты информации в каналах связи от помех решена на достаточно высоком уровне с помощью помехоустойчивого кодирования [34,60,61], то основные задачи компьютерной безопасности, которые связаны с обеспечением конфиденциальности, целостности и доступности информации, обрабатываемой в компьютерных системах, далеки ещё от окончательного решения, хотя в последнее время в этой области поя-
вилось большое количество работ [6,7,14,31,46,51,53,64-69,94,105,115,139-142,165,205,217 и др.] и их число непрерывно возрастает. Несмотря на определенные успехи в данной области, интенсивные теоретические и практические исследования продолжаются и в настоящее время, и можно с уверенностью сказать, что повышенный интерес к этим работам сохранится в обозримом будущем. Более того, из общей теории информации выделилась самостоятельная интенсивно развивающаяся ветвь - теория защиты информации (ТЗИ), основным предметом которой является исследование возможностей повышения надёжности передаваемых электронных данных по реальным каналам связи, Эта теория, несомненно, имеет большое будущее, так как стремительно расширяется сеть пользователей персональных компьютеров, а вместе с ней повышаются требования к передаваемой и обрабатываемой информации.
В проблеме информационной безопасности электронных данных наметились следующие три основных направления исследований:
Совершенствование математических моделей передачи информации с целью увеличения её надёжности и объёма передаваемых сообщений.
Использование математических моделей и методов для повышения качества работы вычислительных устройств и дискретных автоматов, используемых в передаче и обработке информации.
Построение математических моделей передачи и защиты информации, которые удобно использовать для широкого класса систем связи, эксплуатируемых на практике.
Кроме того, одновременно резко возросли требования, предъявляемые к системам противостояния действиям, направленным на защиту от несанкционированного доступа (НСД) к компьютерной информации. В связи с этим особую значимость получила проблема эффективной и надежной передачи, обработки и защиты электронных данных при наличии помех в системах связи - как аппаратно-канальных, так и внешних. Для решения этих задач, в силу их специфики и характера, требуются все более совершенные матема-
б тические модели и методы, так как оппоненты несанкционированного доступа также разрабатывают свои, не менее эффективные методы взлома таких систем, предназначенных для защиты информации. Поэтому на практике считается, что разработчики систем защиты будут в выигрыше, если они успеют разработать новую модель защиты информации до взлома их оппонентами старой. Для решения упомянутой проблемы передачи конфиденциальной информации можно предложить следующие три возможных способа:
Создать абсолютно надежный, недоступный для других автономный канал связи.
Использовать общедоступный канал, но скрыть сам факт передачи конфиденциальной информации,
Использовать общедоступный канал связи, но так закодировать (преобразовать) информацию, чтобы декодировать её мог только адресат.
Первый способ для удалённых абонентов, очевидно, экономически не выгоден. Что же касается второго способа защиты информации, то проведением таких исследований занимается стеганография и такой способ, очевидно, не всегда надёжен. Поэтому самым надёжным и экономически оправданным является третий способ передачи информации.
Исходя из теоретических положений [31,53,141,165] построения стойких и эффективных моделей систем защиты информации, отметим особо, что все математические задачи являются моделями сокрытия и защиты информации, а решения этих задач соответствуют правильным ключам. Следовательно, выбор подходящей труднорешаемой задачи, в частности, NP-полной задачи, позволяет смоделировать систему защиты информации на должном уровне. Особенно, если этот выбор, как отмечал К. Шеннон [163], связан с задачей, которая содержит диофантовые трудности. В приложении книги [43] собрано более 300 задач, NP-полнота которых установлена. Остановимся на одной такой задаче - задаче о рюкзаке К. Как известно [51], стандартная задача Kg относится к классу NP-полных задач и она эквивалентна по сложности задаче о коммивояжере Рк. В частности, если верна основная гипотеза теории
сложности, в чём уверено большинство специалистов, то не существует алгоритма А, который бы решал произвольную задачу о рюкзаке за время, полиномиальное по длине рюкзака. Тогда, следуя этой гипотезе [43,51,139] можно доказать NP-полноту нестандартных задач о рюкзаках Kg, Kv и KF [109] на основе методов локальной замены и построения компонент.
В 1982г. А.Шамир [216] нашел полиномиальный по размеру рюкзака алгоритм решения задач о рюкзаке типа Меркля-Хеллмана, а потому соответствующая РСЗИ не может считаться надёжной системой с открытым ключом. Заметим также, что все задачи о нестандартных рюкзаках со сверхрастущими рюкзаками имеют полиномиальную сложность SP = п (1> и достаточно легко строить алгоритм их решении [195]. Однако возникают большие трудности при разработке алгоритмов решений задач о рюкзаке с плотным или другими типами рюкзаков Кс,Кц и KF, впервые предложенных автором [106].
Таким образом, для моделирования стойких систем защиты информации необходимо исследование новых труднорешаемых задач РЕ и предложить эффективные модели м СЗИ. Причём, стойкость Ss таких систем защиты информации напрямую будет зависеть от сложности SE труднорешаемой задачи Ре- Поэтому, если задачу Ри можно решить полиномиальным алгоритмом Ар, то она принадлежит классу Р и соответствующая модель М будет иметь полиномиальную стойкость SP.
Так как вопросы защиты информации самым непосредственным образом связаны с методами кодирования, обратимся к краткому обзору результатов исследований в области теории избыточного кодирования. В работах [12,13,17,29,196] разработан ряд конструктивных методов синтеза контролирующих кодов, имеющих большую практическую ценность. Заметим также, что, несмотря на значительный прогресс в изучении теории кодов, недостаточно полно рассмотрены практические аспекты программно-аппаратной реализации полученных новых разработок. К тому же в некоторых случаях больший эффект может быть получен при использовании неоптимального алгоритма кодирования и декодирования, который имеет простую программ-
ную или программно-аппаратную реализацию. В этом смысле класс циклических кодов, как важнейший подкласс линейных кодов, является эффективным как с алгоритмической, так и с вычислительной точки зрения - благодаря использованию аппарата полей Галуа.
С другой стороны, как известно [44], имеется прямая аналогия между обычными циклическими кодами передачи информации и циклическими AN-кодами. Причём многие известные циклические коды имеют и арифметические аналоги, хотя нерешенной остаётся задача построения класса циклических AN-кодов, подобного классу кодов БЧХ.
Циклические коды допускают простую техническую реализацию и могут быть использованы для изучения, поиска и построения других не менее эффективных в практическом отношении кодов. Особое внимание в этой связи заслуживают исследования Р.К. Боуза, Д.К. Рой-Чоудхури [13], А. Хок-винхема [196], которые сводят задачу синтеза эффективных кодов к задаче отыскания порождающих полиномов g(x) =Р^(хп'<' — 1) над конечными по-
лями, имеющими заданное множество корней. Дальнейшее развитие этой проблемы, и, в частности, задачи построения неприводимых в поле Галуа полиномов отражено в [176,180] и других работах. Наиболее важный вклад в решении данной проблемы внес P.P. Варшамов [17,19-27,30], получивший ряд фундаментальных результатов конструктивной теории приводимости полиномов над конечными полями, введя в рассмотрение специальные диофан-товы уравнения, решил в общем виде задачу синтеза и оценки максимально возможного числа сигналов в кодах с коррекцией сгруппированных (пачек) ошибок произвольной длины и интенсивности [28].
Следует отметить целый ряд новых подходов, включающих методы современной алгебры и геометрии [42], комбинаторики и теории чисел [30], предложенных различными авторами для решения вышеперечисленных задач. Центральное место здесь занимает диофантовый анализ [1,2,3,28,48,172] и, в частности, теория построения систем параметрических решений много-
степенных систем диофантовых уравнений [11,78-82,143,144,191,194]. С помощью аппарата диофантового анализа удалось получить решение чрезвычайно важных в практическом отношении задач, трудно поддающихся решению обычными способами [3,48]. Перечислим некоторые из них.
F,„ вида:
При отрицательном решении гипотезы Н.Г.Чеботарёва [168] о свойствах полинома деления круга Хрчг(х) в работе [48], для оценки числа N (t+ pqz + ргу + qrx = n) - целых неотрицательных решений, при исследовании алгебраической структуры периодических рекуррентных последовательностей в [3] были использованы линейные диофантовы уравнения вида aiXj + a2X2+ + atxt = m. При изучении недвоичных кодов полезным оказалось привлечение новых для теории арифметических кодов неэлементарных методов теории чисел [44]. Для доказательства квазисовершенности кодов БЧХ, исправляющих две ошибки, в [60] изучается многостепенная система уравнений над x+y+z=a
Автором предлагается новый подход к построению x3+y3 + z3_b
систем, содержащих диофантовые трудности, возникающие при решении многостепенных систем диофантовых уравнений высоких степеней: Хі'+Х2'+. . .+хпІ=уі'+у21+- - -+Уп'» '=1* «ш. При этом, в зависимости от значений основных параметров тип, учитывается либо сложность решения системы, либо сами решения, либо и то и другое одновременно. Особенность таких уравнений заключается в том, что в общем случае неизвестны общие непереборные методы их решения. В то же время для отдельных значений тип эти уравнения допускают параметризацию по одному, двум и более параметрам, т.е. можно получить параметрические решения:
Xj= Xj(ab а2,..., a,), yf = yL(a,, а2,..., at), і = 1.. m, Xj є N, yt є N, из которых следуют конкретные решения в натуральных числах (в общем случае - в целых комплексных (гауссовых) числах). Эта специфика многостепенных систем диофантовых уравнений позволяют нам строить эффективные симметричные и асимметричные СЗИ.
Так как проблемы передачи и защиты информации являются составляющими одной общей проблемы - надёжной и безопасной передачи информации, в данной работе предпринято параллельное исследование в их взаимосвязи. Так, например, можно исследовать вопросы передачи и защиты информации на основе математической модели, использующей сравнение вида:
Wtt-p=5]Ptai =а(то(іт),где ft- члены заданной числовой последовательно-
сти, ctj - могут принимать значения, вообще говоря, из различных числовых множеств А), (і = 1 .. n), aeZ. В частности, совокупность всех бинарных решений сравнения при Pj = I, m = 2п, а > 0 задаёт код Варшамова, исправляющий одиночные вставки, выпадения и симметричные ошибки [29]. В то же время, если в качестве р взять рюкзачный вектор, а в качестве а -спектр некоторого элемента открытого текста, то получим математическую модель рюкзачной системы защиты информации (РСЗИ).
Подчеркнём, что в целом детали комбинированного использования теории защиты информации с теорией кодирования ещё недостаточно проработаны [142], хотя на практике такие модели имеются. Так, например, разработанная Мак-Элисом [205] математическая модель защиты информации имеет сходство с моделями рюкзачного типа, основанными на плотных рюкзаках, в которой используются коды Гоппы, обнаруживающие и исправляющие t > 1 ошибок. Автором предлагается рассмотреть задачу математического моделирования систем защиты информации на основе равносильных рюкзаков с обнаружением и исправлением ошибок, содержащих диофантовые трудности.
Таким образом, для моделирования стойких систем защиты информации необходимо исследование новых труднорешаемых задач РЕ и разработка на их основе новых моделей М систем защиты информации. Причём, стойкость Ss таких систем защиты информации напрямую будет зависеть от сложности SE труднорешаемой задачи РЕ. Поэтому, если задачу Рц можно решить полиномиальным алгоритмом Ар, то она принадлежит классу Р, и соответствующая модель М будет иметь полиномиальную стойкость Sp.
Отметим также, что в указанных выше работах авторы ограничиваются рассмотрением сравнительно простых математических моделей при различных упрощающих ограничениях из-за трудностей исследования аддитивных NP-полных задач для более общих случаев, в том числе алгоритмов и методов решений этих задач, зачастую напрямую зависящих от основных размеров задач и параметров конечных полей.
Итак, подытожив все затронутые выше нерешённые теоретические и практические задачи теории защиты информации, можно констатировать, что на данном этапе развития ТЗИ уровень прикладных достижений теории кодирования и теории защиты информации не соответствует уровню достижений современной алгебры и теории чисел. В частности, недостаточно полно используются результаты исследований NP-полных задач, а именно: задач построения полиномов с заданными свойствами в полях Галуа, задач рюкзачного типа при моделировании стойких систем безопасной передачи данных по дискретным каналам с заданными характеристиками, сочетающими одновременно функции как передачи, так и защиты информации. С другой стороны, современные результаты алгебры и теории чисел не в состоянии обеспечить удовлетворительное решение многих практических задач теории защиты информации, в том числе с обнаружением и исправлением канальных и других ошибок, поступающих извне. Поэтому, исходя из сложившегося к настоящему времени состояния развития теории систем защиты информации, можно сформулировать следующую основную проблему научного исследования: построить на основе NP-полных задач эффективную, содержащую диофантовы трудности, математическую модель СЗИ (в частности, полиалфавитную), с обнаружением и исправлением как аппаратно-канальных, так и других ошибок, поступающих извне.
В работе отражены последние достижения автора по разработке эффективных информационных систем передачи и защиты компьютерной информации, исследованы различные модели систем защиты электронных данных и предложены новые методы их построения. Для этого проведены достаточ-
но подробные исследования полиномиальных систем в конечных полях и систем параметрических решений специальных многостепенных систем диофантовых уравнений. Особое место в работе занимают теоретические исследования проблемы рюкзака и моделирование соответствующих СЗИ на их основе. В частности, в отличие от математической модели стандартного рюкзака, рассматриваются модели обобщённого, универсального и функционального рюкзаков. На основании указанных типов рюкзаков строятся соответствующие СЗИ, которые являются более эффективными, чем аналогичные стандартные рюкзачные СЗИ, предложенными Р.Мерклем, М.Хельманом, БЛором, Р.Ривестом, А.Саломаа и другими авторами.
Цель диссертационной работы состояла в разработке математических моделей и аналитико-численных методов, позволяющих построить эффективные системы передачи и защиты информации на основе проблемы нестандартного и функционального рюкзаков, в том числе на основе равносильных рюкзаков.
Основная идея диссертационного исследования состоит в реализации сложной по К.Шеннону СЗИ, содержащей диофантовы трудности, позволяющие смоделировать стойкие системы передачи и защиты информации (К.Шенноном отмечалось, что наибольшей неопределённостью при подборе ключей, обладают СЗИ, содержащие диофантовы трудности). Для достижения поставленной в диссертации цели соискателю потребовалось провести соответствующие исследования и решить следующие основные задачи:
Проанализировать и обобщить результаты известных работ по разработке эффективных методов построения в явном виде в полях Галуа полиномов с заданными свойствами,
На основе полученных результатов предложить циклические коррек тирующие коды, которые удобно использовать на практике.
Провести исследование некоторых задач из класса NP5 на основе которых смоделировать эффективные системы защиты информации.
4. Разработать новые методы параметрических решений многостепенных
систем диофантовых уравнений в натуральных и целых комплексных числах и предложить СЗИ, содержащие диофантовые трудности.
Развить и обобщить теорию асимметричных стандартных рюкзачных систем и предложить математические модели СЗИ на основе обобщённого, универсального и функционального рюкзаков,
На основе числовых равносильных рюкзаков построить математические модели СЗИ с обнаружением и исправлением ошибок.
Научная новизна исследования.
1, Разработаны рекуррентный и другие эффективные алгоритмы по
строения полинома деления круга Хп (х), которые удобно использовать при
больших п, имеющих два и более простых нечётных делителя и которые до
пускают эффективную реализацию на ЭВМ, Был построен класс корректи
рующего циклического кода на основе полинома Хп(х) и арифметических
AN-кодов со специальными генераторами.
2. Разработаны конструктивные методы построения неприводимых в Fp
полиномов заданной степени в явном виде. Предложен эффективный алго
ритм факторизации заданного полинома на основе представления его с по
мощью базисных элементов А0, Аь -. -»Ap-i кольца Fp [х],
ЗЛредложены эффективные способы факторизации полиномов, которые находят широкое применение при передаче и защите информации, в частности при построении полиномиального варианта системы защиты RSA. С помощью функциональных дробей впервые проведено исследование задачи о разложимости заданного полинома над Fp исходя из длины периода его разложения в цепную дробь. Разработаны специальные алгоритмы разложения полиномов с заданными свойствами, в частности, полинома заданного периода, абсолютно неприводимого или перестановочного в поле Галуа.
4- Получены аналитические выражения для числовых и параметрических решений нормальных и других многостепенных систем диофантовых уравнений как в кольце целых чисел, так и в кольце целых гауссовых чисел. Разработаны эффективные алгоритмы параметризации таких систем (с пара-
метрами первой и второй степени), как на основе частных решений, так и на основе серии решений, имеющих приложения в теории передачи и защиты информации. Эффективность таких алгоритмов заключается в том, что в большинстве случаев сами параметры невысоких степеней - чаще линейные или квадратные.
Предложены новые методы построения нестандартных рюкзачных СЗИ, с повторениями и без повторений компонентов рюкзака. Разработаны нестандартные рюкзачные СЗИ на основе обобщённого, универсального и функционального рюкзаков, введенных автором.
Построены математические модели систем защиты информации в классе NP-полных задач на основе нормальных и других многопараметрических решений многостепенных систем диофантовых уравнений заданной степени.
7. Р азработана теория асимметричных рюкзачных систем защиты ин
формации. На основе равносильных рюкзаков построены математические
модели СЗИ с обнаружением и исправлением ошибок.
Теоретическая и практическая значимость работы. Основные результаты, полученные в работе, являются новыми, достоверными и имеют как теоретическую, так и практическую значимость.
Теоретическая ценность работы состоит:
в разработке новых математических методов построения полиномов с заданными свойствами таких, как рекуррентные, операторные и другие;
в разработке новых и обобщении известных методов параметризации многостепенных систем диофантовых уравнений;
в разработке новых методов нахождения числовых решений заданных многостепенных систем диофантовых уравнений;
в разработке новой теории нестандартных рюкзачных систем защиты информации.
Практическая ценность работы состоит: - в применении разработанных математических моделей к решению задач
построения циклических корректирующих кодов, в теории рекурсивных последовательностей, в теории кольцевых счётчиков, в радиолокации и в других областях, где находит применение теория приводимости;
- в применении предложенных математических методов и моделей к решению задачи построения систем защиты информации с заданными характеристиками.
в разработке математических моделей нестандартных асимметричных рюкзачных систем защиты информации с обобщённым модульным умножением;
в разработке математических моделей систем передачи и защиты информации с обнаружением и исправлением ошибок на основе равносильных рюкзаков.
Апробация работы. Результаты диссертационного исследования и основные научные положения работы докладывались и обсуждались на Всесоюзной школе "Конструктивные методы и алгоритмы теории чисел1* (Минск, 1989г.), на Международных конференциях "Современные проблемы теории чисел" (Тула, 1993г., 1996г., Воронеж, 1995г.), на Международных конференциях "Алгебра и теория чисел: современные проблемы и приложения" (Тула, 2003г,, Саратов, 2004г., Одесса, 2005г.)5 на Международных научно-практических конференциях по информационной безопасности (Таганрог, 2003, 2004, 2005, 2006г.г.), на Второй Международной научно-практической конференции "Исследование, разработка и применение высоких технологий в промышленности" (Санкт-Петербург, 2006 г.), на V Международной научной конференции «Ломоносовские чтения» (Севастополь, 2006 г.), на VII Всероссийском симпозиуме по прикладной и промышленной математике (Кисловодск, 2006г.), на Всероссийской научно-практической конференции "Современное Российское общество: проблемы безопасности, преступности, терроризма" (Краснодар, 2005, 2006г.п), на I, II региональных межведомственной конференциях по защите информации (Краснодар 2000, 2003г.г.), на межвузовской научно-практической конференции "Информационная безопасность
16 при использовании средств вычислительной техники" (Краснодар, 2003г.),
Публикации. Основные результаты диссертационной работы опубликованы в 65 печатных работах: в 60 научных статьях, более 10 из которых вышли в изданиях, рекомендуемых ВАК, в одной монографии, в 2 интеллектуальных продуктах ВНТИЦ, (свидетельства: № 70990000172 от 20,12.99г., № 73200300103 от 21 мая 2003г) и в двух программах для ЭВМ (свидетельства: № 2005611707 от 12.07,05, № 2006610879 от 06.03.06).
Структура и объём работы. Диссертационная работа состоит из введения, шести глав, заключения, библиографического списка, содержащего 223 наименований, и приложения. Она изложена на 320 страницах машинописного текста.
Во введении определяется проблема исследования и обосновывается актуальность темы диссертации, научная новизна и практическая значимость изложенных в ней результатов, приводятся сведения об общей её структуре, и даётся краткая характеристика содержания по главам.
В первой главе проведён анализ известных в литературе теоретических и практических решений проблем, основанных на труднорешаемых задачах теории и практики передачи и защиты информации. Подчёркнуто, что важность NP-полных задач (в частности задач Pg, Pw» Pd и других) состоит в том, что в теории зашиты информации многие симметричные алгоритмы и алгоритмы с открытыми ключами могут быть взломаны за недетерминированное полиномиальное время. К таким системам защиты информации относятся СЗИ на основе нестандартного рюкзака, разработанные автором в пятой главе данной работы.
Показано, что для задач теорий передачи информации определяющую роль играет разработка новых конструктивных методов построения полиномов заданной степени в явном виде над конечными нолями. Они включают эффективные и гибкие подходы для более узкого класса полиномов, но с достаточно высокими степенями. Рассмотренные здесь методы относительно разложения заданного полинома в произведение неприводимых полиномов
над конечными полями указывают на необходимость разработки более эффективных методов на основе современных достижений в алгебре и теории чисел. При этом необходимо, чтобы сам алгоритм разложения не зависел от стандартных параметров заданного полинома и конечного поля. Необходимы методы, требующие значительно меньшего числа аналогичных арифметических операций и допускающие эффективную реализацию на ЭВМ.
Во второй главе изучается проблема построения полиномиальных систем в явном виде, обладающих наперёд заданными свойствами, которая занимает ключевое место в различных областях современных информационных технологий- В частности, разрабатываются конструктивные методы построения в явном виде неприводимых в полях Галуа полиномов, изучаются их свойства. Особое внимание уделено исследованию полиномов деления круга Хп (х), имеющих своими корнями (р(п) элементы поля Галуа одного и того же порядка.
В данной главе изучается математическая модель построения Хп(х)> основная область применения которой - циклические коды для реальных систем передачи информации. В ней предполагается, что п достаточно большое число, которое имеет два или более простых нечётных делителя, не равных между собой. Выводится конечная формула для коэффициентов Хп(х) на ос-нове оценок количества решений линейного диофантового уравнения и уточняется решение гипотезы Н.Г.Чеботарёва относительно значений коэффициентов полинома Хп(х). Делается попытка несколько расширить возможности построения в явном виде неприводимых полиномов заданной степени, используя различные подстановки, в частности, вида Xn(xm) и устанавливаются условия его разложения. Предлагается метод циклотомических классов построения Хп(х) и изучается их приводимость над полями Галуа. Приводится корректирующий циклический код с порождающим полиномом ХДх), и указывается методика построения такого кода. Рассматривается задача существования примитивных в Fp элементов, и описываются арифметические AN-коды для специальных простых генераторов вида 2р+1> 4р+1,4"+1 и др.
Третья глава посвящена разработке эффективных методов разложения полиномов на неприводимые в Fp множители. Известно, что проблема по-строений таких полиномов над конечными полями представляет значительный интерес при математическом моделировании задач современных систем связи эффективной и надежной передачи, хранения и обработки информации при наличии помех, В частности, при решении задачи дискретного логарифмирования в расширенном поле (к которой сводится задача логарифмирования на эллиптической кривой), при исследовании ряда вычислительных задач, которые тесно связаны с факторизацией полиномов над конечными полями. Так, например, разложение на множители полиномов над кольцом целых чисел, построение расширений полей, создание систем защиты информации и др.
В частности, разрабатываются новые способы факторизации полиномов, которые находят применение при передаче и защите информации. При этом используется аппарат формальных степенных рядов в Fpffi(x) и теория числовых и функциональных цепных дробей.
Предлагается операторный метод построения неприводимых в Fp полиномов заданной степени и выводится конечная формула для подсчета числа простых полиномов заданного вида. В частности, рассматриваются приложения указанного метода к задаче разложения двучлена и других полиномов специального вида. Показано, что приведённый способ факторизации полиномов над Fp (данный способ с не значительными изменениями легко распространить также на случай поля Fq, где q = р1,1 > 2) позволяет рассмотреть достаточно широкий круг смежных с ним вопросов. Причём, как это следует из самого подхода, все вспомогательные вычисления производятся с полиномами, степени которых ниже степени факторизируемого полинома. Приводится способ построения неприводимых в Fq полиномов с заданным периодом, основываясь на известном разложении в полях Галуа, Предлагается метод целых перестановочных функций, сохраняющих приводимость и изучаются алгоритмы построения неприводимых полиномов методом анализа.
Четвертая глава посвящена теоретическому изучению и получению аналитических выражений для параметрических решений многостепенных систем диофантовых уравнений m-ой степени:
х1[+х1,+...-Ьхп| = у1|+у2|+_. + уп1,1=1.ят, имеющих приложения в алгебраической теории кодирования и теории систем защиты информации. Кроме того, приводятся, частично обобщаются и решаются диофантовы и системы диофантовых уравнений, встречающиеся в предыдущих главах и других задачах диссертационной работы. Рассматриваются различные способы их параметризации как на основе частных, так и на основе серии решений. Приводится теорема, обобщающая теорему Фролова [194]. Опираясь на результаты предыдущих глав и введя в рассмотрение специальные диофантовые уравнения, удалось найти [112] более простые решения чрезвычайно важных в практическом отношении задач, традиционно не поддающихся решению обычными методами. Здесь рассматриваются также системы многопараметрических (чаще двупараметрических) целых комплексных решений нормальных многостепенных систем диофантовых уравнений. Получен способ, позволяющий из двупараметрических решений многостепенной системы диофантовых уравнений перейти к двупараметри-ческим решениям соответствующих систем в целых комплексных (гауссовых) числах. Приводятся многочисленные примеры решений для всех рассмотренных систем диофантовых уравнений. В некоторых случаях удаётся получить класс решений на основе одной лишь частной системы решений. Предлагаемые здесь многопараметрические решения многостепенных систем диофантовых уравнений используются для создания надёжных и безопасных систем защиты информации.
Пятая глава посвящена построению эффективных математических моделей систем защиты информации на основе результатов, полученных в ходе исследования известной задачи о рюкзаке. Обобщается стандартная модель Ms рюкзачной системы защиты информации, предложенная академиком А. Саломаа [142] и другими авторами [51,135,182,195], приводятся различные
варианты её модификации. В отличие от базового варианта рюкзачных систем [51,142], рассматриваются различные его модификации: рюкзак либо обобщённый, либо универсальный, либо функциональный [104,105,109].
Предлагаются новые модели систем защиты информации на основе обобщенного, универсального и функционального рюкзаков, компоненты которых, в отличие от стандартного рюкзака, либо повторяются, либо нет; модель полиалфавитной системы защиты информации рюкзачного типа, основанная на рюкзаке с повторениями.
Одна из основных модификаций СЗИ основана на задаче моделирования равносильных рюкзаков размерности га степени п, которые определяются автором следующим образом: поставим в соответствие каждому решению нормальной многостепенной системы диофантовых уравнений n-й степени два рюкзака А = (аь а2, -., ат) и В - (bi, Ьз>. ., Ьт), Будем говорить, что рюкзаки А и В размерности in > 3 равносильны между собой и имеют степень п, если выполняются равенства:
п л
А = В или (а і, а 2,..., а п) =(Ь і , Ь 2, -.., b m) , 1 < n < m. (3)
Изучаются математические модели асимметричных рюкзачных систем защиты информации JVfo, для которых автор предлагает в качестве открытых ключей выбирать равносильные рюкзаки размерности I степени h, где I > т, h > п - определяются по заданным критериям канала связи. Равносильные рюкзаки могут быть найдены как решения нормальной многостепенной системы диофантовых уравнений h-ой степени, содержащей 1 переменных, исходя из соответствующего решения п-ой степени с m переменными (гл. IV).
Другая модификация СЗИ с равносильными рюкзачными векторами основывается на обобщённой теореме М.Фролова (см, теорему 4.6Л.) и операции обобщённого сильного модульного умножения. В отличие от стандартного модульного умножения, здесь предусматривается ещё и сложение по модулю г > max{ a, b }, где а > тах{ а;}, b > тах{ bj} с соответствующими ограничениями для операции по заданному модулю.
Разрабатывается новый класс систем защиты информации, в основе
которого лежат диофантовые трудности, возникающие при решении многостепенных систем диофантовых уравнений высоких степеней вида:
х, ,х2,...,хт = у, *ул*—,уш ? И и < т. При этом, в зависимости от основных параметров тип, учитывается либо сложность решения указанной
системы, либо сами решения 3(,32,.-,^= bj , b 2 * . j b m, либо и то и другое одновременно.
Рассматриваются рюкзачные системы, на этапе установления соответствия числовых эквивалентов и элементарных сообщений которых применяются р-ичные системы исчислений, р-ичные коды Варшамова и специальные рюкзаки. Последние рюкзаки строятся на основе многопараметрических решений многостепенных систем диофантовых уравнений.
В данной главе, кроме перечисленных выше моделей, изучаются: модель генерации перестановок числовых эквивалентов, основанная на применении перестановочных целых функций, модель прямого и обратного преобразований на основе теоремы Эйлера-Ферма: X2 + k Y = Р, к = 1,2,3, модель многопользовательского варианта системы защиты RSA, модель по-линомиального варианта системы защиты RSA, построенная на основании результатов, полученных во второй и третьей главах. Приводится метод композиции различных систем защиты информации, а также многоалфавитные СЗИ, в основе которых могут быть рюкзаки различных типов.
Все рассматриваемые нами системы - новые и обобщают ранее известные. Они могут найти непосредственное приложение в области безопасной передачи электронных данных.
В шестой главе приводятся описания среды реализации разработанных алгоритмов и программных модулей. В качестве языка программирования использовался язык Pascal 7-0 в среде ОС MS Windows 98, Результаты реализации разработанных алгоритмов подтверждают теоретические оценки относительно значений коэффициентов полинома Х„(х) и опровергают гипотезу Чеботарёва. Впервые построен в явном виде полином деления круга X2i45(x)
степени 960 с помощью рекуррентного алгоритма, коэффициенты которого могут принимать значения: ± 1,0, ± 2, ± 3, ± 4, -5.
Созданы программы алгоритмов, предназначенные для преобразования компьютерной информации в сетях ЭВМ с целью её защиты от несанкционированного доступа. Алгоритмы предназначены для аппаратной или программной реализации, удовлетворяют практическим требованиям и не накладывает ограничений на степень безопасности передаваемой информации. Можно выбрать один из двух возможных режимов преобразования открытых данных, в зависимости от ценности последних. Оба режима строятся на основе проблемы рюкзака с учетом всех параметров рюкзачных систем защиты информации.
В заключении подведён итог проведённых в диссертации исследований.
Основные положения, выносимые на защиту:
1 .Алгоритмы факторизации полииомов в конечных полях, позволяющие построить эффективные модели систем передачи и защиты информации,
Математические методы и теория параметрических решений многостепенных систем диофантовых уравнений, позволяющие построить математические модели систем защиты информации (СЗИ), обладающих повышенной стойкостью.
Математические модели и теория построения рюкзачных систем защиты информации с повторениями и без повторений, содержащие диофанто-вые трудности.
Математические модели и теория построения систем защиты информации с открытым ключом на основе функционального рюкзака (в частности, на основе обобщённого и универсального рюкзаков) с заданным спектром входа и пространством значений теоретико-числовых функций, входящих в рюкзак.
Теория моделирования полиалфавитных систем защиты информации с обнаружением и исправлением как аппаратно-канальных, так и других внешних ошибок на основе равносильных рюкзаков.
Анализ шлоритмов факторизации полиномов в полях Гапуа
Ввиду повышенного интереса к проблемам факторизации и большой активности развития исследований в этом направлении, приведём краткую характеристику состояния этого вопроса. Отметим, что проблема создания эффективных алгоритмов разложения полиномов над конечными полями особенно важна для теории передачи и защиты информации, и частности для теории кодирования и для изучения линейных рекуррентных соотношений в конечных ПОЛЯХ.
В последнее время, ввиду отсутствия алгоритма полиномиальной сложности решения данной задачи, её применяют для создания эффективных систем защиты информации. В частности, при решении задачи дискретного логарифмирования в расширенном поле (к которой сводится задача логарифмирования на эллиптической кривой). Кроме того, этот алгоритм может использоваться при выборе неприводимого полинома, задающего расширенное поле. Можно привести также ряд вычислительных задач, которые тесно связаны с факторизацией полиномов над конечными полями. Так, например, разложение на множители полиномов над кольцом целых чисел, построение расширений полей, создание систем защиты информации и др.
В предыдущем разделе мы изучили различные алгоритмы построения неприводимых над конечными полями полиномов с заданными свойствами. Теперь рассмотрим алгоритмы факторизации полиномов над конечными полями, исходя из параметров самого полинома и конечного поля, т.к. для одних параметров проблема расщепления полиномов сводится к задаче отыскания корней других полиномов, а в других случаях необходимо учитывать значение порядка поля. Очевидно, эти алгоритмы одновременно позволят нам строить новые неприводимые полиномы над конечными полями.
Хорошо известно [54], что каждый полином положительной степени п f x) = + + .,. + -1 + f„xn из F[x], (где F - некоторое конечное поле) может быть однозначно с точностью до порядка следования сомножителей представлен в виде произведения f(x)=af14(x)f2e2(x).„f (i[)) (1) где aeF, fj(xj, f2(x), -.-, fk(x) - различные нормированные неприводимые полиномы из Fix], а Є], е2 - . - , ек - натуральные числа. Пусть deg(fi) = njt и N=HOK(ni,n2v»,nK), В дальнейшем мы будем считать, что исходный полином f{x) также нормирован и нашей ближайшей целью является практическое представление его в виде (1).
Очевидно, если d(x) = НОД(Г(х), Г(х)) - наибольший общий делитель полиномов f(x) и его производной Г(х) равен единице, то f(x) не имеет кратных сомножителей. Если же d(x) = f(x), то исходный полином представляет собой степень некоторого полинома g{x) из F[x, а именно - f(x) = g(x)q где q некоторая степень характеристики поля F. Учитывая последнее соотношение можно без ограничения общности рассмотреть полиномы, которые не имеют кратных неприводимых сомножителей. Следующая теорема является основной [8, 58].
Теорема 1.2.L Если f(x)eFq[x] - нормированный полином положительной степени и полином hq(x) = h(x) mod (f(x)), то f(x)- П НОЗДх),Ь(х)-с). (2) eEFq
Заметим, что формула (2) не даёт полного разложения f(x), поскольку полипом под произведением может оказаться приводимым в Fq[x].
Если h(x) = с mod (f{x)) для некоторого элемента с є v то по формуле (2) имеем тривиальное разложение f(x), что не имеет смысла в контексте данной задачи. Если же полином h(x) іаков, что по (2) можно найти нетривиальное разложение полинома f(x), то он называется f-разлагающим полиномом. Для построения алгоритма разложения необходимо найти способы построения f-разлагающих полиномов, что связано с вычислением q наибольших общих делителей, и применить на практике это формулу возможно лишь для достаточно малых конечных полей Fq.
В случае известного алгоритма Берлекэмпа [8] f-разлагающие полиномы определяются путём решения системы линейных уравнений (h0, hn.- h XB-E) = (0,0,...,0), (3) где h(x) = h0+ htx + ... + hn x n" , E единичная матрица, a 8- n x п-матрица над Fq, і-я строка которой соответствует полиному xq(l4), приведённому по модулю f(x).
Отметим, что возможность использования матрицы В для определения числа нормированных неприводимых сомножителей полинома f(x) была замечена ещё раньше, а общий случай был исследован Шварцом [58]. Результат, состоящий в том, что rg(B-E) = п- к, установлен автором [175],
Рассмотрим ещё один способ [47J построения f-разлагающих полиномов, который связан с построением некоторого семейства линеаризованных полиномов, содержащего по крайней мере один f-разлагающий полином.
Моделирование неприводимых полиномов с помощью подстановок
Как: известно [16-27], проблема моделирования неприводимых в поле Галуа полиномов заданной степени в явном виде, занимает особое место для различных приложений, и общий подход к ней указал P.P. Варшамов [22].
Здесь мы рассмотрим конструктивный метод моделирования для полиномов специального вида, что дает возможность несколько расширить класс неприводимых над полем Галуа полиномов заданной степени. Пусть Fp - поле Галуа и f(x) = ao+aiX+„.+anxn - полином степени п 2 из кольца Fp[x], который разлагается в поле Fp на к 1 неприводимых над Fp множителей. Отображение f(x) - f(g(x)) = f(g0+g,x +... + gmxm), где g(x) произвольный полином из Fpx] степени т условимся называть ш-ьгм преобразованием полинома f(x). В частности, если g (х) квадратный полином, то указанное преобразование назовем квадратичным преобразованием полинома f(x). Для краткости обозначим через F(x) выражение п m и=0 \=0 и исследуем вопрос его приводимости в Fp, если g(x) полином специального вида. Очевидно, если полином f(x) = fT(x) f2(x), то после замены в нем х через g (х), получаем тождество: f(g( )) = f.(g( )) fi(gOO), откуда следует, что структура полинома f(g(x)) целиком зависит от структуры т-ых отображений неприводимых делителей полинома f(x). Поэтому в дальнейшем всюду будем предполагать, что полином f(x) степени п неприводим над Fp.
Из 2) и 3) следует, что полином х m + 1 неприводим лишь при m = 2а, а полином xZm + хтИ+ I неприводим лишь при т = 3Р, что следует из 4). Далее полином x2m-xm+l+ I , согласно 6) неприводим в следующих трех случаях: m = 2а; т = У; m2a3 .
Ниже приводим таблицу разложений некоторых полиномов и бинарных форм, выполненных при помощи различных полиномиальных подстановок (Более полную таблицу разложений см. в [74, 75J). Для каждого данного полинома и для каждой данной бинарной формы выбирается подстановка таким образом, чтобы получить наибольшее возможное число неприводимых множителей, выделяемых, в основном, при помощи соответствующих формул П.х" +у "- П y2 (d)Xr+ld(x/y),m = 2aP;\..p;\ dm/2u 12.x2"4xV+y2m= П УїШ",р,,,,Хз.+,1і(х/у),іп=ЗврГ р?...р . dm/J" du»/2n3n 14. X2l(xlft) = X2l(x)X«(x)XlO5(x)X2l0(x) = X2l(x)X2l(-x)Xl05(x)Xl05(-x). 5. 4=o d/102 -Хз(х)Хз(-х)Х7(х)Х7(-х)Х5(х)Х51(-х). 16. X]5(x154) = Xl5(x)Xl5(-x)Xl05( В заключение, опять возвращаясь к выше затронутой проблеме, отметим, что указанные разложения с незначительными поправками верны и для полей Галуа, а приведённый метод существенно упрощает моделирование полиномов вида f(g(x)), рассмотренных выше и пригоден для разложения чисел определённого вида на простые множители, Пусть GF(pffl) - поле разложения полинома fn(x) = xn-l, Хп (х) - полином деления круга, р-простое число и (п, р) - 1. Обозначим через Сг пиклотомический класс по модулю п над GF(pm), состоящий из элементов [60] Cr = {r,rp,...,rpra }, где rpm = r(mod п), а через Сг [ - его мощность. Далее, пусть W(n, р) - множество всех циклотомических классов по модулю п над GF(pm). Тогда, очевидно, Со-{0},С = {1,р,...,р", }и {0 1,2 n-l} = UCr г где г пробегает множество всех представителей классов С\.
Теорема 2.5Л. Если (п, г) - 1, то циклотомический класс Сг, содержащий г в качестве наименьшего представителя, имеет m элементов, где m мультипликативный порядок числа р по модулю п.
Доказательство. Пусть (п, г) = 1 и мультипликативный порядок числа р по модулю її равен ш, т.е. р m = l(mod n). Тогда г р m = r(mod n), следовательно, С г = m. Следствие, Поскольку (п, 1) = I, то С ] ] = m . Теорема 2.5.2. При п = 4 и (4, р) 1 выполняется равенство Г 4, если р = l(mod 4), I W(4, р) I - ] [_ 3, если р = 3(mod 4). Доказательство. Пусть р - простое число и р = l(mod 4), тогда из теоремы 2.5.1. следует, что С г= {г} при г = 0,1,2,3 и W(4, р) = 4. Если же р = 3 (mod4),TO р2= l(mod4)nCfl= {0},Сі= {1,3}, С2 = {2}, т.е. W(4, р) = 3. Так, например, полем разложения полипома f4(x) = х4- 1 при p=l(mod4) является простое поле GF(p), а при р = 3(mod4) - поле GF(p2).
Из теоремы 2.5.2. непосредственно вытекает, что полином деления круга ХДх) = х +1 всегда приводим над полем GF(p), если р - 2 или р = l(mod 4), и неприводим, если р = 3(mod 4). Теорема 2.5.3. Пусть р = l(mod п) или р -l(mod п), тогда п, если р = l(mod п), \V(n,p)H L [п /2] + 1, если р = -l(mod п), если п 2 и полем разложения полинома f п (х) = х " - 1 является GF(p) и GF(p2) соответственно, где х] - целая часть числа х.
Доказательство. Пусть р = l(mod п), тогда из определения мультипликативного порядка числа р по модулю п следует, что m = 1 и полем разложения полинома fn (х) является поле GF(p), а каждый циклотомический класс Сг= {г} для г = 0,1,... ,п- 1 и потому W(n,р) = п.
Если же р = -l(mod п), то р 2 = l(mod п) и, следовательно, полем разложения fn (х) является GF(p ), а каждый циклотомический класс Сг = {i\ п-г}, число которых равно W(n, р) = [п / 2) + 1, п 2. В частности, при n = р т-1 имеем:
Операторный метод факторизации полиномов и смежные с ним задачи
Пусть Fq- поле Галу а порядка q - р ,1 1, где р - простое число и Х,Х2,.1.,хч -все его элементы. Обозначим через S=[x,g(i)]= I J п подстановку элементов поля Fq, порождённую функцией g(x)eFq[x]. Назовём функцию g (х) перестановочной функцией [59].
Перестановочные функции индуцируют перестановки элементов конечного поля Fq и, следовательно, соответствуют элементам симметрической группы 8 - группы веек подстановок на множестве из q элементов. Причём, если перестановочные функции f(x) и g (х) поля Fq задают подстановки S f и S к соответственно, то композиция f(g(x)) этих функций - также перестановочная функция в Fq, которой соответствует подстановка s=srsr В частности, для функции f(x) = g(g ... (g(x)). -.) существует наименьшее число t такое, что подстановка S = [ х, х ] = Е, где Е - тождественная подстановка.
Для некоторых значений q легко найти все перестановочные функции, а для других - невозможно. Так, например, произвольная линейная функция является перестановочной функцией для любого поля, однако не существует перестановочной целой функции второй степени в поле Fj.
Полином g (х) называется перестановочным полиномом [59] поля Fq, если соответствующая ему полиномиальная функция g: Fq— Fq, отображающая элемент х jGFq в элемент g(x i)eFq? является перестановкой элементов поля Fq. Полиномы такого вида существуют для любого Fq, так как любое отображение поля Fq в себя можно задать с помощью некоторого полинома степени не более q -1.
С перестановочными полиномами связан ряд естественных вопросов. Во-первых, само выяснение того, является данный полином перестановоч ным или нет, представляет собой нетривиальную задачу. Во-вторых, известно, что общие условия для того, чтобы полином был перестановочным, оказываются достаточно сложными.
Приведённая ниже лемма [58, 82] позволяет на практике находить в явном виде всевозможные целые перестановочные функции заданной степени поля Fq. m Лемма 3.4Л. Целая функция g(x) = ]Tguxu, l m q-lc Коэффициенту тами из поля Fq является перестановочной функцией в поле Fq тогда и только тогда, когда определитель A (go gn « » gm) системы линейных уравнений ф в.» ,,..., ,_,) =0,u=l..q, (1) получаемых из тождества 2\(8(х)Г=х, (2) не равен нулю.
Доказательство. Очевидно, если определить Л = A (go,..., gm) системы линейных уравнений (1) отличен от нуля, то однозначно можно определить функцию G(x), удовлетворяющую тождеству (2).
Далее, при А ф 0 из g(xu) = g(xv), х„, xv є Fq, u Ф v получаем G(g(x„)) = G(g(xv) или xu = xv, из чего следует, что функция g(x) - перестановочная. Из приведённой леммы следует, например, что не существует перестановочной целой функции g(x) = а х : + b х +с второй степени в поле так как определитель соответствующей системы линейных уравнений 1 с с2 Д(а,М)= 0 b 2ab+2bc =0 0 а а2+2ас+Ь2 для всех допустимых элементов поля F3 Отметим также, что целая перестановочная функция g(x) неприводима в Fq лишь при m = 1. Теорема 3.4Л. Пусть f(x) неприводимый над Fq полином степени п и а, Ь, с, d - произвольные элементы поля Fq такие, что a b - с d ф 0. Тогда полином F(x) = f((ax+b)/(cx+d)) (cx+d)n также неприводим в Fq. Доказательство. Известно, что если aeFq n f(ot) = 0»то a,a4,an ,-.,ач -суть все корни полинома f(x) в поле Fqn? и имеетместо разложение: f(x) = fl(x -a4")- (3) С другой стороны, корни полинома F(x), очевидно, равны Рої Рь » Р п- і» где pu = (daqil - b)/(a-caqu), u = 0. .(n-1), причём все они различны, так как из равенства pu = (daqu-b)/(a-caqu) = pv = (daq -b)/(a-eaqv),u tv следует, что aqu-aqvB силу условия a b - с d 0, что противоречиво. Потому из (3) получаем: F(x) = f((ax+b)/(cx+d))(cx+d)n =П(х -РД откуда и следует неприводимость полинома F(x) в Fq. Следствие L Если (п, к) =1, то в условиях теоремы полином F(x) является неприводимым также и над Fq k. Следствие 2. При с = 0, d = 1, (п, к) = 1 полином F(x) = f(ax+b) нспри-водим над Fqk. В частности, из неприводимости полинома f(x) степени п над Fj следует неприводимость полиномов f(x+b), xnf(l/x), (х + l)nf(l/(x + 1)) и др., также надР2.
Метод решения с помощью понижения степени
Рассмотрим модель параметрического решения диофантовых уравнений, которая позволяет строить им соответствующее новое решение, исходя из двух частных решений другого уравнения. Причём эти решения можно устанавливать различными способами, например, основываясь на равенство двух членов параметрических решений подходящего уравнения или на специальное разложение, или применяя различные подстановки.
Пусть необходимо найти решения в натуральных числах следующего, xi5+x3s+. - - +х55 = уі5+у25+... +у55, ( h х2,..., х5, ун у2,. - -, у5) = 1 (А) а также приводимые далее уравнений, которые трудно поддаются параметризации. Здесь мы приводим три параметрических решения уравнения (А). Допустим, что для уравнения H7 X,5+XiS+... + Xs5 ys (1) получены два частных решения, в которых имеется один общий член: а5+а15+... + а55=Ь5иа5+Ь:5+..и + Ь55 = с5, (2) тогда, исключив этот общий член, получим с5+а25+. ,, + a55 = b5+b25+. - + ЬД (3) Это доставляет частное решение уравнения (А). Например, из частных решений 725 195+43- + 4б5+475+675 и 1075 = 75+435+575 + 805+1005 уравнения (1) получаем одно частное решение нашего уравнения 75+575+725+80 +100 -195+465+475+675+Ю75. (4)
Для удобства и компактности записей примем следующие символические обозначения: 1 . Уравнение (А) запишем так: 5 (х„Х2,...,Х5) = (УьУ2,.-.,У5) 2. Уравнение (1) запишем так: (Xi, Х2, .., Xs) = У 3і1. Числовое тождество (4) тогда примет вид (7, 57, 72,80,100) = (19, 46, 47,67,107). Тождество индийского математика Шастри (1934г.) (75b5- а5)5+(а5+ 25b5)5+ (а5-25Ь5)5 + (10aV)5 + (50ab4)5 = «(as+ 75Ь5)5,1,904 а/Ь 2,371, (5) приведённое польским академиком Вацлавом Серпинским в своей книге [137] "О решении уравнений в целых числах", (М.,1961. С.61), без вывода, при 0 25Ь а 75Ь, доставляет бесконечное множество натуральных решений уравнения (1) во взаимно простых числах (при надлежащем преобразовании). Поскольку (5) нами использовалось много раз, приведём наш вывод этого тождества.
Рассмотрим хорошо известное тождество (х + у + zf = (х + у -zf+(x -у + z)5+(-x + у + z)5+ 80xyz x2 + у2 + 72). (6) Пусть х = а5, у = hb5, z - kb5 тогда 80xyz(x2+ y2 + z2) - 80hkaV0(a,0+ b]0(h2+ к2)). Пользуясь свободою выбора коэффициентов h и к, положим
80hk = р5, 24-5hk = р5, (7) h2+k2 = q5. (8) Из (7) следует, что hk = 2-5 (чтобы в обеих частях имели точные пятые степени), тогда hk = 2-5 и h2+ к2 = q5. Разложим 2-5 на произведение двух натуральных чисел всевозможными способами, а именно: h 1 2 2-5 2-5г 2-53 2-54 к 2-54 54 Є 52 5 1 Определим тот набор (h; к), при котором h + к - q , т.е. h + к равно точной пятой степени натурального числа. При наборе (2-52; 52) получаем h2+ к2 = 5s, следовательно, 80hk = 105, х = а5, у - 50b5, z = 25b5, 80xyz (х2+ у2 + z2) = (10aV)5 + (50ab4)s, x + y-z = as+25b5,x-y + z = a5-25b5, -x + y+ z = a5+75b5, x + у + г - a5+ 75b5 и в итоге из (6) получаем тождество (5). При а = 2, b = 1 получаем 1075 = 75+ 405+ 435+ 575+ 100s. Другие наборы не удовлетворяют уравнению (8). Возможно, существует другой способ получения тождества (5), быть может, более короткий.
Выпишем тождества: одно -тождество (5), а другое, получаемое из (5) заменой а через с (75Ь5-с5)5+ (с5+ 25ЬУ+ (с5- b5)s + (10cV)5+ (50cb4)5=(cV 75b5). (9) Потребуем от параметров a, b и с, чтобы один из членов левой части (5) был равен одному из членов левой части (9), выбранным подходящим образом, 149 например, 10aV = 50cb4,a3 = 5cb2. (10) Из (10) следует, что а делится на 5. Пусть a = 5т, тогда 125m3 = 5cb2, cb2=25mJ, Можем полагать b = 5, с = m .Подставим значения a = 5m, b = 5, с = т3 в тождества (5) и (9). Имеем (75-55- 55-т5)5+(5 V +25-55)5 + (55т5- 5-55)5 + (10-53т3-52)5 + + (50-55 mf= (55-т5+75-55)5. Или (75 - т5)5 + (т5 + 25)5 + (т5 - 25)5 + (1 От3)5 + (50т)5 = (т5 + 75)5. (5 ) (75-55-тГ5)5+(ml5+25-55 = (т5+75-55)5 или (75 т5)5+(тЧ5У+(т15 57)5+(2-53т9)5+(2-56-т3)Цт5+75-55)5 (9 ) Тождество (5 ) перепишем в следующем виде (5") (75-5 - 55m5)5+ (55т5+ 25-55)5 + (55т-25-55)5 + (2-56т3)5 + (2-57т)5 = = (55т5+75-55)5. (5ГГ) Из (91) и (5 ), исключив член (2-5 т3) , получим тождество (75-55- 55ms)5+ (55m5+ 75-55)5 + (ml5+ 57)s+ (m!5- 57)5+ (2-5V)5 = = (75-55-55m5)5+(55m5+25-55)5+(55m5-25-55)5+ (ml5+ 75-55)5 + + (2-57m)5.
Это тождество доставляет бесконечное множество решений нашего уравнения (А). Мы можем, разумеется, написать два тождества вида (5), а затем потребовать, чтобы какой-либо член первого тождества был равен какому-либо подходящим образом выбранному члену другого тождества. В этом случае получим одно уравнение с четырьмя неизвестными. Каждое решение этого уравнения доставит соответствующее решение нашего уравнения. Если же из такого уравнения получим параметрическое решение, то тогда получим параметрическое решение нашего уравнения. 150 Пусть второе тождество есть (75 її - ш5)5 + (ш5 + 25п5)5 + (ш5- 5n5)5 + (10mV)5 + (50mn4)5 = = (m5+75n5)5. (11) Возьмём 50ab4 = 50m n4, откуда ab4=mn4. (12) Легко найти параметрические решения уравнения (12). Пусть a = s4, m = г4, тогда sV = r4n4, sb = rn; возьмём b = г, п = s, тогда a = s , b = г, m = г , п = s. Из (5) получаем тождество (75r5- s20)5 + (sM+ 25r5)5 + (s20- 25r5)5+ (10s V)5 + (50sV)s = (13) = (S20+75r5)5. Из (11) имеем (75s5-r10)5+ (r20+25s5)5 + (r20-25s5)5 + (10r12s2)5 + (50 rV)5= = (r20+75s5)5. (14) Из (13) и (14), исключив (50 r4s4)5, получим тождество (75 r5-s20)5+ (s20+ 25 r5)5+ (sZ0-25 rs)s+ (10 s12 r2)5 + (r20+ 75 ss)5 = (75 s5- r20)5+ (r20+ 25 sV+ (r20- 25 ss)s+ (10 r12 s2)5+ (s:o+ 75 rs)s- (15)
Это тождество доставляет двупараметрическое решение уравнения (А) (при надлежащем выборе значений параметров s и г). Возьмём 10a3b2 = 10mV или aV = mV. (16) Пусть a = s2, m = г2, тогда s6b2 = rV, s3b = r3n, следовательно, можем счи тать b = r3, n = s3. Окончательно имеем: a = s\b = r,m = r,n = s. При этих значениях a, b, m, п из (5) и (11) имеем следующие тождества: (75rl5-s,0)5 + (s + 25rl3)5+ (s 25r,s)5+ (10sV)5 + (50r V)5 = = (s +75rLY. (17) (75s15- r )5+ (r10+ 25sls)5+ (r,fl-25sl5)5+ (10rV)s + (50rY2)5 = = (r,0+75s15)5. (18) Исключив из равенств (17) и (і 8) (10 r6 s6)5, получим тождество (75rl5-S,0)5+ (s + 25r,s)5+ (s10- 25r,s)5+ 50r 2 s2)5+ (r10 + 75s15)5 = (75s15- r10)5 +(r,0+25sH)s+(r e- 25s15)5 + (50r2Su)5+(s10 + 75 r15)5. (19)
