Имеет ли ((a ^ x) ^ 1 / x) == a в Zp? (для протокола Jablon) - PullRequest
Новая
       40

Имеет ли ((a ^ x) ^ 1 / x) == a в Zp? (для протокола Jablon)

0 голосов
/ 03 декабря 2011

Мне нужно реализовать протокол Jablon ( paper ), но я два часа сижу на баге.

Я не очень хорошо разбираюсь в математике, поэтому не знаю, виновата ли она в том, что я написал это, или это просто невозможно. Если это невозможно, я не вижу, как протокол Jablon может быть реализован, поскольку он опирается на тот факт, что ((gP ^ x) ^ yi) ^ (1 / x) == gP ^ yi.

Возьмите следующий код. Это не работает. 

    BigInteger p = new BigInteger("101");
    BigInteger a = new BigInteger("83");
    BigInteger x = new BigInteger("13");
    BigInteger ax = a.modPow(x, p);
    BigInteger xinv = x.modInverse(p);
    BigInteger axxinv = ax.modPow(xinv, p);

    if (a.equals(axxinv))
        System.out.println("Yay!");
    else
        System.out.println("How is this possible?");

1 Ответ

10 голосов
/ 03 декабря 2011

Ваша проблема в том, что вы неправильно вычисляете k (1 / x) . Нам нужно, чтобы k (1 / x)) k было х. Маленькая теорема Ферма говорит нам, что k p-1 равно 1 модулю p. Поэтому мы хотим найти y такой, что x * y равен 1 mod p-1, а не mod p.

Итак, вы хотите BigInteger xinv = x.modInverse(p-1);.

Это не будет работать, если x имеет общий множитель с p-1. (Ваш случай избегает этого.) Для этого вам нужна дополнительная теория.

Если p простое число, то r является первообразным корнем, если ни одно из r, r ^ 2, r ^ 3, ..., r ^ (p-2) не конгруэнтно 1 mod p. Не существует простого алгоритма для создания примитивного корня, но они распространены, поэтому обычно вам нужно проверить только несколько из них. (Для p = 101 первое число, которое я попробовал, 2, оказалось примитивным корнем. 83 также.) Тестирование их может показаться трудным, но это не так уж и плохо, поскольку оказывается, что (опуская куча теории тут) только делители р-1 нужно проверять. Например, для 101 вам нужно только проверить полномочия 1, 2, 4, 5, 10, 20, 25 и 50.

Теперь, если r - примитивный корень, то каждое число mod p - это некоторая степень r. Какая сила? Это называется проблемой дискретного логарифма и не является простой. (Это сложность - основа RSA, хорошо известной криптографической системы.) Вы можете сделать это с пробным разделением. Поэтому, пытаясь 1, 2, 3, ... вы в конечном итоге обнаружите, что, например, 83 равно 2 ^ 89 (мод 101).

Но как только мы узнаем, что каждое число от 1 до 100 равно 2 в некоторой степени, мы получаем способ вычисления корней. Потому что возведение числа в степень х просто умножает показатель степени на х. И 2 ^ 100 равно 1. Таким образом, возведение в степень умножается на х (мод 100).

Итак, предположим, что мы хотим, чтобы y ^ 13 было 83. Тогда y равно 2 ^ k для некоторого k, такого что k * 13 равно 89. Если вы поиграете с Китайской теоремой об остатках , вы можете понять, что к = 53 работает. Следовательно, 2 ^ 53 (mod 101) = 93 - это 13-й корень из 89.

Это сложнее, чем мы делали раньше. Но предположим, что мы хотели взять, скажем, 5-й корень из 44 мода 101. Мы не можем использовать простую процедуру, потому что у 5 нет мультипликативного обратного мода 100. Однако 44 равно 2 ^ 15. Поэтому 2 ^ 3 = 8 является 5-м корнем. Но есть еще 4, а именно 2 ^ 23, 2 ^ 43, 2 ^ 63 и 2 ^ 83.

...