Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Matematikai problémák vizsgálata a Maple
programcsomag segı́tségével
Tengely Szabolcs
tengely@science.unideb.hu
http://www.math.unideb.hu/~tengely

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

1 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Áttekintés

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

2 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Feszı́tőfák keresése - Kruskal

Adott G (V , E ) gráf és egy s : E −→ R+ súlyfüggvény.
Keresünk olyan feszı́tőfát, amelyben az élek súlya minimális.
Kruskal algoritmus: rendezzük az éleket növekvő sorrendbe asúlyok szerint, addig választunk be éleket, amı́g fát nem kapunk.
Delete-reverse algoritmus: csökkenő sorrendbe rendezzük az éleketés addig törlünk, amı́g összefüggő gráf marad.

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

3 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Feszı́tőfák keresése - Kruskal> FeszitoFa1:=proc(G)> local g0,f,eG,l; g0:=Graph(NumberOfVertices(G),'weighted');> f:=(x,y)->if x[2]<y[2] then true; else false; end if;> eG:=sort([op(Edges(G,weights))],f);> l:=1; while not IsTree(g0) do> if IsForest(AddEdge(g0,eG[l][1],inplace=false)) then g0:=AddEdge(g0,eG[l]); end if;> l:=l+1;> end do;
> g0;
> end proc;(1)> with(GraphTheory):> with(RandomGraphs):> Graf:=RandomGraph(7,15,connected, weights=1..6);(2)> DrawGraph(Graf);

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

4 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Feszı́tőfák keresése - Kruskal
1
3
1

6

7

6

2

2
4
6

6

6
35

6

3
1

5

4

5

5

4

> DrawGraph(FeszitoFa1(Graf));

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

5 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Feszı́tőfák keresése - Reverse-Delete
1

2

2

1

3

3

5

6

7

1
4

3

4

> FeszitoFa2:=proc(G)> local f,eG,H,l; f:=(x,y)->if x[2]>y[2] then true; else false; end
if;> eG:=sort([op(Edges(G,weights))],f);> H:=G; l:=1;> while not IsTree(H) do> if IsConnected(DeleteEdge(H,eG[l][1],inplace=false)) then> DeleteEdge(H,eG[l]); end if;> l:=l+1; end do;> H;> end proc;(3)

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

6 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple(3)

Feszı́tőfák keresése - Reverse-Delete> DrawGraph(FeszitoFa2(Graf));

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

7 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Feszı́tőfák keresése - Reverse-Delete
1
3
1

7

2

2
4

3

6

3
1

5

4

>

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

8 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Sakktábla bejárásam × n-es sakktábla bejárása
Adott m × n-es sakktábla esetén egy mezőről indulva lóugrással
járjuk be a táblát úgy, hogy minden mezőt pontosan egyszerérintünk és a kiindulópontba jutunk vissza.
Gráfelméletre lehet visszavezetni. Csúcsok: [a1 , a2 ], [b1 , b2 ], . . .
|a1 − b1 ||a2 − b2 | = 2.

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

9 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Sakktábla bejárása
with(GraphTheory):
csucs:=(m,n)->{seq(seq([a,b],a=1..m),b=1..n)};(1)
f:=x->if abs(x[1,1]-x[2,1])*abs(x[1,2]-x[2,2])=2 then true; else false;end if;(2)
A:=(m,n)->select(f,{seq(seq([u,v],u=csucs(m,n)),v=csucs(m,n))});(3)
B:=(m,n)->{seq({convert(k[1],string),convert(k[2],string)},k=A(m,n))};(4)
Gsakk:=(m,n)->Graph(B(m,n));(5)sakkgraf:=Gsakk(6,6);(6)
IsHamiltonian(sakkgraf,'s');
true

(7)

s;
(8)

HighlightTrail(sakkgraf,s,red);
DrawGraph(sakkgraf);

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

10 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Sakktábla bejárása[1, 1][1, 3][1, 5][2, 2][2, 4][2, 6][3, 1][3, 3][3, 5][4, 2][4, 4][4, 6][5, 1][5, 3][5, 5][6, 2][6, 4][6, 6][1, 2][1, 4][1, 6][2, 1][2, 3][2, 5][3, 2][3, 4][3, 6][4, 1][4, 3][4, 5][5, 2][5, 4][5, 6][6, 1][6, 3][6, 5]

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

