Вопрос 2

идея алгоритма состоит в том, чтобы возвести a в произвольную степень, применяя элементарные операции возведения в квадрат и умножения. В качестве фазового пространства X этой задачи рассмотрим множество троек X = {(b,k,p)}. Здесь b выступает в роли текущего основания степени, k - в роли текущего показателя степени, p - это уже вычисленная часть степени. Ключевым моментом всегда является формулировка инварианта цикла: I(b,k,p): bk*p = an = const, т.е. величина bk*p постоянна и равна an. Легко подобрать начальные значения так, чтобы инвариант выполнялся: b0 = a; k0 = n; p0 = 1. I(b0,k0,p0) = I(a,n,1): an*1 = an Условие завершения совместно с выполнением инварианта должно обеспечить легкое решение требуемой задачи, т.е. вычисление an. Действительно, если k = 0, то из инварианта следует, что b0*p = p = an, т.е. искомая величина содержится в переменной p. Итак, условие завершения состоит в равенстве нулю числа k: Q(b,k,p): k = 0 Осталось написать преобразование T точки x = (b,k,p), которое сохраняет инвариант и одновременно уменьшает k. Определим преобразование T следующим образом: T(b,k,p) = (b*b, k/2, p), если k четное T(b,k,p) = (b, k-1, p*b), если k нечетное Легко видеть, что инвариант сохраняется и k монотонно убывает. Итак, выпишем алгоритм быстрого возведения в степень для случая вещественного основания: вещ алг. быстрое возведение в степень(вх: вещ a, цел n)

Вопрос 3

Определение группы

Пусть задано множество элементов G g₁, g₂, ... , g_n , обладающих следующими свойствами:

Определен закон умножения элементов g_i g_j = g_k, причем если g_i, g_j G, то g_i g_j = g_k G, i, j, l = 1, 2, ..., n.
Выполняется закон ассоциативности g_i (g_j g_k) = (g_i g_j) g_k.
Существует единичный элемент e, eg_i = g_i, i = 1, 2, ... , n.
Существует обратный элемент g _i^-1, g _i^-1g_i = e, i = 1, 2, ... , n.

Тогда на множестве G задана группа элементов g₁, g₂, ... , g_n

Вопрос 4 rsa алгоритм

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

Пример. Пусть группа — мультипликативная группа вычетов по модулю , где и — различные простые числа, которые держатся в секрете. Порядок группы равен . В настоящее время считается, что задача разложения целого числа на простые множители настолько сложна, что это обеспечивает достаточную стойкость системы шифрования. Замечание 1. Свойство быть квадратичным вычетом сохраняется при зашифровке. Замечание 2. Неизвестно, является ли задача расшифровки в RSA алгоритме задачей, эквивалентной задаче факторизации целых чисел.

Замечание 3. Сравнение верно для любого класса вычетов по модулю , а не только для вычетов взаимно простых с . Действительно, пусть . Тогда . Число кратно и значит , следовательно, и так как и — различные простые числа, то . Аналогично . Из мультипликативности классов вычетов следует, что сравнение верно для любого , так как любой необратимый элемент группы кратен или [ 5 ].