Здравствуйте, kfmn, Вы писали:

K>...В общем, буду благодарен за любые подсказки.


Есть еще одна идея. Перед началом вычислений

Я бы разложил p-1 на простые множители:

p-1 = p1^a1 * p2^a2 * pk^ak;

и проверил бы

a^((p-1)/pj) mod p

на равенство 1.

Если ни одно из равенств не выполняется, то a — генерирующий элемент группы (Z/pZ)* и в ответе будут первые 100 чисел интервала (или весь интервал, что короче)

Здравствуйте, kfmn, Вы писали:

K>...В общем, буду благодарен за любые подсказки.


Есть еще одна идея. Перед началом вычислений

Я бы разложил p-1 на простые множители:

p-1 = p1^a1 * p2^a2 * pk^ak;

и проверил бы

a^((p-1)/pj) mod p

на равенство 1.

Если ни одно из равенств не выполняется, то a — генерирующий элемент группы (Z/pZ)* и в ответе будут первые 100 чисел интервала (или весь интервал, что короче)

PS Это позволит иметь дело с подгруппой размера по крайней мере в 2 раза меньше, чем p-1.