11 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Gráfok szı́nezése - algebrai út

Csúcsok szı́nezések-szı́nezés:f (x) = x(x − 1)(x − 2) · · · (x − k + 1)véges test feletti polinom.
f (x1 ) = 0,f (x2 ) = 0, . . . , f (xn ) = 0

garantálja, hogy minden csúcsot kiszı́nezünk.

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

12 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Gráfok szı́nezése - algebrai út

Csúcsok szı́nezésef (xi ) − f (xj )osztható xi − xj -vel.
g (xi , xj ) =f (xi ) − f (xj ).
xi − xj

Minden xi xj ∈ E esetében g (xi , xj ) = 0.

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

13 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Gráfok szı́nezése - algebrai útszin:=proc(G,k)
local f,g,n,rendszer, el,T,t; f:=x->expand(product(x-a,a=0..k-1));
g:=(x,y)->simplify((f(x)-f(y))/(x-y));n:=NumberOfVertices(G);rendszer:={x[1]} union {seq(f(x[j]),j=2..n)};el:=Edges(G);for T in el do t:=op(T);rendszer:=rendszer union {g(x[t[1]],x[t[2]])};
end do;rendszer;end proc;(1)

with(GraphTheory): K3:=CompleteGraph(3);(2)
szin(K3,2);(3)[msolve(szin(K3,2),3)];(4)[msolve(szin(K3,3),3)];(5)
with(SpecialGraphs): P:=PetersenGraph();(6)
A:=[msolve(szin(P,3),5)];(7)

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

14 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple(7)

Gráfok szı́nezése - algebrai út
a1:=[seq(op(A[1][k])[2],k=1..10)];(8)for s from 1 to 10 do HighlightVertex(P,s,COLOR(RGB,1/(1.5-a1[s]),1/(2.9-a1[s]),1/(7.1-a1[s])));
end do;DrawGraph(P);

1

6

5

2
8

9

10

4

Tengely Szabolcs

2014.04.26

7

3

Matematikai problémák és a Maple

15 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Mátrixok hatványai sajátvektorokkal

Diagonalizálás
A egy mátrix, P a sajátvektorokból álló mátrix:
P −1 APdiagonális. Ezt felhasználva meghatározhatjuk az An mátrixot zárt
alakban.

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

16 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Rekurzı́v sorozatok

Fibonacci sorozat
F0 = 0, F1 = 1 és Fn = Fn−1 + Fn−2 , legyen


1 1
A=
1 0
ekkor An

Tengely Szabolcs



1
0




=

Fn+1
Fn

2014.04.26

.

Matematikai problémák és a Maple

17 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Inhomogén rekurzı́v egyenletrendszer

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

18 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Mátrixok hatványai sajátvektorokkal
with(LinearAlgebra):matrixN:=proc(A)local u,v,Diag; u,v:=Eigenvectors(A);Diag:=Matrix([[u[1]^n,0],[0,u[2]^n]]);v.Diag.v^(-1);
end proc;(1)

matrixN(Matrix([[4,-3],[1,0]]));(2)

Fib:=(matrixN(Matrix([[1,1],[1,0]])).Vector([1,0]))[2];(3)
simplify(Fib);(4)
seq(evala(subs(n=k,Fib)),k=0..10);(5)
A:=Matrix([[2,1],[1,2]]);(6)
U1:=subs(t=n,sum(matrixN(A),n=0..t-1)).Vector([1,1]);(7)

U2:=matrixN(A).Vector([2,3]);(8)

U1+U2;(9)Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

19 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Berlekamp algoritmus

Polinomok Fq [X ] felett
f (X ) =Pn

k=0 ai X

i ekkor a kis Fermat-tétel miattf (X )q =nXai X qi .

k=0

Az X q − X polinom faktorizációja egyszerű. Egy F polinom
faktorizációjához keresunk olyan f (X )-et, amelyref (X ) ≡ f (X )q

Tengely Szabolcs

2014.04.26(mod F ).

Matematikai problémák és a Maple

