Технологии цифровых подписей.

Алгоритмы возведения в степень

Алгоритмы быстрого возведения в степень (дихотомический алгоритм возведения в степень, бинарный алгоритм возведения в степень) — алгоритмы, предназначенные для возведения числа x в натуральную степень n за меньшее число умножений, чем это требуется в определении степени^[1]. Алгоритмы основаны на том, что для возведения числа x в степень n не обязательно перемножать число x на само себя n раз, а можно перемножать уже вычисленные степени. Так, например, если {\displaystyle n=2^{k}} степень двойки, то для возведения в степень n достаточно число возвести в квадрат {\displaystyle k} раз, затратив при этом k умножений вместо {\displaystyle 2^{k}} . Кроме того, некоторые алгоритмы для дальнейшей оптимизации используют тот факт, что операция возведения в квадрат быстрее операции умножения за счёт того, что при возведении в квадрат цифры в сомножителе повторяются^[2].

Бинарный алгоритм возведения в степень был впервые предложен в XV веке персидским математиком Аль-Каши^[3].

Данные алгоритмы не всегда оптимальны. Например, при использовании схемы «слева-направо» быстрое возведение в степень n = 15 потребует выполнения трёх операций умножения и трёх операций возведения в квадрат, хотя возведение в 15-ю степень можно выполнить и за 3 умножения и 2 возведения в квадрат^[4].

Нахождение простых чисел.

Простые числа – это натуральные числа, большие единицы, которые имеют только два делителя: единицу и само это число.

Примеры простых чисел: 2, 3, 5, 7, 11, 13…

(Единица не является простым числом!)

Существует множество задач, связанных с простыми числами, и хотя формулируются они достаточно просто, решить их бывает очень трудно. Некоторые свойства простых чисел еще не открыты. Это побудило немецкого математика Германа Вейля (Wayl, 1885-1955) так охарактеризовать простые числа: «Простые числа – это такие существа, которые всегда склонны прятаться от исследователя».

Во все времена люди хотели найти как можно большее простое число. Пока люди считали только при помощи карандаша и бумаги, им нечасто удавалось обнаружить новые простые числа. До 1952 г. самое большое известное простое число состояло из 39 цифр. Теперь поиском все больших простых чисел занимаются компьютеры. Это может представлять интерес для любителей рекордов.

Не будем гнаться за рекордами, а рассмотрим несколько алгоритмов нахождения простых чисел.

Технологии цифровых подписей.

ЭЦП – раздел криптографии ЭЦП позволяет осуществить

· аутентификацию автора (создателя) информации

· доказательство (проверку) того факта, что подписанное сообщение или данные не были модифицированы при передаче информации в компьютерных сетях.

· невозможность отказа от авторства.

 

Электронная подпись предназначена для идентификации лица, подписавшего электронный документ, и является полноценной заменой (аналогом) собственноручной подписи в случаях, предусмотренных законом

Электронная цифровая подпись

· Битовая строка, присоединяемая к документу после подписания, называется электронной цифровой подписью.

· Протокол, с помощью которого получатель убеждается в подлинности отправителя и целостности сообщения, называется проверкой подлинности (аутентификацией).