2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Схема Шнорра
Сообщение13.01.2013, 08:50 
Добрый день.
Для реализации эцп по схеме Шнорра необходимо выбрать числа:
$p$ – простое число, $q$ – простое число, такое что $q|(p-1) $
$a$ - элемент, такой что $a^q = 1 \mod p$
Подскажите, пожалуйста, алгоритм решения этого сравнения или литературу, в которой можно его найти.
В той литературе, которая у меня на руках, рассматриваются лишь существование решения для общего случая, либо только количество корней такого частного, а как решать - не понятно.

 
 
 
 Re: Схема Шнорра
Сообщение13.01.2013, 09:05 
Так, т.е. $p,q$ Вы уже выбрали и Вам надо найти все $a$?
В таком случае, находите образующую по модулю $p$ (для этого на практике достаточно проверить порядка $O(\ln ^2p)$ первых простых чисел на то, являются ли они первообразными по модулю $p$ (по критерию Лемера - просто по определению)). Пусть $g$ - первообразная. Тогда $a:a\equiv g^{k\frac{p-1}{q}}\pmod p, k=1,...,p$ - все искомые решения.

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group