20 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Berlekamp algoritmus
P:=x^5+10*x^4+25*x^2+28;(1)
h:=add(s,s=[seq(a[i]*x^i,i=0..4)]);(2)h31:=add(s,s=[seq(a[i]*x^(31*i),i=0..4)]);(3)for k from 31 to 124 do h31:=subs(x^k=modpol(x^k,P,x,31),h31); end do:
h31;
(4)

with(LinearAlgebra):
sys:=[seq(coeff(h31,x,k)=coeff(h,x,k),k=0..4)];(5)

var:=[seq(a[k],k=0..4)];(6)(A,b):=GenerateMatrix(sys,var);(7)

with(LinearAlgebra[Modular]):
A31:=Mod(31,A,integer[]);(8)

N:=Basis(31,A31,row,false,column);(9)

T1:=x^3+12*x^2+26*x;(10)
for k from 0 to 30 do PT:=Gcd(P,T1+k) mod 31; if PT<>1 then print(PT);end if; end do:(11)

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

21 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Berlekamp algoritmus(11)

T2:=x^4+7*x^2+17*x;(12)
for k from 0 to 30 do PT:=Gcd(P,T2+k) mod 31; if PT<>1 then print(PT);end if; end do:(13)

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

22 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Rácsok

Adott b1 , b2 , . . . , bk vektorok Rn -ben,Λ = {z1 b1 + z2 b2 + . . . + zk bk : zi ∈ Z}
egy rács.
Adott rácsot több vektorrendszer is meg tud határozni. Rövid
vektorokból álló rendszerek a gyakorlatban hasznosak(titkosı́tások). Az LLL-algoritmus segı́tségével találunk rövid
vektorokat. Bemutatunk néhány érdekes alkalmazást.

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

23 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Polinomok gyökei
f:=expand(cos(16*x));(1)

cos(Pi);(2)
F:=subs(cos(x)=X,f)+1;(3)

Fsol:=solve(F,X);(4)

evalf(Fsol[13]);(5)a:=evalf[25](cos(Pi/16));(6)
with(LinearAlgebra):
M:=Matrix(9,shape=identity);(7)

M1:=<M|<seq(round(evalf[100](10^50*cos(Pi/16)^k)),k=0..8)>>;Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

24 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Polinomok gyökei(8)

with(IntegerRelations):
T:=LLL(M1);(9)

fx:=add(u,u=[seq(T[1,t]*x^(t-1),t=1..9)]);(10)
solve(fx,x);(11)

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

25 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Polinomok faktorizációjaf:=expand((x^5+x^2+2014)*(x^6+x^3+x+2014));(1)
factor(f);(2)
a:=evalf[50](fsolve(f,x));(3)
with(LinearAlgebra):
M:=Matrix(6,shape=identity);(4)

M1:=<M|<seq(round(evalf[50](10^20*a^k)),k=0..5)>>;(5)

with(IntegerRelations):
LLL(M1);(6)Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

26 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Hátizsák probléma - Merkle-Hellman titkosı́tás
S:=[7,11,19,39,79,159,329,649,1297,2663];add(k,k=S);(1)

p:=nextprime(5252);(2)
m:=3000;(3)
minv:=1/m mod p;(4)publikus:=[seq((S[k]*m) mod p,k=1..nops(S))];(5)uzenet:=[1,0,1,0,1,0,1,0,1,0];(6)kodolt:=add(t,t=[seq(uzenet[k]*publikus[k],k=1..nops(S))]);(7)
u1:=kodolt*minv mod p;(8)hatizsak:=proc(H,s)
local V,k,s1; V:=[seq(0,k=1..nops(H))];s1:=s;for k from nops(H) to 1 by -1 do
if s1>=H[k] then V[k]:=1; s1:=s1-H[k]; end if;
end do;V;
end proc;(9)

hatizsak(S,u1);(10)
with(LinearAlgebra):
M:=Matrix(10,shape=identity);

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

27 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Hátizsák probléma - Merkle-Hellman titkosı́tás(11)

M1:=convert(<M,Vector[row](10,fill=0)>,matrix);(12)

M2:=<M1|Vector[column](11,[seq(publikus[k],k=1..10)],fill=-kodolt)>:
convert(M2,matrix);(13)

