FN_Alg17 (Лекции 2009), страница 3

Расшифровывание сообщения осуществляется по формуламТеорема 17.7. Если НОД(e, m) = 1, то e — обратимый элемент в Zm .J В соответствии с теоремой 17.3 из условия НОД(e, m) = 1 вытекает, что для некоторыхцелых чисел µ и ν выполняется равенство µe + νm = 1. Это равенство в факторкольце Z/mZпо идеалу mZ означает, что (µ + Z)(e + Z) = 1 + Z. Указанное факторкольцо изоморфно кольцуZm , в котором это равенство трансформируется в следующее: µ0 e = 1, где µ0 — остаток отделения µ на m. IТеорема 17.8. Если k − 1 ...

(p − 1)(q − 1), то S k − S ... n.J Утверждение S k −S ... n означает, что если S 6= 0, то S k−1 = 1 в Zn . Условие k−1 ... (p−1)(q−1)равносильно равенству k − 1 = α(p − 1)(q − 1). Таким образом, утверждение теоремы сводитсяк следующему: если 0 < S < pq, то S (p−1)(q−1) − 1 ... pq. Согласно малой теореме Ферма имеемS p−1 − 1 ... p. Отсюда вытекает, что* S (p−1)(q−1) − 1 ... p.

Аналогично S (p−1)(q−1) − 1 ... q. Согласносвойству 9 заключаем, что S (p−1)(q−1) − 1 ... pq. IÌÃÒÓОпять S p−1 − 1 ... p означает, что S p−1 = 1 в Zp . Но тогда S (p−1)(q−1) = 1 в Zp , что опять-таки эквивалентноотношению S (p−1)(q−1) − 1 ... p.*ÔÍ-12Комплексные числа и Rn как объект для построениясистемы.

Комплексные числа числовойa bкак действительные матрицы второго порядка вида. Кватеринионы как комплексные−b aматрицы второго порядка. Сложение и умножения — матричные. Множество кватернионов какчетырехмерная алгебра над R. Базис этой алгебры. Представление кватернионов в базисе. Таблицабазисных произведений. Сопряженный кватернион как эрмитово сопряженная матрица.

Выводотсюда равенства z1 z2 = z2 z1 . Норма кватерниона. Тождество |z| = z z. Норма произведения.Свойства операций: а) групповые свойства сложения; а) альтернативность умножения: ba = a b;в) ассоциативность; г) нет делителей нуля.ÌÃÒÓ17.5. КватернионыÔÍ-12Предложенная схема может оказаться непригодной, если официальный“ ключ дешифрова”ния d можно заменить другим паразитным“, причем таких паразитных“ окажется много.””Задача взломщика упрощается, так как ему для чтения достаточно найти любой из паразит”ных“ ключей.Теорема 17.8 имеет довольно очевидное усиление: если k − 1 ...

НОК(p − 1, q − 1), то S k − S ... n.Отсюда естественный вывод: при подборе чисел p и q желательно, чтобы НОД(p − 1, q − 1) былкак можно меньше.ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12i = 1, k.ÌÃÒÓÌÃÒÓi = 1, k.ÔÍ-12ÔÍ-12ÌÃÒÓ50Мы рассмотрим один алгоритм с асимметричным ключом, который можно использовать идля шифрования с открытым ключом, и для дешифрования с открытым ключом.Алгоритм базируется на паре простых чисел p и q. Полагаем n = pq. Выбираем число e,взаимно простое с m = (p − 1)(q − 1) и не превышающее m. Тогда в кольце вычетов Zm число eявляется обратимым. Полагаем d = e−1 , где обратный элемент вычисляется в Zm .

Пара чиселn и e составляет ключ шифрования, а пара чисел n и d — ключ дешифрования.Предположим, что сообщение представляет собой последовательность чисел S1 , S2 , . . . , Sk ,каждое из которых меньше n. ПолагаемSi = Cid mod n,ÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-1217. КОЛЬЦО МНОГОЧЛЕНОВÌÃÒÓ...............................................................................................9. Жорданова нормальная форма9.1.

Корневые подпространства . . .9.2. Жорданова нормальная форма9.3. Комплексные корни . . . . . . .9.4. Теорема Кэли — Гамильтона .........................................................................................121214192013. Операции над тензорами13.1. Понятие тензора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . .13.2. Матричная запись тензоров . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13.3. Преобразование тензоров, записанных в матричной форме . . . . . . . . . . . . . .2222232414. Множества и отношения14.1. Алгебра множеств . . . . .

. . . . .14.2. Отображения и соответствия . . .14.3. Отношения и операции . . . . . . .14.4. Элементы математической логики14.5. Мощность множеств . . . . . . . ......262630323435.....363636363640..........................16. Кольца и поля16.1. Кольца . . . . . . . . . . . . . . . . . .16.2. Специальные типы колец . . . . . .

. .16.3. Гомоморфизмы колец и факторизация16.4. Модули и алгебры . . . . . . . . . . . .16.5. Алгебры на полем . . . . . . . . . . . .......................................................................................................................................................................................................................................................................................................................................................19. Полукольца и булевы алгебры19.1.

Определение полукольца . . .19.2. Ряды в полукольцах . . . . . .19.3. Замкнутые полукольца . . . .19.4. Системы линейных уравнений19.5. Симметричные полукольца . .19.6. Решетки . . . . . . . . . . . ...................................................................................................................51515357586367...в...

. . . . . . .. . . . . . . .. . . . . . . .полукольцах. . . . . . . .. . . . . . . .69............ÔÍ-12.....434345494950ÌÃÒÓ17. Кольцо многочленов17.1. Определение кольца многочленов . . . . . . . . .17.2. Деление с остатком и его свойства . . . .

. . . .17.3. Разложение на неприводимые множители . . . .17.4. Использование делимости в теории шифрования17.5. Кватернионы . . . . . . . . . . . . . . . . . . . . .ÌÃÒÓÔÍ-12ÌÃÒÓ.....ÔÍ-12ÔÍ-12.....ÌÃÒÓÌÃÒÓ.....1134610ÔÍ-124. Псевдорешения и псевдообратная матрица4.1. Метод наименьших квадратов . . . . . . . .4.2. Псевдорешения . .

. . . . . . . . . . . . . . .4.3. Скелетное разложение . . . . . . . . . . . .4.4. Псевдообратная матрица . . . . . . . . . . .4.5. Проектирование на подпространство . . . .ÌÃÒÓÔÍ-12ОГЛАВЛЕНИЕÔÍ-12ÌÃÒÓÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓ.