ВУЗ:
Составители:
Механизм кодирования и декодирования по алгоритму RSA
RSA – аббревиатура от сокращения фамилий 3-х ученых, разработавших
эту систему – Рональда Райвеста, Ади Шамира и Леонарда Адельмана.
Алгоритм был предложен в 1977 году. Он основывается на том, что нахождение
больших простых чисел осуществляется сравнительно легко, но разложение на
множители произведения двух таких чисел требует значительных
вычислительных затрат.
Простым числом называется число из натурального ряда, большее 1,
которое делится без остатка только на 1 и само на себя.
Аксиома
. Число простых чисел бесконечно.
Число x называется простым относительно y, если его нельзя разложить
на сомножители, на которые число y не делится без остатка. Например число 4
является простым относительно 15, а число 6 не является простым
относительно числа 15.
Числа x и y называются взаимно простыми, если наименьший общий
делитель НОД (x,y) = 1.
Малая теорема Ферма
. Если P – простое число, то
()
px
p
mod1
1
=
−
для
любого х, простого относительно P.
Следовательно:
()
px
p
mod1
1
=
−
,
()
pxx
p
mod1
1
=⋅
−
,
()
xp
x
x
p
×=
mod1
.
()
pxx
p
mod
=
Функцией Эйлера (n) называется число положительных целых меньших n
и простых относительно n, на которые n не делится без остатка.
N 2 3 4 5 6 7 8 9 10 11 12
(n) 1 2 2 4 2 6 4 6 4 10 4
1 1 1 1 1 1 1 1 1 1 1
2 3 2 5 2 3 2 3 2 5
3 3 5 4 7 3 7
4 4 7 5 9 4 11
5 7 5
6 8 6
7
8
9
C
П
И
С
О
К
10
Страницы
- « первая
- ‹ предыдущая
- …
- 71
- 72
- 73
- 74
- 75
- …
- следующая ›
- последняя »
