Дана эллиптическая кривая над полем Z7 : E : y^2 = x^3 + 3x + 2 Требуется определить все точки над из E над полем Z7. Во-первых, что такое E? Не более, чем имя-собственное кривой? Обычно при решении задачи нахождения всех точек на кривой используется примитивный элемент, который способен генерировать все точки. Например, будет у нас другая кривая : y^2 = x^3 + x + 6. И есть примитивный элемент а = (2, 7). Дальше мы находим 2а и 3a и так далее до тех пор, пока некий an не окажется равен а. И тогда, если мы соберём вместе все полученные ненулевые элементы вместе с нулём, то получим мы циклическую группу. И вроде как все точки найдём. Однако мне решительно непонятно, как можно определить все точки над кривой имея только саму кривую и поле над которым она) Самому создать примитивный элемент и действовать как в описанном мною случае? Создать самому притивный элемент можно или методом перебора (смотреть кто замкнёт группу) или есть специальные программы, выдающие примтивный элемент, но это всё сложно и здесь решается всё гораздо проще. Если где-то чушь порю и обнажаю полное незнание криптографии эллиптических кривых, так, собственно, не скрываю этого - знал бы криптографию, не сидел бы на форуме...
RUB Да. Ты случайно не путаешь примитивный элемент мультипликативной группы поля F, над которым кривая, и примитивный элемент группы E(F), образованной точками на кривой? E(F) в общем виде вовсе не обязана иметь примитивный элемент. Вроде бы только перебором, т.е. перебирать все х из F и смотреть будет ли y^2 квадратом. Во всяком случае я еще ничего лучшего(в алгоритмическом смысле) не встречал, если кто знает, поделитесь пожалуйста. Встречный вопрос: каков практический смысл нахождения всех точек кривой? Или просто для интереса? P.S. Endlich ein "Landsmann" )
В этом случае достаточно перебрать все пары (x,y) для x,y из Z7 и подставить их в уравнение кривой. Те, что удовлетворяют равенству, и будут искомыми.
Relf - да, именно так. Спасибо. Stiver - смысла в нахождении всех точек кривой действительно нет. В общем виде иметь примитивный элемент действительно не обязана. А ещё я всё-таки познал философский смысл роли поля, оно нам mod p задаёт, т.е. p - оно и есть поле, вроде как если у нас Z7 было, то и теперь будет mod 7. Stiver : Jawohl, Kamerad))
