Методы факторизации натуральных чисел. Ишмухаметов Ш.Т. - 12 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

Глава 1. Простые числа 13
Не любая группа имеет генератор. Группа, в которой есть генератор,
порождается одним элементом и называется циклической.
Большинство операций в кольце вычетов Z
n
можно выполнять,
выполнив сначала действия с числами, а затем находя остаток от деления
результата на модуль n. Однако с операциями возведения в степень и
вычисления дискретного (модулярного) логарифма, такой порядок является
очень неэффективным. Например, если мы захотим вычислять 2
199
(mod
1003), используя калькулятор, входящий в состав операционной системы
Windows, то результат окажется неверным. В то же время эту же операции
несложно выполнить с помощью алгоритма быстрого возведения в степень
по модулю заданного натурального числа, который мы сейчас опишем.
1.2. Алгоритм быстрого возведения в степень по модулю
Предположим, что требуется вычислить z = a
b
mod n. Рассмотрим
следующий алгоритм:
1. Представим b в двоичный системе исчисления: b = (b
0
b
1
... b
k
)
2
,
b
i
∈ {0, 1}. Например, 199 = 11000111
2
,
2. Заполним следующую таблицу
b b
0
b
1
... b
k
a a
0
a
1
... a
k
где a
0
= a, a
i+1
=
(
a
2
i
mod n, если b
i+1
= 0,
a
2
i
· a mod n, если b
i+1
= 1
для i ≥ 0.
Результат появится в последней ячейке второй строки.
Пример. Вычислить 2
199
mod 1003:
b 1 1 0 0 0 1 1 1
c 2 8 64 84 35 444 93 247
Ответ: 2
199
mod 1003 = 247.
Глава 1. Простые числа                                                  13

Не любая группа имеет генератор. Группа, в которой есть генератор,
порождается одним элементом и называется циклической.
            Большинство операций в кольце вычетов Z n можно выполнять,
выполнив сначала действия с числами, а затем находя остаток от деления
результата на модуль n. Однако с операциями возведения в степень и
вычисления дискретного (модулярного) логарифма, такой порядок является
очень неэффективным. Например, если мы захотим вычислять 2199 (mod
1003), используя калькулятор, входящий в состав операционной системы
Windows, то результат окажется неверным. В то же время эту же операции
несложно выполнить с помощью алгоритма быстрого возведения в степень
по модулю заданного натурального числа, который мы сейчас опишем.


1.2. Алгоритм быстрого возведения в степень по модулю
     Предположим, что требуется вычислить z = ab mod n. Рассмотрим
следующий алгоритм:

      1. Представим b в двоичный системе исчисления: b = (b0 b1 ... bk )2 ,
bi ∈ {0, 1}. Например, 199 = 110001112 ,
      2. Заполним следующую таблицу

       b     b0 b1    ...    bk
        a    a0 a1    ...    ak

                      (
                          a2i mod n, если bi+1 = 0,
где a0 = a, ai+1 =                                       для i ≥ 0.
                          a2i · a mod n, если bi+1 = 1

      Результат появится в последней ячейке второй строки.

Пример. Вычислить 2199 mod 1003:
       b      1   1   0      0    0   1    1   1
        c     2   8 64 84 35 444 93 247

Ответ: 2199 mod 1003 = 247.

Страницы