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

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

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


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

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

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

A>и проверил бы

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

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

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

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


Спасибо, я думал про это, но не увидел тут перспективы существенного ускорения, поэтому не попробовал. Ну и, к сожалению, для первокурсника, которому не читали теорию чисел, этот вариант не катит точно...