|
Собственно задача:
эллиптическая кривая y^2=x^3+7 mod 211 ее порядок n = 199 начальная точка G = (3, 33) для любой точки Q = kG, лежащей на этой кривой, найти связь (закономерность) с точкой G, т.е. определить:
1. четное или нечетное число точек находится между G и Q (или может оно кратно какому-нибудь числу z)
2. в каком из диапазонов лежит точка Q: k = [1..99] или [100..198]
вот все точки этой кривой (k, x, y)
Есть эллиптическая кривая над конечным полем вида y^2=x^3 + 7 mod p, где p простое число.
Алгебраическое сложение двух точек лежащей на этой кривой (точки ненулевые несимметричные P(x1;y1) и Q(x2;y2)):
если P и Q не равны, тогда P+Q=-R ,
m=(y1-y2)/(x1-x2) mod p,
x3=m^2 - x1 - x2 mod p,
y3 = y1 + m*(x3 - x1) mod p
R(x3;y3) так как для сложения нужно -R,тогда сумма точек P+Q=-R=(x3;-y3).
Если P и Q равны(то есть удвоение точки P(x1;y1)), тогда P+P=-R(x3;-y3),
m=(3*(x1^2))/(2*y1) mod p,
x3=m^2 - x1 - x2 mod p,
y3 = y1 + m*(x3 - x1) mod p.
Скалярное умножения для данной элептической кривой:
n*P=P+P+P+P+....n раз,то есть при умножении точки P на натуральное число n, точку P нужно сложить n раз.
Задача состоит в следующем- Допустим мы имеем некоторую точку Q и знаем ее значение и также знаем значение точки P, нам известно что Q=n*P, n - неизвестная.есть ли алгебраические методы определение четности n без перебора?
Пример.
эллиптическая кривая y^2=x^3+7 mod 211
начальная точка P = (3, 33)
Q(199;38)=n*P(3;33) нужно определить n четное число или нечетное.(в данном примере n=59,то есть нечётное).
Все точки кривой из примера в файле n199.txt
|
07.04.2023, 17:01 