with(IntegerRelations):
convert(LLL(M2),matrix);

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

28 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Hátizsák probléma - Merkle-Hellman titkosı́tás(14)

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

29 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Index kalkulus

Additı́v és multiplikatı́v csoportok(G , +) =⇒ ng1 = g2
(H, ×) =⇒ h1n = h2

additı́v

multiplikatı́v

Fq multiplikatı́v csoportban:tm
ak ≡ p1t1 p2t2 · · · pm(mod q)k ≡ t1 loga p1 + t2 loga t2 + . . . + tm loga pm

Tengely Szabolcs

2014.04.26(mod q − 1)

Matematikai problémák és a Maple

30 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Index kalkulus> q:=101;(1)> nops({seq(7^k mod 101,k=1..101)});
100

(2)

> seq([k,ifactor(7^k mod 101)],k=1..20);(3)> with(LinearAlgebra[Modular]):> M:=Mod(100,Matrix([[0,0,0,1],[3,0,1,0],[0,1,2,0],[3,1,0,0]]),integer[]);(4)> MI:=Inverse(100,M);(5)> b:=Mod(100,Matrix(4,1,[1,3,13,8]),integer[]);(6)> Multiply(100,MI,b);(7)> seq([k,ifactor(7^k*25 mod 101)],k=1..20);(8)> x:=(41+36-5) mod 100;(9)
> 7^72 mod 101;
(10)
> IndexCalc:=proc(a,b,q,FB) local B,M,M1,k,l,r,LOGS,logseq;> with(numtheory): with(padic):

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

31 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Index kalkulus> with(LinearAlgebra[Modular]):> B:=Mod(q-1,Matrix(nops(FB),1),integer[]);> M:=Mod(q-1,Matrix(nops(FB),nops(FB)),integer[]);> M1:=M; k:=1; l:=1; r:=[seq(Rank(p,M1),p=factorset(q-1))];> while add(s,s=[seq(Rank(p,M),p=factorset(q-1))])<nops(factorset(q-1))*nops(FB) do> if evalb(factorset(a^k mod q) subset FB) then M1[l]:=Mod(q-1,Matrix(1,nops(FB),[seq(ordp(a^k mod q,f),f=FB)]),integer[]); print(M1,r,[seq(Rank(p,M1),p=factorset(q-1))],l,k); end if;> if add(s,s=[seq(Rank(p,M1),p=factorset(q-1))])-add(s,s=r)=nops(factorset(q-1)) then M:=M1; B[l]:=k; l:=l+1; r:=[seq(Rank(p,M1),p=factorset(q-1))];
end if; k:=k+1;> end do;> M; print(FB); LOGS:=Multiply(q-1,Inverse(q-1,M),B); print(LOGS);> k:=1; while not evalb(factorset((a^k*b) mod q) subset FB) do> k:=k+1; print(k); print(factorset((a^k*b) mod q));
> end do;> logseq:=[seq(ordp((a^k*b) mod q,f),f=FB)]; print(logseq);> (add(k,k=[seq(LOGS[t,1]*logseq[t],t=1..nops(LOGS))])-k) mod (q-1);> end proc;(11)

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

32 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Index kalkulus> IndexCalc(7,24,101,{2,3,5,7,11});

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

33 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Index kalkulus

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

34 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Index kalkulus

2
3
4

8

Tengely Szabolcs

2014.04.26(12)

Matematikai problémák és a Maple

35 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Elliptikus görbék - összeadás

Elliptikus görbe
E:y 2 = x 3 + ax + b

E (Q) = {(x, y ) ∈ Q2 : y 2 = x 3 + ax + b} ∪ {∞}.
A görbe pontjain bevezetünk egy összeadás műveletet.

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

36 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Elliptikus görbék - összeadásy 2 = x 3 − 3x + 7

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

37 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Elliptikus görbék - összeadásTengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

38 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Elliptikus görbék - összeadásTengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

39 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Elliptikus görbék - összeadás

Most bemutatjuk hogyan lehet a Maple segı́tségével az összeadástelvégezni adott elliptikus görbék esetében. A módszer működik ZN
felett is, de összetett N esetében előfordulhat, hogy nem tudunk
kiszámı́tani bizonyos nevezőket. Ezt fel tudjuk használni
faktorizációra.

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

