$ф$ определяется как функция от группы эллиптических кривых к конечному полю, используемому для определения кривой, что дает координату X рассматриваемой точки. Для целей этого определения я предполагаю нейтральность группового закона (иначе говоря, точку в бесконечности, и отмеченную $\infty$) имеет координаты $(г,г)$, с $z$ фиксированный элемент поля такой, что для $х=г$ уравнение кривой не имеет решения $у$ (для всех стандартные кривые над простым полем $\mathbb F_p$, и AFAIK все остальные, мы можем взять $г=0$, куда $0$ поле нейтрально).
Набор $S$ это образ всей группы $\лангле Г\рангл$ к $ф$, таким образом, подмножество поля, включающее $z$.
$ф$ почти точно равномерна на $S$: набор $S$ имеет $(n-1)/2$ элементы, где $n$ является (простым) порядком $\лангле Г\рангл$, и каждый элемент $S$ кроме $z$ имеет ровно два предшественника $ф$, имеющие одну и ту же координату X. $z$ имеет единственный антецедент, и это $\infty$.
С криптографической точки зрения (таким образом, с $n$ достаточно большой, чтобы $\кв.п$ не является перечислимым), вероятность того, что счетное число независимых и равномерно случайных элементов $W_i$ из $\лангле Г\рангл$ включать $\infty$, столкнуться или столкнуться $f(W_i)$ является незначительным, и $f(W_i)$ являются (неотличимыми от) независимыми и равномерно случайными элементами $S$.
Аргумент: для данного $х$ в поле уравнение кривой становится фиксированным уравнением второй степени, которое в конечном поле имеет ноль, одно или два различных решения. Когда $х\в S$, случай нулевых решений имеет место только для $х=г$, по определению $ф$ и $S$. Случай одного решения не имеет места для стандартных кривых над простым полем (я не знаю исключения для других¹, а если бы оно и было, оно все равно было бы исключительным). Это оставляет два решения в качестве единственного (или, по крайней мере, наиболее распространенного) случая для $x\nz$.
¹ Это верно для кривых с уравнением $y^2=x^3+ax+b$, что имеет место для ECDSA с использованием простого поля. Доказательство, которое справедливо для любой кривой ECDSA, или опровержение приветствуются.
