Appendix B: Software
279
ical problems we use MATLAB’s built-in powermod() function instead of mod()
function.
% ECadd_p.m
function Pc=ECadd_p(Pa,Pb,a,b,p)
if Pa(2) == Inf, Pc=Pb; return; end
if Pb(2) == Inf, Pc=Pa; return; end
if Pa(1) == Pb(1) & Pa(2) ˜= Pb(2), Pc=[0,Inf]; return; end
if Pa(1) == Pb(1)
if Pa(2) == Pb(2) & Pa(2) == 0
Pc=[0,Inf];
return
else
denominv=powermod(2*Pa(2),p-2,p); % (12.34)
s=powermod((3*Pa(1)*Pa(1)+a)*denominv,1,p);
end
else
denominv=powermod(Pb(1)-Pa(1),p-2,p);
s=powermod((Pb(2)-Pa(2))*denominv,1,p);
end
Pc(1)=powermod(s*s-Pa(1)-Pb(1),1,p);
% (12:33)
Pc(2)=powermod(-s*(Pc(1)-Pa(1))-Pa(2),1,p);
The following script ECCadd_p_test.m prepares the two plots shown in Fig. 12.7.
After defining the parameters a, b, and p as well as the function f2 for the righthand side of the elliptic equation, we choose the x-coordinate of the generator G
and search a suitable y-coordinate that lies on the curve. Note that not all values of
x lead to a suitable value of y. We break the routine, if no point is found. Otherwise,
we plot the G as a red asterisk, and start a loop in which G is repeatedly added
to P c until the point at infinity appears, which indicates the order to the underlying
group G, as discussed in Sect. 12.7. At this point we break the execution of loop and
plot the points and annotate the axes.
% ECadd_p_test.m
clear all; close all
p=113; a=0; b=7;
f2=@(x)powermod(x.ˆ3+a*x+b,1,p);
xstart=15;
% order: 13->114, 15->19
y2=f2(xstart)
for k=1:p
% is it on the curve?
yy=powermod(k,2,p);
if yy==y2
q=[k,yy];
G=[xstart,k]
break