Цитата приглашает вычислить $5\,П$ на эллиптической кривой уравнения $E:\Y^2\эквив X^3+3X+7\pmod{11}$ чтобы экспериментально прийти к выводу, что это точка в бесконечности $\mathcal O$ (нейтральное сложение точек), и получить интуицию, поэтому вычисление $5\,П$ на эллиптической кривой уравнения $ E: \ Y ^ 2 \ эквив X ^ 3 + 3X + 7 \ pmod {187} $ (как выполняется алгоритмом) дает значение, которое нельзя инвертировать по модулю $187$.
Все это исходит из Китайская теорема об остатках. Возможные утверждения и последствия этого: для $n=p\,q$ с $\gcd(p,q)=1$ (в том числе $n=187$ , $р=11$ , $q=17$ как в примере)
- Любое количество по модулю $n$ может быть эквивалентно вычислено по модулю $р$ и по модулю $q$.
- кольцо целых чисел по модулю $n$, отмеченный $\mathbb Z_n$, имеет канонический изоморфизм с $\mathbb Z_p\раз\mathbb Z_q$.
- Для любого целого числа $z$ в $[0,n)$ мы можем однозначно определить $z_p=z\bmod p$ и $z_q=z\bmod q$, и тогда выполняется $z=\left((q^{-1}\bmod p)\,(z_p-z_q)\bmod p\right)\,q+z_q$.
- Для данной эллиптической кривой уравнения, взятого по модулю $n$, и точки $U$ и $В$ на этой кривой, если мы сможем вычислить $U+V$ согласно уравнениям сложения точек эллиптической кривой в поле, что дает $(Х,Y)$ ; то мы можем эквивалентно сделать то же самое для кривых с тем же уравнением, взятым по модулю $р$ и по модулю $q$ получение координат $(X_p,Y_p)$ и $(X_q,Y_q)$ , то получите $(Х,Y)$ дважды применив метод, указанный выше.
- Вышеприведенное для сложения точек распространяется на умножение точек на целое число.
Какое понимание это дает нам?
Мы получаем понимание того, что, вычисляя эллиптическую кривую в кольце $\mathbb Z_n$ за $n$ (изначально) неизвестной факторизации, как если бы это было поле (это не так), нам также удалось вычислить эллиптическую кривую в кольце $\mathbb Z_p$ куда $р$ является (изначально) неизвестным фактором $n$. И (пока еще без формального доказательства, но с поучительным примером) причина вычисления на кривой в $\mathbb Z_n$ попасть в невычислимое обратное, состоит в том, что точка в бесконечности $\mathcal O$ была достигнута на кривой в одном из $\mathbb Z_p$ или же $\mathbb Z_q$ (при условии $р$ и $q$ являются основными, что делает $\mathbb Z_p$ и $\mathbb Z_p$ поля и $\mathcal O$ на соответствующей кривой четко определена).
Это позволит нам понять Почему алгоритм работает, что в свою очередь позволяет рассуждать о нем и оценивать его вероятность успеха (то есть выявления нетривиального фактора $n$). Когда $n$ является произведением различных простых чисел $p_i$, эта вероятность представляет собой сумму вероятностей достижения бесконечно удаленной точки для одной кривой для каждой из $p_j$, за вычетом (очень низкой) вероятности того, что он сработает одновременно на всех кривых.
