Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Algo » •Дискретное логарифмирование по модулю M алгоритмом baby-step-giant-st
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
po4emu tolko dlya vzaimno prostih a i m
a^(n*p-q) mod m = b mod m
( a^(n*p)*a^(-q) ) mod m = b mod m
(a^(n*p) * a ^ (-q) * a^q) mod m = (b * a^q) mod m
razve ne dlya vseh a i m?
a^(-q) это обратный элемнт к a^q, но если gcd(a,m)!=1 тогда и gcd(a^q,m)!=1 и у числа a^q нету обратного элемента в этом поле.
Да, по некоторым данным, есть возможность применять этот метод и для не взаимно простых a и m. Однако я не представляю, как это можно сделать 
А проблема даже не в обратном (он в самом алгоритме явно и не используется), а в том, что при выводе окончательной формулы мы умножали обе части на a в какой-то степени, а при этом неравенство могло превратиться в равенство.
А, ну может быть, тогда этот алгоритм можно применять и для не взаимно простых a и m, но потом перед выводом проверять каждый найденный корень непосредственным возведением в степень?..
есть возможность применять этот метод и для не взаимно ????
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Algo » •Дискретное логарифмирование по модулю M алгоритмом baby-step-giant-st