Элементы теории кодирования и криптография

Элементы теории кодирования и криптография Сосновский Юрий Васильевич yury_sosnovsky@mail.ru §1 Наибольший общий делитель П.1 Делимость и ее свойства В нашем курсе мы будем работать с двумя числовыми множествами ℕ={1,2,3,….}, ℤ={0,1,-1,2,-2,…}. Опр. Говорят, что целое число a делится нацело на ненулевое целое число b, если существует целое число c, такое , что a=bc. Факт делимости нацело записывается следующим образом . Примеры. Так как , то число 6 делится нацело на числа 2,-2, 3,-3. Это же можно записать в виде формул . Аналогично показывается, что . Этот пример показывает что делимость не зависит от знака числа. Не стоит путать факт делимости нацело и операции деления. Например, запись означает, 8 можно представить в виде произведения двух целых множителей, один из которых 4. Запись означает, что надо выполнить операцию деления числа 8 на число 5 и получить частное . Простейшие свойства деления соберем в теорему. Т. 1. Для любых натуральных чисел a,b,c справедливы следующие свойства: 1) ; 2) если и , то ; 3) если и , то ; 4) если , то ; 5) если , то ; 6) если и , то . Доказательство. 1) Так как справедливо равенство , то и . 2) Так как и , то по определению делимости нацело , где - натуральные числа. Поскольку и поскольку произведение -целое число, то . 3) Если и , то , где - натуральные числа. Поскольку и поскольку –натуральное число, то . 4) Если , то , для некоторого натурального . Поскольку , то . 5) Если , то , для некоторого натурального . Так как натурально , то . Умножая это неравенство на натуральное число , получим , т.е. . 6) Если и , то согласно уже доказанному свойству 5) справедливы неравенства и , из которых следует равенство . Отметим, что свойство3) утверждает, что из делимости нацело слагаемых следует делимость нацело суммы. Однако из делимости нацело суммы вовсе не следует делимость нацело слагаемых. Например, сумма 1+1=2 делится нацело на 2, но ни одно из слагаемых не делится на 2. П.2. Теорема о делении с остатком Если произведение двух целых чисел всегда является целым числом, то частное от деления целого числа на ненулевое целое существует, но не всегда является целым числом, т.е. операция выводит нас из множества целых чисел. Поэтому на множестве целых чисел вместо обычной операции деления используется операция деления с остатком. Для ее обоснования потребуется теорема о делении с остатком. Т.2. Для любого целого и любого натурального существуют и единственные целые и такие, что . Доказательство. Докажем сначала существование целых и . Выберем наибольшее кратное числа , не превосходящее . Тогда -целое число и по выбору кратного справедливы неравенства . Положим . Как разность двух целых чисел и число тоже будет целым. Последнее равенство перепишем в виде . Так как , то, вычитая из обеих частей этого неравенства число , получим и справедливость неравенства доказана. Так как , то, вычитая из обеих частей этого неравенства число , получим и справедливость неравенства . Таким образом доказано существование целых чисел и , удовлетворяющих равенству и неравенствам из теоремы. Пусть наряду с найденными нами целыми числами и существуют целые числа и , что . Так как , то , то кратное числа не превосходит . Так как , то , то следующее кратное числа уже превосходит . Следовательно, число является наибольшим кратным числа , не превосходящим числа . Тогда кратные и совпадают, значит числа и тоже совпадают. Поскольку число натурально, то из равенства следует, что . Единственность доказана. Поскольку на семинарских занятиях мы с вами уже поработали с теоремой о делении с остатком, оценили ее значение для математики и для практики, то в лекциях на этом останавливаться не будем. П.3. Наибольший общий делитель Натуральное число называется общим делителем натуральных чисел и обозначается ), если . Например, 2-од(4,16,28). Согласно свойству 5) из т.1 для любого общего делителя натуральных чисел справедливы неравенства . Поэтому множество общих делителей любого набора натуральных чисел конечно и из всех общих делителей всегда можно выбрать наибольший. Например, общие делители чисел 4, 16, 28 не превосходят 4. Ясно что среди них можно выбрать наибольший. Натуральное число называется наибольшим общим делителем натуральных чисел и обозначается ), если самый большой общий делитель этих чисел. Чтобы научиться находить наибольший общий делитель у любого количества натуральных чисел, начнем со случая двух чисел. Нам понадобятся два вспомогательных утверждения. Л.1. Если натуральное число нацело делится на натуральное число , то . Доказательство. По условию леммы . Кроме того, по свойству 1) из теоремы 1. Значит -общий делитель чисел и . Пусть -общий делитель чисел и . Тогда по определению и . По свойству 5) из теоремы 1 из условия следует неравенство , что - наибольший общий делитель чисел и . Л.2. Если для натуральных чисел и справедливо равенство для некоторого целого неотрицательного и натурального , то Доказательство. Пусть . Тогда и . По свойству 4) из теоремы 1получаем, что , а по свойству 3) из теоремы 1 получаем, что , значит . Пусть . Тогда и . Так как - натуральное число и , то по свойству 3) из теоремы 1, в котором вместо суммы поставлена разность, получаем, что . Значит . Этими рассуждениями мы показали, что пары чисел и имеют одни и те же общие делители . Значит наибольшие общие делители этих пар чисел совпадают. П.4. Алгоритм Евклида нахождения наибольшего общего делителя двух чисел Вначале опишем пошагово алгоритм Евклида. Возьмем два натуральных числа и . Пусть для определенности . На первом шаге разделим число на число с остатком и получим . Если , то и по лемме 1 получаем, что . Если , то по лемме 2 На втором шаге разделим с остатком число на число с остатком и получим . . Если , то и по лемме 1 получаем, что . Если , то по лемме 2 На третьем шаге разделим с остатком число на число и получим и проделаем аналогичные рассуждения. Поскольку при каждом шаге остатки строго уменьшаются, оставаясь целыми неотрицательными, то не позднее чем через шагов остаток станет равным нулю и мы найдем наибольший общий делитель чисел и . А теперь сформулируем теорему, которая следует из описания алгоритма Евклида. Т.3. Наибольший общий делитель двух натуральных чисел равен последнему, отличному от нуля, остатку в алгоритме Евклида. Для иллюстрации найдем ) по алгоритму Евклида. Для этого проделываем столько шагов в алгоритме Евклида, пока не получим нулевой остаток. +10, , , . Согласно лемме 2 справедливы равенства . Согласно лемме 1 справедливо равенство . П.5. Свойства наибольшего общего делителя двух чисел Т.4. Для любых трех натуральных чисел справедливо равенство . Доказательство. Поскольку число положительно, то нетрудно заметить, что если в алгоритме Евклида для чисел на первом шаге мы получили выражения , то в алгоритме Евклида для чисел мы получим выражения , т.е. все равенства и неравенства умножились на положительное число . Точно такая же картина будет наблюдаться на всех остальных шагах алгоритма Евклида. В частности, и последний ненулевой остаток умножится на число . Но последний ненулевой остаток равен . Поэтому . Т.5. Для любых натуральных чисел существуют целые числа , такие, что (равенство Безу). Доказательство проведем индукцией по количеству шагов в алгоритме Евклида. Если в алгоритме Евклида для чисел потребовался всего один шаг, то и . Равенство будет искомым равенством Безу. Допустим, что равенство Безу можно найти для всех пар натуральных чисел, для которых в алгоритме Евклида надо проделать шагов. Предположим, что для чисел в алгоритме Евклида надо проделать шаг. Тогда для чисел в алгоритме Евклида надо проделать шагов. По индукционному предположению для чисел существуют целые , такие, что . Чтобы получить равенство Безу для чисел , выразим из уравнения на первом шаге , подставим в равенство Безу для чисел и получим . Поскольку числа целые, то полагая , получим равенство Безу для чисел . Т.6. Наибольший общий делитель d любой пары натуральных чисел делится нацело на любой общий делитель c чисел . Доказательство проведем индукцией по количеству шагов k в алгоритме Евклида для пары . Так как , то и . Если , то, как мы раньше отмечали, , т.е. и . Пусть наибольший общий делитель любой пары, для которой в алгоритме Евклида требуется выполнения k шагов, делится нацело на любой их общий делитель. Пусть для пары в алгоритме Евклида требуется выполнения k+1 шага. Тогда для чисел в алгоритме Евклида требуется выполнения k шагов. По индукционному предположению наибольший общий делитель чисел , который совпадает с наибольшим общим делителем пары , т.е. с d, будет делиться нацело на любой общий делитель пары . Поскольку общие делители у пар чисел и одинаковы, то c- общий делитель и по индукционному предположению . П.6. Взаимно простые числа Два натуральных числа называются взаимно простыми, если их наибольший общий делитель равен 1. Коротко это определение можно записать так: числа взаимно просты )=1. Числа 5 и 8 взаимно просты, а числа 6 и 8 не взаимно просты. В этом можно убедиться при помощи алгоритма Евклида. Нужные нам для теории и практики свойства взаимно простых чисел соберем в теорему. Т.7. Для любых натуральных чисел справедливы следующие свойства: 1) Числа взаимно просты существуют такие целые , что . 2) Если и числа взаимно просты, то . 3) Число взаимно просто с числом число взаимно просто и с числом и с числом . 4) Если и числа взаимно просты, то . Доказательство.1) Если числа взаимно просты, то )=1. Согласно теореме 5 существуют такие целые числа , что . Пусть существуют такие целые числа , что и пусть . Тогда и . По теореме 1.4 произведения и тоже делятся нацело на . По теореме 1.3 их сумма, равная 1 тоже делится нацело на . Тогда по теореме 1.5 справедливо неравенство . Следовательно , т.е. у чисел общим делителем может быть только 1, поэтому )=1 и числа взаимно просты. 2) Пусть и числа взаимно просты. Тогда существуют такие целые числа , что . Умножая это равенство на , получим . Поскольку и , то согласно теоремы 1.4. По теореме 1.3 сумма , равная , тоже делится нацело на . 3) Если число взаимно просто с числом , то существуют такие целые , что . Мы видим, что для натуральных чисел существуют такие целые и , что . Следовательно, числа и взаимно просты. Аналогично показывается, что числа и тоже взаимно просты. Если число взаимно просто и с числом , и с числом , то существуют такие целые , что . Перемножая эти равенства, получим цепочку равенств , последнее из которых показывает, что числа и взаимно просты. 4) Пусть и числа взаимно просты. Тогда существуют такие целые , что . Умножая это равенство на , получим равенство . Так как , то , значит . По аналогичной причине . Поскольку каждое из двух слагаемых суммы делится нацело на , то и сумма, равная , тоже делится нацело на . Отметим, что очень важные для теории и для практики свойства 2) и 4) перестают быть справедливыми, если убрать требование взаимной простоты. Действительно, произведение делится нацело на 6, но ни один из множителей ни 3, ни 4 не делится нацело на 6. Следовательно, для произвольных трех натуральных чисел свойство 2) не верно. Поскольку число 12 делится нацело и на 4, и на 6, но не делится на их произведение, то свойство 4) тоже перестает быть справедливым для произвольных натуральных чисел. П.7. Решение диофантова уравнения первой степени с двумя неизвестными Алгебраическое уравнение называется диофантовым, если все его коэффициенты являются целыми числами и у уравнения требуется найти только целочисленные решения. Для диофантовых уравнений первой степени существует алгоритм нахождения целочисленных решений. Этот алгоритм позволит нам находить секретные ключи для абонентов криптосистемы RSA. Изложим этот алгоритм в следующей теореме. Т.8. Пусть -диофантово уравнение первой степени с двумя неизвестными и пусть . Тогда 1) Если правая часть уравнения (1) не делится нацело на , то уравнение (1) не имеет целочисленных решений. 2) Если , то уравнение (1) имеет бесконечно много целочисленных решений, которые задаются формулами где -некоторое частное решение уравнения (1), –произвольное целое число. Доказательство. Так как , то , поэтому для некоторых целых , . 1) Пусть не делится нацело на , но пусть уравнение (1) имеет целочисленное решение , . Тогда справедливо равенство Так как , то , . Значит их сумма , равная тоже делится нацело на вопреки предположению. 2) Предположим, что . Тогда для некоторого целого . Так как ), то согласно теореме 5 существуют такие целые , что справедливо равенство (равенство Безу). Умножая это равенство на , получим равенство , которое показывает, что пара целых чисел является частным решением уравнения (1). Подставим теперь в уравнение (1) формулы (2) и получим т.е. значения переменных, заданные по формулам (2), превращают уравнение (1) в верное равенство. Следовательно, имея одно частное решение уравнения (1), мы при помощи формул (2) получим бесконечно много решений уравнения (1). Для завершения доказательства теоремы нам осталось доказать, что всякое решение , уравнения (1) задается формулами (2). Так как , –решение уравнения (1), то справедливо равенство Вычитая из равенства (4) равенство (3), получим Откуда . Подставляя в это равенство выражения для и , получим равенство . Сокращая на , получим равенство . (5) Поскольку , то после сокращения на получим, что =1, т.е. числа взаимно просты. Из равенства (5) следует, что . Согласно теореме 7.2 из условия и взаимной простоты чисел следует, что , т.е. для некоторого целого . Откуда и значение получено по первой формуле из (2) . Подставляя выражение для в равенство (5), получим . Сокращая последнее равенство на , приходим к равенству , из которого следует, что значение получено по второй формуле из (2). Доказательство теоремы 8 содержит способ решения диофантовых уравнений первой степени от двух переменных. Покажем это на примере решения диофантова уравнения . Найдем . Поскольку знак числа не влияет на делимость, то . Применяя к числам 56 и 82 алгоритм Евклида, получим равенства Согласно теореме 3 . Поскольку , то согласно теореме 8 уравнение имеет бесконечно много целочисленных решений, задаваемых формулами (2). В формулах (2) нам известны все числа, кроме частного решения , нашего уравнения. Прежде чем найти это частное решение, найдем тождество Безу для чисел Для этого выразим из предпоследнего равенства в алгоритме Евклида остаток . Подставим в это равенство выражение для предыдущего остатка , полученное из предыдущего равенства, и получим . Подставим в это равенство выражение для предыдущего остатка из первого равенства, и получим . Это равенство и есть искомое равенство Безу. Частное решение уравнения получается из равенства Безу умножением последнего на 9. Действительно, вычисляя произведения в скобках и в правой части равенства , получим равенство , которое показывает, что в качестве частного решения исходного уравнения можно взять . Формулы (2) из теоремы 8 позволяют выписать общее решение уравнения . §2. Основная теорема арифметики П.1. Простые и составные числа Согласно теореме 1.1 из §1 всякое натуральное число , отличное от 1, имеет по крайней мере два натуральных делителя и . Это простое замечание служит отправной точкой двух очень важных в теории чисел определений. Отличное от 1 натуральное число называется простым, если оно не имеет натуральных делителей, отличных от 1 и от . Отличное от 1 натуральное число называется составным, если оно имеет натуральный делитель, отличный от 1 и от . Числа являются простыми, поскольку имеют в точности два натуральных делителя 1 и самого себя. Числа являются составными, поскольку , т. е. эти числа имеют более двух натуральных делителей. Отметим, что натуральное число 1 имеет только один натуральный делитель, поэтому оно не является ни простым, ни составным. Все остальные натуральные числа являются либо простыми, либо составными. Важную роль простых чисел подчеркивает следующая теорема, доказанная еще древними греками. Т.1. Всякое отличное от 1 натуральное число либо само является простым, либо является произведением простых чисел. Доказательство проведем индукцией по числу . Если , то 2- простое число и доказывать нечего. Предположим, что всякое отличное от 1 натуральное число, меньшее , является либо простым, либо произведением простых чисел. Докажем, что аналогичное свойство справедливо для числа . Поскольку всякое отличное от 1 число является либо простым, либо составным, то рассмотрим два случая. Если число является простым, то доказывать нечего. Если число является составным, то оно имеет натуральный делитель , отличный от 1 и от , т.е. для некоторого натурального . Так как то . Так как , то , т.е. b-отличное от 1 натуральное число, меньшее . Из равенства следует, что , значит . Если , то вопреки выбору . Следовательно, . Если , то . Сокращая равенство на , получим равенство , противоречащее выбору . Следовательно, , тогда , т.е. - отличное от 1 натуральное число, меньшее . Тогда для чисел и применимо предположение индукции, т.е. каждое из этих чисел либо является простым, либо разлагается в произведение простых чисел. В этом случае число , являющееся их произведением, разлагается в произведение двух или большего числа простых чисел. В школьном курсе арифметики широко применяется алгоритм разложения натуральных чисел в произведение простых чисел. П.2. Бесконечность множества простых чисел Т.2.(Евклид) Множество простых чисел бесконечно. Доказательство. Допустим, что множество простых чисел конечно и пусть - все простые числа и их в точности штук. Рассмотрим натуральное число . Так как число больше 1, то по теореме 1оно либо является простым, либо является произведением простых чисел. В любом случае у числа имеется простой делитель . Поскольку , то натуральное число при делении на 2 дает остаток 1, следовательно число не делится нацело на 2. По аналогичной причине натуральное число не делится нацело ни на 3, ни на 5,…, ни на .Так как , то простое число отлично от простых чисел . Поэтому простых чисел не штук, а по крайней мере на 1 больше. Это противоречие показывает, что простых чисел бесконечно много. Теорема Евклида играет важную роль в теории и в практике, в частности, в криптографии. П.3. Характеристические свойства простых чисел В следующих двух теоремах мы приведем такие два свойства простых чисел, которыми составные числа не обладают. Поэтому эти свойства называют характеристическими свойствами простых чисел. Т.3. Пусть - простое число. Тогда для любого натурального либо , либо числа и взаимно просты. Доказательство. Пусть . Тогда . Поскольку - простое число и , то либо , либо . Если , то из условия следует, что . Если , т.е. , то числа и взаимно просты. Т.4. Если произведение нескольких натуральных чисел делится на простое число , то хотя бы один из множителей , ,…, делится на простое число . Доказательство. Так как число простое, то согласно теореме 3 либо , либо числа и взаимно просты. Если , то все доказано. Если же числа и взаимно просты, то из условия делимости на произведения двух чисел и взаимной простоты первого множителя и числа , следует, что второй множитель делится нацело на . Мы оказались точно в такой же ситуации, как и в условии теоремы, только количество сомножителей уменьшилось на 1. Проделывая аналогичные рассуждения на каждом шаге, мы либо докажем теорему, либо уменьшаем количество сомножителей на 1. Если нам пришлось проделать шаг, то в произведении остался только один множитель , который нацело делится на . Теорема 4 очень часто используется как в теории, так и при решении задач. Еще раз напомним, что для составных чисел она не верна. Действительно, произведение делится нацело на 4, но ни один из множителей 6,9 не делится нацело на 4. П.4. Основная теорема арифметики Мы все подготовили для доказательства основной теоремы арифметики. Т.5. (Основная теорема арифметики) Всякое отличное от 1 натуральное число разлагается в произведение простых чисел, причем это разложение единственное с точностью до порядка множителей. Доказательство. Существование разложения в произведение простых чисел было доказано в теореме 1, если считать одно простое число как произведение одного сомножителя. Докажем единственность разложения в произведение простых чисел. Допустим, что отличное от 1 натуральное число раскладывается в произведение простых чисел двумя способами: (1) где - простые числа, Так как произведение делится нацело на , то и произведение тоже делится нацело на . Поскольку число простое, то согласно теореме 4 один из множителей этого произведения, скажем, делится нацело на . Так как –простое число, то оно отлично от 1. Тогда число являясь отличным от 1 делителем простого числа , обязано с ним совпадать, т.е. . Сокращая обе части равенства (1) на получим равенство . (2) В равенстве (2) аналогичные рассуждения проведем для и т.д. до тех пор, пока в одной части равенства не возникнет 1. Тогда и в другой части равенства обязана стоять 1. Следовательно количества простых множителей в обеих частях равенства (1) равны и множители попарно совпадают. П.5. Описание делителей натурального числа Согласно теореме 1.5 из §1 все делители натурального числа не превосходят . Однако не все числа, меньшие , являются делителями числа . Например, число не является делителем числа , хотя и не превосходит его. Описание всех делителей натурального числа может быть получено с помощью следующей теоремы. Т.6. Для любого натурального числа , отличного от , справедливы следующие утверждения: 1) Если число является делителем числа , то либо , либо разложение числа на простые множители является частью разложения числа на простые множители. 2) Произведение множителей любой непустой части разложения числа на простые множители однозначно определяет делитель числа . Доказательство. 1) Если отличное от натуральное число является делителем натурального числа , то для некоторого натурального числа справедливо равенство . Значит, разложение числа на простые множители будет являться частью разложения числа на простые множители. 2) Возьмем какую-нибудь часть из разложения числа на простые множители и обозначим через произведение отобранных множителей. Если оказалось, что были выбраны все простые множители из разложения числа , то согласно теореме 5 и, очевидно, что число является делителем числа . Если изначально были выбраны не все простые множители из разложения числа , то обозначим через произведение не выбранных простых множителей. Поскольку разложения чисел и на простые множители совпадают, то из теоремы 5 следует, что . Следовательно, число является делителем числа . Теорема 6 позволяет находить все делители натурального числа по его разложению на простые множители. Поясним этот способ на примере числа , разложив его на простые множители . Вначале выпишем делитель числа , который не содержит ни одного простого множителя из разложения числа . Затем выпишем числа ; ; ; ; , содержащие по одному, двум, трем, четырем и пяти множителям соответственно из разложения числа на простые множители. Согласно теореме 6 все указанные числа являются делителями числа и других делителей у числа нет. Общим кратным натуральных чисел и называется натуральное число m, делящееся и на , и на . Наименьшим общим кратным двух натуральных и называется наименьшее из их общих кратных. Поскольку произведение делится нацело и на , и на , то оно является общим кратным чисел и . Перебирая все натуральные числа, не превосходящие найдем наименьшее общее кратное чисел и . Этими рассуждениями мы показали, что для любых двух натуральных чисел наименьшее общее кратное существует. Но таким способом его вычислять нерационально. Теорема 6 позволяет находить наибольший общий делитель и наименьшее общее кратное любой пары натуральных чисел. Поясним этот способ на примере пары чисел Разложив эти числа в произведение простых множителей, получим равенства . По теореме 6.1 в разложении на простые множители любого общего делителя чисел и должно быть не более двух множителей, равных , не более одного множителя, равного , а множителей, равных или не должно быть вовсе. Чтобы общий делитель был наибольшим, надо в его разложение включить наибольшее возможное количество простых множителей. Следовательно, . Согласно теореме 6.2 в разложении на простые множители любого общего кратного чисел и должно быть не менее трех множителей, равных ; не менее двух множителей, равных ; множителей, равных и , должно быть хотя бы по одному. Чтобы общее кратное было наименьшим, надо в его разложение включить наименьшее возможное количество общих простых множителей. Значит, . П.6. Метод Ферма разложения на множители Для обоснования алгоритма Ферма разложения натуральных чисел на отличные от единицы множители нам потребуется следующая теорема. Т.7. Если - составное нечетное число, то существуют целые неотрицательные числа , такие, что . Доказательство. Поскольку число составное и нечетное, то справедливо равенство , где - нечетные натуральные числа, удовлетворяющие неравенствам . Числа найдем из системы уравнений . Складывая эти уравнения и деля на 2, получим, что Вычитая из первого уравнения второе и деля на 2, получим, что Поскольку числа были нечетными натуральными и поскольку , то числа будут целыми неотрицательными, причем . Так как , то , откуда . Так как - отличные от единицы нечетные натуральные числа, то . Следовательно . Тогда , откуда . Значит, выполняются и все ограничения на число . Используя теорему, построим пошаговый алгоритм Ферма разложения отличного от 1 нечетного натурального числа в произведение отличных от 1 множителей. Шаг 1. Присвоим значения . Шаг 2. Если , то присвоить значения . Напечатать « Справедливо разложение » и перейти к шагу 5. Шаг 3. Если , то присвоить значения и перейти к шагу 2. Шаг 4. Если , то напечатать «Число является простым» и перейти к шагу 5. Шаг 5 Окончание алгоритма. Обращаю Ваше внимание на то, что в алгоритме через […]обозначается целая часть числа. Кроме того отметим, при число . Действительно, если , то и . Откуда . Оценим разность . Однако описание шага 3 показывает, что число может превосходить число самое большое на 1. Противоречие доказывает, что . Разложим при помощи алгоритма Ферма число в произведение двух нетривиальных множителей. На первом шаге алгоритма присвоим значения . Поскольку , то переходим к шагу 3. Так как то присваиваем значения и переходим к шагу 2 . Поскольку , то переходим к шагу 3. Так как то присваиваем значения и переходим к шагу 2. Поскольку , то переходим к шагу 3. Так как то присваиваем значения и переходим к шагу 2. Поскольку , то переходим к шагу 3. Так как то присваиваем значения и переходим к шагу 2. Поскольку , то переходим к шагу 3. Так как то присваиваем значения и переходим к шагу 2. Поскольку , то переходим к шагу 3. Так как то присваиваем значения и переходим к шагу 2. Поскольку , то переходим к шагу 3. Так как то присваиваем значения и переходим к шагу 2. Поскольку справедливо равенство , то присваиваем значения . В ответе пишем, что справедливо равенство , т.е. число разлагается в произведение двух множителей . П.7. Количество делений в алгоритме Евклида. В отличие от громоздкого способа Ферма разложения на множители, алгоритм Евклида является очень быстрым алгоритмом. Об этом говорится в теореме Ламе(1795-1870). Т.8. Количество делений в алгоритме Евклида для двух натуральных чисел и , не превосходит числа - пятикратного количества цифр в десятичной записи меньшего из них. Доказательство. Пусть . Тогда значное число. Применим к числам и алгоритм Евклида и получим Положим и индукцией по покажем, что справедливо неравенство , (3) где , =1,61…- корень многочлена , т.е. справедливо равенство При имеем При имеем , тогда . Предположим, что неравенство (3) справедливо для и для и докажем его для . Из алгоритма Евклида можем записать = . Здесь мы воспользовались равенством , поскольку - корень многочлена . При имеем . Непосредственным вычислением убеждаемся, что , т.е. . Справедлива цепочка неравенств . Логарифмируя неравенство по основанию 10, получим , откуда и значит . §3. Теоретическое обоснование криптосистемы RSA П.1 Сравнения и их простейшие свойства Понятие сравнения Вы уже изучали в курсе теории чисел. Поскольку это понятие и его свойства играют ключевую роль в криптосистеме RSA, то мы отведем два пункта на повторение. Пусть m- отличное от единицы натуральное число. Говорят, что целое число a сравнимо с целым числом b по модулю m и пишут , если разность нацело делится на m. Формульно определение сравнения можно записать следующим образом Например, , поскольку С другой стороны, , поскольку и не делится нацело на . Простейшие свойства сравнений соберем в теорему. Т. 1. Пусть m- отличное от единицы натуральное число. Тогда для любых целых справедливы следующие свойства: 1) ; 2) если , то ; 3) если , то ; 4) если и , то ; 5) если и , то а) ; б) ; в) для любого натурального k; 6) для любого натурального k справедлива равносильность ; 7) всякое целое число сравнимо по модулю со своим остатком при делении на ; 8) любые два разных остатка при делении на не сравнимы по модулю ; 9) если и число взаимно просто с модулем , то . Доказательство. 1) Так как и , то . 2) Так как , то . Значит . 3)Так как , то . Тогда , значит . 4) Поскольку и , то . Тогда . Значит . 5) Поскольку и , то . а) Так как , то . б) Так как , то . в) Если в 4б) вместо сравнений , взять два одинаковых сравнения , и воспользоваться уже доказанным свойством 4б), то получим . Если в 4б) вместо сравнений , взять сравнения , и воспользоваться уже доказанным свойством 4б), то получим и т. д. 6) Если , то , тогда . Значит . Если теперь , то , тогда . Значит . 7) По теореме о делении с остатком можем записать , где - целые неотрицательные числа, причем . Тогда . Значит . 8) Пусть - два различных остатка при делении на . Пусть для определенности . Если , то . Тогда согласно теореме 1 из §1 справедливо неравенство . Цепочка неравенств показывает, что число не может быть остатком при делении на . Это противоречие показывает, что два различных остатка при делении на не сравнимы по модулю . 9) Если , то . Поскольку числа и взаимно просты, то из условия следует, что . Значит . Свойства 1)-8) у сравнений такие же как, у равенств, поэтому обозначение сравнения очень похоже на обозначение равенства. Свойство 9) для равенств формулируется по-другому. Действительно, если равенства можно сокращать на любое ненулевое число, то сравнения можно сокращать только на числа, взаимно простые с модулем. Теорема 1 очень сильно облегчает вычисления в криптосистеме RSA. Кроме того, теорема 1 позволяет легко выводить признаки делимости. Т.2. (Общий признак делимости Паскаля) Пусть - десятичная запись числа и пусть для натурального и целых справедливы сравнения Тогда натуральное число делится нацело на тогда и только тогда, когда на делится нацело число . Доказательство. Умножим 1-е сравнение из теоремы 2 на , 2-е сравнение на и т.д. умножим е сравнение из теоремы 2 на . Согласно теореме 1.1 и 1.5 будут справедливы сравнения Складывая почленно эти сравнения и применяя теорему 1.5, получим, что , т. е. . С помощью этого сравнения мы получаем цепочку равносильностей , которая и завершает доказательство теоремы 2. П.2. Малая теорема Ферма В курсе теории чисел эту теорему вам доказывали. В целях замкнутости изложения мы докажем ее еще раз. Т.3.(Малая теорема Ферма) Пусть - простое число. Тогда для любого целого , взаимно простого с , справедливо сравнение . Доказательство. Возьмем все ненулевые остатки при делении на . Их в точности штук. Умножим каждый из этих остатков на число , и получим последовательность чисел . (1) Пусть – остатки при делении на взятых по порядку чисел последовательности (1). Тогда по теореме 1.7 будут справедливы сравнения (2) Если равны какие–нибудь два остатка , где , то согласно теореме 1.2 будет справедливо сравнение . Тогда с учетом сравнений (2) и теоремы 1.4 получим, что . Откуда . Поскольку числа и взаимно просты, то из условия следует, что , т.е. . Тогда согласно теореме 1.8 . Следовательно, числа последовательности попарно различны. Если , то . Поскольку числа и взаимно просты, то , чего не может быть, так как - ненулевой остаток при делении на и значит . Следовательно, все числа последовательности отличны от нуля. Мы показали, что - попарно различные ненулевые остатки при делении на . Поскольку их штук, то это все различные ненулевые остатки при делении , т.е. это числа , но, возможно, записанные в другом порядке. Тогда, перемножая сравнения (2), получим (3) Поскольку числа являются остатками при делении на , то они не делятся нацело на . По свойству простых чисел они взаимно просты с . Сокращая согласно теореме 1.9 сравнение (3) последовательно на числа , взаимно простые с модулем , получим требуемое в теореме 2 сравнение . П.3. Теоретическое обоснование криптосистемы RSA Теоретическое обоснование криптосистемы RSA состоит всего из одной теоремы. Т.4. Пусть - два различных простых числа и пусть . Если -такие натуральные числа, что , то для любого натурального справедливо сравнение . Доказательство. Для доказательства сравнения достаточно показать, что . Так как - различные простые числа, то они взаимно просты. Поэтому условие будет выполнено, если будут выполнены два условия и . Если , то , тогда и и первое условие выполнено. Пусть поэтому не делится нацело на , тогда по свойству простых чисел число взаимно просто с и по теореме Ферма справедливо сравнение . Поскольку , то т. е. для некоторого целого неотрицательного . Откуда . С учетом сравнения можем записать . Из определения сравнения получаем, что . Таким образом при любом натуральном выполняется первое условие. Аналогично доказывается справедливость второго условия . Как отмечалось выше, из двух этих условий вытекает теорема 3. 4. Разработка и использование криптосистемы RSA П.1. Разработка криптосистемы RSA Авторами криптосистемы RSA являются американские математики Rivest, Shamir, Adleman. Они опубликовали сообщение об этой криптосистеме в 1978 году. Допустим, что разработчику нужно организовать конфиденциальную связь между двумя абонентами А1 и А2 при помощи криптосистемы RSA. Для этого ему потребуется четыре больших простых числа. В учебных целях возьмем и вычислим произведения . Осталось найти натуральные числа и - открытые и секретные ключи абонентов А1 и А2 соответственно, удовлетворяющие сравнению из теоремы 3. Найдем открытый и секретный ключи для абонента А1. Сначала вычислим произведение и разложим его на простые множители . В качестве открытого ключа можно взять любое натуральное число, меньшее 10176 и взаимно простое с ним, например, . Условие о взаимной простоте чисел и легко выполнить, зная разложение числа на простые множители. Секретный ключ будем находить из сравнения и условия , требуемого теоремой 3. Справедлива следующая цепочка равносильностей . Чтобы свести задачу о нахождении секретного ключа к известной нам задаче, рассмотрим диофантово уравнение . Среди всех целочисленных решений этого уравнения нас интересует то, у которого переменная принимает наименьшее положительное значение, поскольку справедливость условия не зависит от переменной . Для решения диофантова уравнения найдем . Для этого применим алгоритм Евклида к числам , Мы получили последовательность остатков 11, 7, 4, 3, 1, 0. Согласно теореме Евклида наибольший общий делитель чисел равен последнему, отличному от нуля остатку в алгоритме Евклида, т.е. в нашем случае . Поскольку правая часть уравнения делится на , то диофантово уравнение имеет бесконечно много целочисленных решений. Если бы , т. е. если бы числа и были не взаимно посты, то диофантово уравнение не имело бы решений. Для разработчика криптосистемы это означало бы, что для такого значения открытого ключа невозможно найти секретный ключ. Чтобы найти тождество Безу для чисел , выразим остаток из предпоследнего равенства в алгоритме Евклида и получим заготовку для тождества Безу . Выражая остаток из равенства в алгоритме Евклида, получим . Подставляя это равенство в заготовку для тождества Безу, получим следующую заготовку для тождества Безу , т. е. . Выражая остаток из равенства в алгоритме Евклида, получим . Подставляя это равенство в заготовку для тождества Безу, получим следующую заготовку для тождества Безу , т. е. . Выражая остаток из равенства в алгоритме Евклида, получим . Подставляя это равенство в заготовку для тождества Безу, получим следующую заготовку для тождества Безу , т. е. . Выражая остаток из равенства в алгоритме Евклида, получим . Подставляя это равенство в заготовку для тождества Безу, получим равенство , из которого легко получается тождество Безу . Тождество Безу показывает, что пара чисел является частным решением диофантова уравнения . Мы знаем, что любое решение этого диофантова уравнения может быть получено по формулам . Поскольку нас интересует целочисленное решение с наименьшим натуральным , то его мы получим при , а именно, . Как ранее отмечалось надо взять . Осталось только проверить, что выполняется сравнение , требуемое теоремой 3. Так как , то сравнение справедливо. После того, как найдена пара ключей для абонента А1 , найдем пару ключей для абонента А2. Для этого вычислим произведение . Возьмем в качестве числа натуральное число, взаимно простое с , например, . Аналогично тому, как делалось выше, сведем нахождение решения сравнения к нахождению целочисленного решения диофантова уравнения с наименьшим натуральным . Оказалось что . Полагая, получим секретный ключ абонента А2. Проверим, что для открытого и секретного ключей абонента А2 выполняется сравнение , требуемое теоремой 3. Так как , то сравнение справедливо. Разработчик сделал свою работу и должен передать криптосистему абонентам А1 и А2 телефонную книгу, в которой напечатаны данные А1 : . A2: . Таким образом числа и , знают все, но их разложение на простые множители не знает никто, кроме разработчика. Открытые ключи , тоже знают все, поэтому они и называются открытыми. Секретные ключи и передаются абонентам А1 и А2 конфиденциально, поэтому ключ знает только абонент А1, а ключ - только абонент А2. П.2. Процесс шифрования Допустим, что абоненту А1 надо конфиденциально передать абоненту А2 дату наивысшего взлета советского школьного математического образования-1956 год- при помощи разработанной криптосистемы. Абонент А1 шифрует сообщение «» при помощи открытого ключа и модуля абонента А2. Процесс шифрования заключается в возведении числа в -ю степень и нахождения остатка при делении числа на . Поскольку согласно теореме 1 из §3 сравнения можно перемножать, возводить в натуральную степень, сравнивать по модулю со своим остатком при делении на , то на этапах процесса шифрования удобнее использовать не равенства, а сравнения по модулю . Вычисление остатка при делении на у чисел типа производится пошагово. Использование свойств степеней, теорема о делении с остатком на и теорема 1.7 из §3 позволяют на каждом шаге понижать степень, а основание степени ограничивать числом . Распишем подробнeе несколько шагов. По свойствам степеней можем записать . При помощи калькулятора можем найти, что . По теореме 1.7 из §3 можем записать, что . Это сравнение позволяет понизить степень . Поскольку и , то справедливы сравнения . Эти сравнения позволяют еще раз понизить степень . Поскольку , то . Понижаем степень при помощи этого сравнения . Поскольку , то справедливы сравнения . Эти сравнения позволяют еще раз понизить степень . Поскольку то , . Так как - остаток при делении на , то процесс шифрования сообщения «» закончился. Абонент А1 отсылает по открытым каналам абоненту А2 зашифрованное сообщение . Процесс дешифровки Получив это сообщение, абонент А2 расшифровывает его при помощи своего секретного ключа тем же самым способом-возведением в степень с последующим нахождением остатка при делении на . Проделаем эти вычисления. Поскольку то справедливо сравнение . Это сравнение позволяет понизить степень . Поскольку , то справедливы сравнения . Эти сравнения позволяют понизить степень . Поскольку , то справедливо сравнение . Это сравнение позволяет понизить степень . Ранее мы показывали, что справедливо сравнение . Понизим с его помощью степень . Поскольку число является остатком при делении на , то согласно теореме 3 оно и есть то сообщение, которое абонент А1 хотел послать абоненту А2. Сделаем несколько замечаний по построению криптосистемы, по процессам шифрования и дешифровки. 1. Для каждого из абонентов разработчик задает значение открытого ключа так, чтобы числа и были взаимно просты. Решая диофантово уравнение , разработчик вычисляет такое его целочисленное решение, у которого переменная принимает наименьшее натуральное значение. Это значение берется за значение секретного ключа . Поскольку при дешифровке приходится возводить натуральные числа в -ю степень, то, чтобы оставаться в натуральных числах, нужно чтобы целое число было положительным. Во избежание лишних вычислений из всевозможных допустимых значений для выбирают наименьшее положительное. Открытый и секретный ключи будут правильно работать, если они удовлетворяют сравнению , требуемому теоремой 3. 2. Надо помнить, что и абонент А1, и абонент А2 знают модули и открытые ключи , но не знают разложения чисел и на простые множители. Секретный ключ знает только его владелец. Поэтому, посылая сообщение абоненту А2, абонент А1 использует модуль и открытый ключ абонента А2. Соответственно, посылая сообщение абоненту А1, абонент А2 использует модуль и открытый ключ абонента А1. 3. При понижении степени возникает вопрос в какую степень лучше возводить? В действительности все эти действия выполняет компьютер. В учебных целях эти действия выполняются вручную. Ясно, что чем в большую степень удается возвести и затем безошибочно найти остаток, тем большее понижение степени получится. Поэтому все зависит от калькулятора, от того числа, которое Вы возводите в степень и от Вашей аккуратности. Например, число 69 можно было бы возводить и в 6-ю степень и делить с остатком на число 11227, число 691 можно было бы возводить и в 4-ю степень, а число 1956 мы возводили в 3-ю степень. 4. Ясно, что зашифрованное число и расшифрованное число должны совпасть, поскольку оба они являются сравнимыми по модулю остатками при делении на . Если произошло несовпадение, то начните с того, что при помощи теоремы 3 проверьте согласованность открытого и секретного ключей у абонента А2. Далее проверьте, что Вы ничего не напутали с модулями и ключами. После чего проверяйте вычисления шифрования и дешифровки пошагово. . Построение больших простых чисел П.1. Терема Поклингтона В 1914 году Поклингтоном была доказана следующая теорема. Т.1. Пусть натуральное число имеет вид , где - натуральные числа, а - простое число, не являющееся делителем числа . Если существует такое целое число , что , то всякий простой делитель числа имеет вид для некоторого натурального . Доказательство. Пусть - простой делитель числа . Согласно условиям теоремы для целого числа справедливо сравнение , т.е. . Так как - делитель числа и , то , т.е. , в частности не делится на . Пусть - наименьшее натуральное число, для которого справедливо сравнение . Число называют порядком элемента по модулю числа . По теореме о делении с остатком можем записать , где - целые неотрицательные числа и . Поскольку , то из определения порядка элемента следует, что , т.е. . Так как и , то не делится нацело на , т.е. не сравнимо с 1 по модулю . Если бы , то , для некоторого натурального . Тогда вопреки сказанному выше. Значит, число = не делится нацело на . Поэтому . Поскольку число не делится на , то согласно теореме Ферма справедливо сравнение . Рассуждая аналогично тому, как из сравнения мы получили условие , мы из сравнения получим условие . Из условий и следует, что , т.е. для некоторого натурального . Отсюда . . Из теоремы Поклингтона аналогичными рассуждениями получается следующая теорема. Т.2. Пусть натуральное число имеет вид , где - натуральные числа, а - простое число, не являющееся делителем числа . Если существует такое целое число , что и что число не сравнимо с 1 по модулю у числа найдется простой делитель вида для некоторого натурального . П.2. Теорема Диемитко Теорема Диемитко лежит в основе получения простых чисел для отечественного стандарта цифровой подписи ГОСТ 34.10-94. Отметим, что с 1 июля 2002 года этот стандарт был заменен на новый ГОСТ 34.10-2001. Теорема 3.( Диемитко, 1988 г.) Пусть q- простое число, не являющееся делителем четного числа , пусть и пусть справедливо неравенство . Если существует такое натуральное число , для которого выполняются два условия , но , то число простое. Доказательство. Допустим, что число составное. Тогда разложим число в произведение степеней простых чисел . Согласно лемме одно из чисел делится нацело на . Можно считать, что . Поскольку , то можно записать . Тогда . Так как , то . Значит . Поскольку , то и . Следовательно, . Если , то и - простое число, вопреки предположению, что составное. Если же , то - четное число, тогда и тоже четное число, вопреки условиям теоремы. Значит . Поскольку -делитель нечетного числа , то -нечетное простое число. Если , то , но 1 не является простым числом. Если , то число четное, но - нечетное простое число. Значит . С учетом неравенства и двух неравенств , можем записать , т. е. получили противоречие , которое доказывает, что число простое. В варианте №40 число равно 397. В нашем случае теорема Диемитко рекомендует искать число в виде , где - четное число. Поскольку требуется, чтобы , то будем брать . Возьмем , тогда . В этом случае условие принимает вид и оно, очевидно, выполнено. Число 1589 не такое и большое, в учебнике Киселева « Арифметика» для 5-6 классов есть таблица всех простых чисел, не превосходящих 6000, из которой можно узнать, что число 1589 не является простым. Можно проверить простоту числа 1589 при помощи деления на все простые числа, не превосходящие . Можно проверить простоту этого числа способом Ферма. В нашем задании это надо сделать при помощи теоремы Диемитко, в которой рекомендуется брать . Так как , то выполнено второе условие из теоремы Диемитко. Проверим справедливость первого условия, понижая степень тем же способом, что и в задании № 3. Поскольку, то . Поскольку и , то . Эти сравнения позволяют понизить степень и упростить сравнение Поскольку и , то . Эти сравнения позволяют понизить степень и упростить сравнение . Поскольку и , то справедливы сравнения . Они позволяют понизить степень и упростить сравнение . Мы видим, что второе условие теоремы Диемитко не выполняется. Если бы число было простым, то из взаимной простоты нечетного числа и числа согласно теореме Ферма следовало бы сравнение , которое как мы проверили не выполняется. Значит число не является простым, т. е. является составным. Если же некотором при , отличном от степени двойки, оказалось не выполненным второе условие, то либо взаимную простоту чисел и надо устанавливать как-то по-другому, либо брать другое значение для . Поскольку значение вместо простого числа привело к составному , то возьмем . Тогда . Ясно, что . Так как , то выполнено второе условие из теоремы Диемитко. Проверим справедливость первого условия. Поскольку , то . Поскольку и , то . При помощи этих сравнений можно понизить степень и упростить сравнение Поскольку , то справедливы сравнения . С их помощью понизим степень и упростим сравнение . Поскольку и , то справедливы сравнения. При помощи этих сравнений можем записать . Поскольку , то . Для числа выполняется и второе условие из теоремы Диемитко. Значит число является простым. П.3. Возможности взлома криптосистемы RSA. Теорема 4. Если абоненты и криптосистемы RSA используют одну и ту же пару простых чисел , то они могут вычислить аналоги секретных ключей друг у друга. Доказательство. Абоненту известен свой модуль , свои открытый и секретный ключи. Кроме того, из телефонной книги он узнает модуль и открытый ключ абонента . В частности, сравнивая свой и абонента модули, он понимает, что для него и для абонента используется одна и та же пара простых чисел. Покажем, как абонент может вычислить аналог секретного ключа абонента . Абонент знает, что его открытый и секретный ключи удовлетворяют сравнению , но не знает числа . По определению сравнения справедливо условие , т.е. . Поскольку , то и абонент знает натуральное число . Пусть . Тогда и . Поскольку числа и взаимно просты и поскольку , то числа и тоже взаимно просты. Так как и числа и взаимно просты, то . Поэтому - натуральное число и число можно представить в виде произведения натуральных чисел и . Если , то тогда и абонент может вычислить число . Пусть . Рассуждая как выше из условия , получим, что , т.е. - натуральное число. Если , то тогда и абонент может вычислить число . Рассуждая аналогично, получим строго убывающую последовательность натуральных чисел . Эта последовательность должна оборваться на каком-то, скажем, на l шаге. По построению это возможно только в случае, когда Следовательно числа и взаимно просты. Тогда диофантово уравнение имеет бесконечно много целочисленных решений. Среди этих решений выберем такое , у которого первая компонента наименьшая положительная. Для положительных чисел , будет справедливо равенство . Перепишем это равенство в виде . Следовательно, , тогда . Значит и выполняется условие согласованности открытого ключа и аналога секретного ключа абонента В доказательстве теоремы 4 содержится способ построения аналога секретного ключа. Покажем, как этот аналог находится, на примере и . От лица разработчика снабдим абонентов и открытыми и секретными ключами. Поскольку , то возьмем и найдем секретный ключ из условия согласованности ключей: для натуральных чисел и должно выполняться сравнение . В нашем случае надо подобрать секретный ключ так, чтобы 187 -1 -1 . Чтобы решить последнее уравнение в натуральных числах рассмотрим диофантово уравнение и найдем все его целочисленные решения. Для этого надо вычислить . Найдем при помощи алгоритма Евклида: , Значит . Поскольку правая часть диофантова уравнения делится нацело на 1, то это диофантово уравнение имеет бесконечно много целочисленных решений. Чтобы все их найти достаточно найти только одно частное решение этого уравнения и воспользоваться формулами. Для нахождения частного решения найдем тождество Безу для чисел и , используя равенства из алгоритма Евклида: . Из последнего числового равенства получаем частное решение диофантова уравнения Общее решение этого уравнения задается формулами Среди этих решений надо выбрать решение с наименьшим натуральным . При получаем решение , которое нам не подходит. При получаем решение При получаем решение с большим, чем у предыдущего решения значением неизвестной . Следовательно, возьмем в качестве секретного ключа число . Проверим условие согласованности ключей и , т.е., что справедливо сравнение 187. Действительно, . Действуя аналогично, по открытому ключу найдем секретный ключ абонента . Для этого нам надо среди всех целочисленных решений диофантова уравнения выбрать решение с наименьшим натуральным . Вычислим при помощи алгоритма Евклида: . Значит . Поскольку правая часть диофантова уравнения делится нацело на 1, то это диофантово уравнение имеет бесконечно много целочисленных решений. Чтобы все их найти достаточно найти только одно частное решение этого уравнения и воспользоваться формулами. Для нахождения частного решения найдем тождество Безу для чисел и , используя равенства из алгоритма Евклида: . Из последнего числового равенства получаем частное решение диофантова уравнения Общее решение этого уравнения задается формулами Среди этих решений надо выбрать решение с наименьшим натуральным . При получаем решение . При получаем решение При получаем решение При других значениях значение неизвестной либо является отрицательным, либо большим чем , натуральным числом. Следовательно, возьмем в качестве секретного ключа число . Проверим условие согласованности ключей и , т.е., что справедливо сравнение 343. Действительно, . Если раньше мы действовали как разработчики, то теперь мы действуем от лица абонента . Мы будем предполагать, что абонент хорошо знаком с криптосистемой RSA. Он знает свои открытый и секретный ключи, знает открытый ключ абонента . Сравнивая модули абонентов и , абонент понимает, что они равны. Согласно основной теореме арифметики из равенства модулей следует равенство пары простых чисел у абонентов и . Поэтому число которое используется для нахождения открытых и секретных ключей, для абонентов и одно и то же. Отметим, что абонент этого числа не знает. Однако абонент может вычислить некоторое кратное числа 3744. Из условия согласованности ключей и следует, что справедливо сравнение 187. Абонент может вычислить число . Дальше абонент поступает так, как в доказательстве теоремы 4. По алгоритму Евклида он найдет : Следовательно, . Теперь абонент может найти число . В доказательстве теоремы 4 было показано, что поэтому ). По алгоритму Евклида абонент вычислит : , . Следовательно, . Аналог секретного ключа абонента абонент найдет среди решений диофантова уравнения . Поскольку он уже посчитал , то ему нужно найти тождество Безу для чисел , используя равенства из алгоритма Евклида: . Последнее равенство показывает, что частное решение диофантова уравнения . Тогда общее решение этого уравнения имеет вид . Из этих выражений видно, что решение с наименьшим натуральным получается при . Поэтому в качестве аналога секретного ключа абонента абонент возьмет число . Покажем, что пара чисел 343 и 12007 согласованы. Действительно, . Значит . Следовательно при помощи чисел 343 и 12007 можно зашифровывать и расшифровывать сообщения в нашей криптосистеме, но при помощи чисел 343 и 775 это будет делаться быстрее.