40 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Elliptikus görbék - összeadás> elliptic_add := proc(p1,p2,E) local g,inv,x1,x2,x3,y1,y2,y3,a,b,n;x1 := p1[1]; x2 := p2[1]; y1 := p1[2]; y2 := p2[2];a := E[1]; b := E[2]; n := E[3];if (x1=infinity and y1=infinity) then [x2,y2];elif (x2=infinity and y2=infinity) then [x1,y1];elif (x1=x2 and y1 <> y2) then [infinity,infinity];
elif (x1=x2 and y1=y2 and y1<>0) theng := igcdex(2*y1,n,inv);
if g = 1 thenx3 := ((3*x1^2+a)*inv)^2-2*x1 mod n;y3 := ((3*x1^2+a)*inv)*(x1-x3)-y1 mod n;[x3,y3];else g; end if;
elif (x1=x2 and y1=y2 and y1=0) then[infinity,infinity];else
g := igcdex(x2-x1,n,inv);
if g = 1 thenx3 := ((y2-y1)*inv)^2-x1-x2 mod n;y3 := (y2-y1)*inv*(x1-x3)-y1 mod n;[x3,y3];else g; end if;
end if;end proc;(1)

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

41 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Elliptikus görbék - pont többszöröse> elliptic_mul := proc(p1,k,E) local pn,ps,d,r;
pn := p1; r := irem(k,2);
if r = 1 then ps := p1; else ps := [infinity,infinity]; end if;
d := (k-r)/2;
while (d > 0 and (not (type(ps,integer) or type(pn,integer)) and (pn <>[infinity,infinity]))) dor := irem(d,2);
pn := elliptic_add(pn,pn,E);
if r = 1 then ps := elliptic_add(ps,pn,E); end if;
d := (d-r)/2;
end do;if type(pn,integer) then pn;else ps; end if;
end proc;(2)> N:=65^64+64;(3)> elliptic_mul([0,1],2*3*5*7*11*13*17*19,[21,1,N]);(4)> N mod 12653;(5)> N/12653;(6)> k:=1; while nops(elliptic_mul([0,1],2*3*5*7*11*13*17*19*23*29*31*37*41*43,[k,1,N/12653]))<>1 do k:=k+1; end do:
(7)
> k;
(8)

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

42 / 43

Maple és a gráfelmélet
Maple és lineáris algebra
Maple és az LLL-algoritmus
Index kalkulus Maple segı́tségével
Elliptikus görbék és a Maple

Elliptikus görbék - faktorizáció
(8)> elliptic_mul([0,1],2*3*5*7*11*13*17*19*23*29*31*37*41*43,[31,1,N/12653]);(9)> k:=1; while nops(elliptic_mul([0,1],2*3*5*7*11*13*17*19*23*29*31*37*41*43,[k,1,N/(12653*136573)]))<>1 do k:=k+1; end do:
(10)
> k;
(11)
> elliptic_mul([0,1],2*3*5*7*11*13*17*19*23*29*31*37*41*43,[131,1,N/(12653*
136573)]);(12)> N/(12653*136573*89009);(13)> k:=1; while nops(elliptic_mul([0,1],2*3*5*7*11*13*17*19*23*29*31*37*41*43,[k,1,N/(12653*136573*89009)]))<>1 do k:=k+1; end do:
(14)
> k;
(15)
> elliptic_mul([0,1],2*3*5*7*11*13*17*19*23*29*31*37*41*43,[161,1,N/(12653*
136573*89009)]);(16)> N/(12653*136573*89009*929501);(17)> k:=1; while nops(elliptic_mul([0,1],2*3*5*7*11*13*17*19*23*29*31*37*41*43,[k,1,N/(12653*136573*89009*929501)]))<>1 do k:=k+1; end do:
(18)
> k;
(19)
> elliptic_mul([0,1],2*3*5*7*11*13*17*19*23*29*31*37*41*43,[376,1,N/(12653*
136573*89009*929501)]);(20)> N/(12653*136573*89009*929501*2500297);(21)

Tengely Szabolcs

2014.04.26

Matematikai problémák és a Maple

43 / 43