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

Question

9 = 2 ^ X мод 11

Что такое X и как вы находите X?

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

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

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

Более подробная информация находится на странице Discrete Logarithm . Примечание:

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

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

Answer 2

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

2 ^ 0 мод 11 = 1
2 ^ 1 мод 11 = 2
2 ^ 2 мод 11 = 4
2 ^ 3 мод 11 = 8
2 ^ 4 мод 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), но это тоже часть модульной арифметики.

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