Элементы теории чисел

Целое число аделит другое целое числоb(аb) если и только еслиb=dадля некоторого целого числаd. В этом случаеаназ-ся делителем или множителемb. Пустьа- целое число и оно больше 1, тогдаапростое число если его единственным положительным делителем будут 1 и самоа. В противном случаеаназ-ся составным. Любое целоеn>1 может быть представлено единственными образом с точностью до порядка сомножителя как произведение простых чисел. Существующий с точки зрения криптографии факт состоит в том, что неизвестно никакого эффективного алгоритма разложения чисел на множители, хотя с другой стороны не было получено нижней оценки временной сложности разложения. Неизвестны эффективные методы восстановления двух простых чиселp иqиз произведенияn=pq. Наибольший общий делитель чисела иb(НОД(а,b)) - это наибольшее целое делящее одновременноа иb. В эквивалентной формеа иbесть то единственное натуральное число, которое делита иbи делится на любое целое, делящее иаиb. Наименьшее общее кратное - есть наименьшее натуральное число, делящееся и нааи наb. НОД может быть вычислен с помощью алгоритма Евклида. Он реализуется цепочкой неравенств:а=bq₁+r₁, 0<r₁<b; b=r₁q₁+r₂, 0<r₂<r₁; r₁=r₂q₃+r₃, 0<r₃<r₂;....; r_k-2=r_k-1q_k+r_k, 0<r_k<r_k-1; r_k-1=r_kq_k+1. Остановка гарантируется, т.к. остатки от деленияr_iобразуют строгую убывающую последовательность натуральных чисел. Из этой цепочки получаем, чтоr_k- общий делительаиb. И более того, что общий делительа иbделит в свою очередьr_k.318=2001+118; 200=1181+82; 118=821+36; 82=362+10; 36=103+6; 10=61+4; 6=41+2; 4=22. Оценим временную сложность алгоритма: можно видеть, что алгоритм выполняющий обычное деление выполняется за квадратичное время. Итоговая оценка была бы все еще экспоненциальной если бы выполнялась операцияr_i+1<r_i, однако для всехi r_i+2<r_i/2. Т.о. временная сложность - самая большая кубическая. Считывая цепочку равенств снизу вверх найдем суммарно за кубическое числаx иy, такие, что НОД(а,b)=xа+yb.Говорят, чтоасравнимо сbпо модулю:аb(modm) еслиm делит разностьа-b: числоm2. Для любого целогоxв точности одно из чисел 0,1,...,m-1 сравнимо с х по модулюm. Число наз-ся наименьшим неотрицательным остатком х по модулюm, если оно сравнимо с х по модулюm: (x, modm). [x]- целая часть х, т.е. наибольшее целоех. (x, modm)=x-[x/m]m. Еслиаиmвзаимно просты, то тогда сущ-етx иy, такие что выполняется равенство: 1=xа+ym, т.е.xа1(modm). След-но, целое число х наз-ся обратным капо модулюm. Обратное число определяется однозначно если считать сравниваемые числа равными. Сложность нахождения обратного числа примерно такая же как и у алгоритма Евклида. Отсюда следует, что и сравнениеаzb(modm)может быть решено за кубическое время. Для нахожденияzсначала вычисляетсяа^-1(modm) и умножается наb.

Поиск секретной лазейки

Задача. Известен рюкзачный вектор B=(b₁,...,b_n), где В явл-ся открытым ключом. Известно, что вектор В получен из сверхрастущего вектора А сильным модульным умножением отн-но модуляmи множителяt. Вектор А и числаm иt- неизвестны, необходимо их найти.t^-1u(modm). Вычислениеuпоtилиtпоuравносильно применению алгоритма Евклида. Св-во Евклидовости утверждает, что для целого числааи ненулевого целого числаbсущ-ет единственное частноеqи остаток. Рассмотрим алгоритм поиска лазейки. Сделаем след-щие допущения: 1) фиксируется константа, пропорциональнаяd>1; 2) затем выбирается модуль изdn двоичных разрядов, гдеn - число компонентов вектора В; 3) компоненты а_iсверхрастущего вектора А состоят изdn-1-n+i битов. Еслиdне явл-ся целым, тоdnзаменяется на[dn].Старший разряд в каждой компоненте равен 1, это гарантирует, что А всегда будет сверхрастущим и ************************. Еслиn=100 иd=2, тоnсостоит из 200 двоичных разрядов, а число разрядов компонент а₁,...,а₁₀₀возрастает от 100 до 199. Следует отметить, что при построении алгоритма **********************. Нас устраивает любая параu иm, такая что при условии, чтоuиmудовлетворяют ограничениям, накладываемым на модульное умножение в отношении В. Вектор А явл-ся сверхрастущим и *****************************. Парыuиmбудем называть секретными парами. Как только удастся отыскать хотя бы одну секретную пару можно начать расшифровку.