Задано: n N. Для криптографических приложений нас интересует задача вычисления значения в случае, когда

Найти: .

Для криптографических приложений нас интересует задача вычисления значения в случае, когда . Легко видеть, что = (р -1) (q -1). Таким образом, если р и q известны, то задача решается просто. С другой стороны, если известны n и , то решая уравнение , получаем p и q. Значит, задача полиномиально сводится к суженной задаче факторизации. Справедливо и обратное сведение. Таким образом, эти две задачи полиномиально эквивалентны.

2. Задачи распознавания и построения первообразных корней по модулю р.

Первая из задач формулируется так.

Задано: р – простое нечетное, N.

Распознать: порождает ли g группу Z ?

Для этой задачи неизвестны ни детерминированные, ни вероятностные полиномиальные алгоритмы. Но если задано каноническое разложение числа р – 1, то задача решается простой проверкой условий:

для любого простого .

Таким образом, видно, что указанная задача полиномиально сводится к задаче факторизации числа р – 1 (возведение в степень осуществляется бинарным методом)

Вторая задача формулируется следующим образом.

Задано: простое нечетное р.

Найти: N такое,что g порождает группу Z .

И для этой задачи неизвестны эффективные алгоритмы. Можно лишь указать очевидное вероятностное сведение второй задачи к первой. Учитывая, что существует первообразных корней по модулю р, вероятность неудачи равна . Это сведение можно использовать для такой ослабленной задачи нахождения первообразного корня:

Задано: простое нечетное р, .

Найти: N такое,что g порождает группу Z .

Сформулируем еще один вариант решения задачи построения первообразного корня по простому модулю.

Дата добавления: 2014-11-16