Поясните плиз чайнику на пальцах (именно на пальцах, т.к. литературы разумеется полно и гуглится всего полно) как вычислить дискретный логарифм скажем для p=13, p-1=2*2*3. За генератор можно взять 2 или может 7 - в принципе для любого должно работать? Короче решить 2^x=b mod 13. Можно составить две таблички соответственно по числу простых делителей в их степенях, т.е. 0..3 и 0..2 и туда подсматривать... Чиста конкретна
В общем, зря я струхнул сразу... После пятого прочтения стало понятно. Наиболее просто и бездоказательно алгоритм изложен в Вики, хороший готовый рецепт... Однако изложение крайне неряшливое, неправильно задан диапазон изменения индексов и местами перепутаны индексы i и j. Так что если кому будет нужна распальцовка на конкретном примере могу запостить в будушем =)))
Там еще такой жуткий баг: вместо -x0 -x1 -x2... следует читать -x0 -x1*q -x2*q^2... Короче, мне удалось написать рабочий код =)))
Лан, предвижу возражения, поэтому укажу на ошибки (на мой взгляд). Нужно: Шаг 1: Составление таблицы j принадлежит 0...q_i-1 Шаг 2: Рассматриваем сравнение (ba^(-x_0-...-x_(j-1)*q_i^(j-1))^ ... = a^(x_j ... Конец цикла по j Конец цикла по i Примерно так =)))
Прикольный я метод извлечения квадратных корней придумал.. Нужно найти дискретный логарифм и разделить его на два, а если логарифм нечетный и не делится на два, значит число суть квадратичный невычет. Так все просто
