Здравствуйте!
Подскажите пожалуйста алгоритм выбора параметров a и b эллиптической кривой над полем F(p), я нашел pdf http://residentrf.ucoz.ru/_ld/0/33_HankersonMeneze.pdf там есть алгоритм
"Algorithm 4.17 Generating a random elliptic curve over a prime field Fp"
на странице 197 (аналогичный есть в X9.62-1998), все шаги вроде ясны но не ясен самый главный 10 шаг, там сказано
"10. Select arbitrary a,b ∈ Fp, not both 0, such that r ·b2 ≡ a3 (mod p)."
Не как не возьму в толк как же на основе вычисленного r получить a и b?
Или может есть какой-нибудь еще способ получения параметров эллиптической кривой?
Очень прошу помочь
Дмитрий.

Здравствуйте, 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 существенно.