Представление чисел суммой двух квадратов и эллиптические кривые

[Lau]

нечётное простое число
А бывает ли простое и одновременно чётное число?

[grechnik]

Да, есть ровно одно такое число: 2.

[rozhik]

0 четное или нет?

[hatred1993]

Четное

[rozhik]

пост немного с подколкой. wiki имеет хорошую статью по этому поводу.
Но субьективно нечётное простое число действительно звучит странно.

[denbrubeck]

Да, но счет простых чисел начинается с 2, исходя из определения.

[Lau]

Отлично, юмор на хабре всегда ценили :-)
Но по теме статьи Ваш ответ вряд ли можно засчитать

[grechnik]

В статье встречаются выражения (p-1)/2 и (p+1)/2 в качестве целых чисел. Чтобы это было правдой, нужно, чтобы p было нечётным.
Можно воспринимать словосочетание «нечётное простое число» как «простое число, не равное 2», это эквивалентно. Для статьи важно, чтобы p не было равно 2.

[halyavin]

Если x₂/x₁ — квадратичный невычет, то аналогично эллиптическим кривым число решений равно 2p минус число решений в случае квадратичного вычета, то есть 2p-(p-1)=p+1.

Что-то у меня не получается это вывести аналогичным образом. При домножении x₂ на g, величина x₂(x₁²-x₂²) не домножается на g³ как хотелось бы.

[halyavin]

Чтобы получилось «аналогично» нужно обобщить начальное утверждение: cy₁²=y₂²+u имеет p-1 решение если c — квадратичный вычет, а u отлично от нуля. Уже из этого утверждения будет следовать, что gcy₁²=y₂²+u имеет p+1 решение при тех же ограничениях. После чего нужно заметить, что x₂(x₁²-x₂²) не может равняться нулю в рассматриваемом случае.

[grechnik]

Да, именно так.

[halyavin]

Верно ли, что именно так генерируют кривые для целей криптографии?

[grechnik]

Да. Вариант со случайным перебором до посинения, впрочем, тоже используется.
Например, российский ГОСТ 34.10-2012 на цифровую подпись не содержит требований к генерации кривых, но приводит два примера для тестов. В первом d=915. Во втором, видимо, случайный перебор.

[halyavin]

А перебирают что, кривые? Или речь о каком-то переборе для нахождения числа точек на кривой?

[grechnik]

Да, кривые. Выбирают случайную кривую, считают число точек на ней, если не подошло по каким-то причинам — начинают сначала.

[grechnik]

В криптографии, где нужна одна кривая, можно и подождать. Скорость генерации критична, когда кривых с известным числом точек нужно много, например, в алгоритмах проверки/доказательства простоты с использованием эллиптических кривых.

[zuborg]

У Вас отличный слог, легко и приятно читать )
Продолжайте в том же духе, пожалуйста.