Точка эллиптической кривой

[Stasya7]

Пусть задано уравнение эллиптической кривой над конечным полем и её параметры. Нужно найти (какую-нибудь) точку (не особую) этой кривой. Я правильно понимаю, что поиск только прямым перебором? Или можно как-нибудь оптимизировать?

[Sonic86]

Stasya7 в сообщении #1166049 писал(а):

Пусть задано уравнение эллиптической кривой над конечным полем и её параметры. Нужно найти (какую-нибудь) точку (не особую) этой кривой. Я правильно понимаю, что поиск только прямым перебором? Или можно как-нибудь оптимизировать?

Могу только сказать, что если кривая имеет вид $y^2=P_3(x)$, то фиксируя $x$ мы получим квадратное уравнение в поле $\mathbb{F}_q$. И я что-то даже для простого поля не могу придумать, как это уравнение быстро решать. Можно довольно быстро найти образующую, а вот дискретное логарифмирование - $NP$-задача, пусть не перебором, но пишут, что довольно страшное:
https://ru.wikipedia.org/wiki/%D0%94%D0 ... 0%B8%D0%B5
Т.е. можно поперебирать иксы и попытаться поискать квадратные корни - авось и найдем.

[Xaositect]

Для квадратного корня есть алгоритм: https://en.wikipedia.org/wiki/Tonelli%E ... _algorithm