Как найти значение переменной в выражении MOD?

Question

9 = 2^X мод 11

Что такое X и как найти X?

Это связано с поиском простого текста в алгоритме RSA, и я пишу для него программу на C.

Answer 1

Ответ: 6 + 10i для любого целого числа i.

Простой способ получить решения для малых модулей — перебрать все значения x.Вам нужно всего лишь проверить от 0 до 10 (= 11 - 1), чтобы найти первое решение, если оно существует.

x = 0
while x < 50:
    if 9 == 2**x % 11:
         print x
    x += 1

Выход:

6
16
26
36
46

Очевидно, что это займет много времени, если модуль большой.

Более подробная информация находится на Дискретный логарифм страница.Примечание:

Нет эффективного классического алгоритма для вычисления общего дискретного логарифма logbg не известно.Наивный алгоритм состоит в том, чтобы поднять B до более высоких и более высоких способностей K до тех пор, пока не будет найдено желаемое G;Это иногда называют умножением испытаний.Этот алгоритм требует линейного времени работы по размеру группы G и, следовательно, экспоненциально по количеству цифр в размере группы.

Если бы можно было легко инвертировать модульное возведение в степень, это не был бы хороший криптографический примитив.

Answer 2

Очевидно, что последовательность 2 ^ n mod 11 будет циклической.

2 ^ 0 mod 11 = 1
2 ^ 1 мод 11 = 2
2 ^ 2 мод 11 = 4
2 ^ 3 мод 11 = 8
2 ^ 4 mod 11 = 5
2 ^ 5 мод 11 = 10
2 ^ 6 мод 11 = 9
2 ^ 7 мод 11 = 7
2 ^ 8 мод 11 = 3
2 ^ 9 мод 11 = 6
2 ^ 10 мод 11 = 1
2 ^ 11 мод 11 = 2

Итак, длина цикла равна 10.

2 ^ n mod 11 = 9 для n = 6 + 10 * m, где m - целое число

Answer 3

Я думаю, что это можно решить с помощью модульной арифметики . Другой способ - вычисление 9 = 2 ^ X в F ₁₁ (Z / 11Z), но это тоже часть модульной арифметики.

Другое решение (где вы найдете только ОДНО решение) заключается в численном решении уравнения, что, вероятно, проще в программе на Си.