@WhiscasH

Дано сравнение x^p0 = 1 (mod p), где p0 и p - константы, большие простые числа.
Необходимо найти хотя бы одно решение (кроме единицы), при p0 размером 160 бит и p размером 1024 бит.

Пытался подбирать случайные значения x - слишком долго.

Есть какая-нибудь формула, которая поможет быстро найти хотя бы одно решение?

Добавлено через 6 минут
Если кому интересно или если будет полезно, я пытаюсь реализовать схему Шнорра, в которой используется составной открытый ключ (p, q, g, y). |p| = 1024, |q| = 160. Нужно подобрать такое g != 1, что g^q = 1 (mod p).

Добавлено через 11 часов 20 минут
Нашел ответ.
Нужно выбрать случайное h из (1; p - 1). Тогда с достаточно большой вероятностью g = h^(p-1)/q mod p будет подходить под условие g^q = 1 (mod p).

0

@kabenyuk

Уважаемый WhiscasH, вообще-то в этой схеме p0 - делитель числа p-1. Потому в качестве х можно выбрать например 2^{(p-1)/p0}.

1