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

DIM>..., все шаги вроде ясны но не ясен самый главный 10 шаг, там сказано
DIM>"10. Select arbitrary a,b ∈ Fp, not both 0, such that r ·b2 ≡ a3 (mod p)."
DIM>Не как не возьму в толк как же на основе вычисленного r получить a и b?

Да уж... Не знаю, какой простой способ тут подразумевался авторами.

Можно, конечно, действовать совершенно прямолинейно. Выбираем случайно a до тех пор, пока ar не окажется квадратичным вычетом по модулю p (что проверяется вычислением символа Лежандра). Затем вычисляем b, умножив a в кубе на число, обратное r (которое получается с помощью расширенного алгоритма Евклида, как описано ранее в этой книге, или просто возведением в степень p-2, хотя это и чуть медленнее; все эти операции, естественно, по модулю p) и вычислив квадратный корень по модулю p из результата (что делается алгоритмом Шенкса-Тонелли). Случай всяких там нулей рассмотреть отдельно.

В случае, если число p-1 не делится на 3, всё становится проще, поскольку в этом случае легко вычисляются кубические корни по модулю p, и это позволяет действовать наоборот — т.е. выбирать случайно b и вычислять a.

Что касается "какого-нибудь ещё способа" — вряд ли, если требование выбора из ВСЕХ изоморфизм-классов по модулю p существенно.