Диофантово уравнение в четности или нечетности чисел?
Я хочу разобраться с формулами решения диофантовых уравнений. Недавно я наткнулся на старую статью посвященная понятиям теории эллиптических кривых. Меня заинтересовал раздел "МЕТОД СЕКУЩИХ ДИОФАНТА".
http://window.edu.ru/resource/758/20758/files/9710_138.pdf
если y^2 = x^3 + ax + b это формула кривой которое образует точки G(x, y)
При сложение координат мы получаем новую точку Jacobian curve
а так же новую точку можно получить и при скалярном умножение точек на порядковый номер (то есть на закрытый ключ)
используя онлайн генератор я построил простенькую кривую
Параметры кривой:
y^2 = x^3 + ax + b % p
p = 897
a = 0; b = 8
Базовая точка G(x) = 268 G(y) = 741
У меня возник вопрос допустим у меня есть новая точка (100, 396) мне неизвестен закрытый ключ к нему и мне неизвестно является ли закрытый ключ четным или нечетным числом.
Можно ли применяя формулы диофантовых уравнений определить является ли закрытый ключ четным или нечетным числом для новой точки (100, 396) ?
Ответы (1 шт):
Во-первых, в статье о диофантовых уравнениях, на которую вы привели ссылку, явным образом сказано
В настоящее время неизвестно никакой общей процедуры для нахождения всех рациональных решений уравнения y2 = x3 + ax2 + bx + c.
Во-вторых, решение диофантового уравнения не даёт ответ на ваш вопрос - найти множитель n такой, что P = nG.
В-третьих, и в главных, статья о диофантовых уравнениях ищет рациональные точки над E, то есть точки с координатами в Q - поле рациональных чисел. У вас же кривая над полем вычетов по модулю простого числа.
Принципиальная разница заключается в том, что квадратный корень в Q извлекается крайне редко - вероятность случайно выбрать число m/n которое является квадратом рационального числа, стремится к нулю по мере роста n. Поэтому уравнение y^2 = ax^3 + bx + c в Q решить крайне нетривиально.
Но в полях вычетов по модулю p половина элементов имеет корень (доказательство смотрите, например, в книге Блейхут Р. Теория и практика кодов, контролирующих ошибки, теорема 4.6.15 на странице 105). Поэтому уравнение y^2 = ax^3 + bx + c решается практически для любого x, и никакие методы решения диофантовых уравнений не требуются.
Поэтому ответ на ваш вопрос - нет, нельзя. Методы решения диофантовых уравнений не применимы для ответа на вопрос является ли чётным число n из уравнения P = nG