Как вы строите эллиптические кривые над конечным полем, используя Matlab

Мне нужно нарисовать эллиптическую кривую над конечным полем F17 (другими словами, я хочу нарисовать какие-то определенные точки на кривой), но у меня что-то не получается.

Кривая определяется уравнением:

y^2 = x^3 +x + 1 (mod 17)

Я пробовал способ ниже, но он не может работать.

для x = 0:16, plot(x, mod(sqrt(x^3+x+1), 16),'r')', end

Может ли кто-нибудь помочь?

[Обновление]

Согласно предложениям Натана и Билла, вот слегка измененная версия.

 x = 0:18
 plot(mod(x,16), mod(sqrt(x.^3+x+1), 16),'ro')

Однако мне кажется, что цифра НЕВЕРНАЯ , например, y не является целым числом, когда x=4 .

введите здесь описание изображения


matlab cryptography matlab-figure
person Matt Elson    schedule 06.02.2012    source источник
comment
В вашем определении кривой вы пишете mod 17, а в своей функции Matlab mod 16, какой из них правильный?   -  person Lucas    schedule 06.02.2012
comment
Проблема в том, что вы используете sqrt. Функция matlab sqrt не работает с конечными телами.   -  person Lucas    schedule 06.02.2012
comment
График эллиптической кривой над конечным полем на самом деле не имеет смысла, он выглядит как случайно разбросанные точки. Чтобы вычислить квадратный корень по модулю простого числа, см. этот алгоритм, который не должен быть слишком сложным для реализации в Matlab.   -  person President James K. Polk    schedule 08.02.2012

Ответы (3)


arrow_upward
3
arrow_downward

Вы должны проверить все точки, которые удовлетворяют уравнению y^2 = x^3 +x + 1 (mod 17). Поскольку это конечное поле, вы не можете просто извлечь квадратный корень из правой части.

Вот как бы я поступил:

a=0:16  %all points of your finite field
left_side = mod(a.^2,17)  %left side of the equation
right_side = mod(a.^3+a+1,17) %right side of the equation

points = [];


%testing if left and right side are the same 
%(you could probably do something nicer here)
for i = 1:length(right_side)
    I = find(left_side == right_side(i));
    for j=1:length(I)
        points = [points;a(i),a(I(j))];
    end
end

plot(points(:,1),points(:,2),'ro')
set(gca,'XTick',0:1:16)
set(gca,'YTick',0:1:16)
grid on;

эллиптическая кривая

person Lucas    schedule 06.02.2012
comment
+1, мне кажется, все в порядке (обратите внимание, что точки идут парами с координатами y и 17-y). - person Krystian; 06.02.2012
comment
Большое спасибо, я искал способ сделать это, он дает правильный сюжет - person Hind Dev; 11.01.2019

arrow_upward
1
arrow_downward

Matlab изначально работает с векторами.

ваш синтаксис был близок, но его нужно векторизовать:

x = 0:16
plot(x, mod(sqrt(x.^3+x+1), 16),'r')

Обратите внимание на . в x.^3. Это говорит Matlab кубировать каждый элемент x по отдельности, а не возводить вектор x в третью степень, что ничего не значит.

person Nathan Fellman    schedule 06.02.2012
comment
Попробовав ваше предложение, я обнаружил, что Matlab неожиданно рисует кривую, а не несколько точек) - person Matt Elson; 06.02.2012
comment
Попробуйте изменить 'r' на 'ro' в ответе @Nathan, чтобы получить точки. - person Bill Cheatham; 06.02.2012
comment
ваш mod() должен быть 17, а не 16, так как его FF_{17}. - person Krystian; 06.02.2012
comment
Более того, AFAIK, возведение в квадрат в Matlab выполняет квадратный корень с действительным знаком, который не имеет смысла в конечном поле. Попробуйте, например. GP/Pari для чего-то, что лучше подходит для модульной/конечной арифметики полей. - person Krystian; 06.02.2012

arrow_upward
0
arrow_downward

Вы можете использовать этот код, если хотите построить на действительных числах:

syms x y;
v=y^2-x^3-x-1;
ezplot(v, [-1,3,-5,5]);

Но для сюжета по модулю сначала вы можете написать код ниже;

X=[]; for x=[0:16], z=[x; mod(x^3+x+1,17)]; X=[X, z]; end, X,

Затем вы можете построить X с матрицей координат.

person R. Jalaei Salahi    schedule 09.05.2017