Рейтинг:1

Значение поля фактора в ЭЦМ Ленстры

флаг et

Я просматриваю факторизацию эллиптических кривых Ленстры из книги Сильвермана «Математическая криптография».

Я понял сам алгоритм, но не смог понять конкретный момент, сделанный в книге.

Мы пытаемся разложить 187.

Мы используем $E: Y^2 = X^3 + 3X + 7 \bmod 187$ с $P = (38, 112)$

Когда мы пытаемся вычислить $5P$, мы должны вычислить обратное число 11 в 187, что мы не можем сделать, поскольку 11 не взаимно просто с 187, и, следовательно, мы можем найти 11 как множитель 187.

До этого ясно. Однако после этого в книгах говорится

Рассмотрим более подробно, почему мы не смогли вычислить $5P$ по модулю 187. Если вместо этого мы посмотрим на эллиптическую кривую $Е$ по модулю 11, то быстрое вычисление показывает, что точка $P = (38,112) \экв (5,2) \pmod{11}$ удовлетворяет $5P = \mathcal O$ в $E(\mathbb F_{11})$. Это означает, что когда мы пытаемся вычислить $5P$ по модулю 11, мы получаем точку $\mathcal O$ на бесконечности, поэтому на каком-то этапе расчета мы пытались разделить на ноль. Но здесь «ноль» означает ноль в $F_{11}$, так что на самом деле мы пытаемся найти обратную по модулю 11 часть некоторого целого числа, которое делится на 11.

Мы уже разложили на множители 187 и обнаружили, что 11 является одним из множителей. Так в чем смысл вычислений $5P$ в $\mathbb F_{11}$. Какое понимание это дает нам?

fgrieu avatar
флаг ng
Я читал, что «Мы изучаем более внимательно» и «быстрое вычисление» не предназначены для шагов в алгоритме. Это шаги в объяснении алгоритма.
флаг et
@fgrieu - да, я понимаю, что это не шаг в алгоритме. Но я не могу понять, что именно это объясняет - вот в чем вопрос
Рейтинг:3
флаг ng

Цитата приглашает вычислить $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$, за вычетом (очень низкой) вероятности того, что он сработает одновременно на всех кривых.

флаг et
Как можно сделать вывод, что причина, по которой НОД не вернул 1, заключается в том, что $5P \bmod 11 = \mathcal O $?
флаг et
Для вашей точки _"Для любого целого числа $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$"_ - Где я могу прочитать больше об этом - есть ли какое-либо название для этого отношения - что мне искать?
fgrieu avatar
флаг ng
@ user93353: это формула, используемая в RSA с CRT. Он сжимает последнюю формулу в 1 и последние две в 2 [здесь] (https://www.di-mgt.com.au/crt_rsa.html#rsacalculations) с $z$, $z_p$, $z_q$ ( теперь в нижнем регистре), где у них есть $m$, $m_1$, $m_2$. В Википедии [есть такие] (https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Using_the_Chinese_remainder_algorithm). Эту формулу немного сложно разработать, но ее легко проверить, используя определение оператора $\bmod$. Я не знаю ни одного источника, который заботился бы об этом доказательстве.
fgrieu avatar
флаг ng
@user93353: А, нашел официальное название: обобщенное на произвольное число множителей $n$, это алгоритм Гарнера. Источником является [Справочник по прикладной криптографии] (https://cacr.uwaterloo.ca/hac/), раздел [14.5.2] (https://cacr.uwaterloo.ca/hac/about/chap14.pdf#). стр.=23). Доказательств нет, и это не совсем так, как я это утверждаю, но все же это самое близкое, что я получаю.
флаг et
Спасибо большое

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.