Debreceni Egyetem
Természettudományi Kar
Matematikai Intézet

Diplomamunka/Szakdolgozat

Diszkrét logaritmus
készítette:

Vasenszki Zoltán

témavezet®: Dr. Tengely Szabolcs

Debrecen, 2010.10.23.

Tartalomjegyzék

Tartalomjegyzéki

1 Bevezetés

3

2 Diszkrét logaritmus

9

3 Magma kód

17

Irodalomjegyzék

21

1.1. A csoport fogalma és néhány alapvet® tulajdonságai . . . . . . . .
1.2. A csoportok és elemeik rendje, részcsoportok . . . . . . . . . . . .

3
5

2.1. A diszkrét logaritmus probléma . . . . . . . . . . . . . . . . . . . . 92.2. Az index kalkulus módszer . . . . . . . . . . . . . . . . . . . . . . . 10
2.3. Példa az algoritmus m¶ködésére . . . . . . . . . . . . . . . . . . . . 11
2.4. Faktorbázis és a kiválasztás módszere . . . . . . . . . . . . . . . . . 11iKöszönetnyilvánítás

Ezúton szeretnék köszönetet mondani a szüleimnek, akik a kezdetekt®l fogva családi és anyagi hátteret biztosítottak számomra tanulmányaim sikeres befejezéséhez.

1

1. Bevezetés

A következ® bevezet® részben az algebra néhány alapvet®, a csoportokkal foglalkozó
eredményei kerülnek bemutatásra. A fejezet Bódi Béla Algebra [1] cím¶ könyvének
a felhasználásával készült.
1.1. A csoport fogalma és néhány alapvet® tulajdonságai

1.1.1. Deníció. Az A és a B adott halmazok A × B direkt szorzata (vagyDescartes-féle szorzata) az

A × B = {(a, b)|a ∈ A, b ∈ B}

halmaz, ahol az (a, b) rendezett pár.

1.1.2. Deníció. Egy A × A −→ A leképezést kétváltozós m¶veletnek (vagybinér m¶veletnek) nevezünk.

Egy kétváltozós m¶velet egy adott A halmazon annak bármely két eleméhez
egy harmadikat rendel: ∀a, b ∈ A : (a, b) ∈ A.

1.1.3. Deníció. (M¶veletek tulajdonságai) Egy (kétváltozós) ∗ : A × A −→ Am¶velet1. asszociatív, ha:∀a, b, c ∈ A : (a ∗ b) ∗ c = a ∗ (b ∗ c)

2. kommutatív, ha:∀a, b ∈ A : a ∗ b = b ∗ a

Példák:• A Z egész számok halmazán az azon deniált + összeadás és · szorzás kommutatív és asszociatív, de a − kivonásra egyik sem igaz.
• Az a, b Rn -beli vektorok < a, b >∈ R skaláris szorzatára igaz, hogy
< a, b >=< b, a >tehát ez a kétváltozós m¶velet kommutatív.
3

4

FEJEZET 1.

BEVEZETÉS• A mátrixok körében deniált szorzás asszociatív, hiszen ha A ∈ Mm×n ,B ∈ Mn×p , C ∈ Mp×r , D = A · B , G = B · C , F = (A · B) · C és
H = A · (B · C), akkor a mátrixok szorzásának deníciója szerintXdi,j =
ai,k · bk,jkgi,j =

Xbi,k · ck,jkés így
fi,j

=

XX
XX
(
ai,l · bl,j ) · ck,j =ai,l · bl,k · ck,j =

=

X

k

l

k

l

X
X
ai,l · (bl,k · ck,j ) =ai,l · gl,j = hi,j

l

k

l

viszont nem kommutatív, hiszen
1 2
3 4

!

0 1
0 0

!
=

0 1
0 3

!
6=

3 4
0 0

!
=

0 1
0 0

!

1 2
3 4

!
.

1.1.4. Deníció. (G, ∗) neve félcsoport, ha ∗ egy kétváltozós asszociatív m¶veleta G halmazon.

Megjegyzés: ha ∃e ∈ G :∀a ∈ G : a ∗ e = e ∗ a = a

akkor G neve egységelemes félcsoport, e a ∗ m¶veletre nézve neutrális elem.
Például az n × n-es R feletti mátrixok a mátrixszorzás m¶velettel félcsoportot
alkotnak.

1.1.5. Deníció. G csoport a ∗ m¶veletre nézve, ha félcsoport és∀a ∈ G : ∃a−1 : a ∗ a−1 = a−1 ∗ a = e

Ha a ∗ m¶velet kommutatív, akkor kommutatív csoport(Abel-csoport).
Az a−1 elemet az a elem inverzének nevezzük.

Példák:• A Z egész számok halmaza a rajtuk értelmezett + összeadás m¶veletre te-kintve kommutatív-csoport.

• az n × n-es R feletti invertálható mátrixok a mátrixszorzás m¶velettel (nemkommutatív) csoport.

A csoportok néhány egyszer¶ tulajdonságai:1.2.

A CSOPORTOK ÉS ELEMEIK RENDJE, RÉSZCSOPORTOK

5

1.1.1. Tétel. Bármely (G, ∗) csoportra igazak a következ®k:1.

G neutrális eleme egyértelm¶

2.

G minden elemének inverze egyértelm¶3.

∀a ∈ G-re (a−1 )−1 = a

4.

∀a, b ∈ G-re (a ∗ b)−1 = b−1 ∗ a−1

1. Legyenek e és f neutrális elemei a csoportnak, ekkor a neutrális
elem denícióját felhasználva

Bizonyítás.

e=e∗f =f ∗e=f

nyerhet®, így a neutrális elem valóban egyértelm¶.
2. Legyenek a, b, c ∈ G, b, c egyaránt az a elem inverzei. Ekkor
c = c ∗ e = c ∗ (a ∗ b) = (c ∗ a) ∗ b = e ∗ b = b

adódik, a ∗ m¶velet asszociativitása miatt, tehát a csoport tetsz®leges elemének inverze egyértelm¶.
3. A harmadik állítás következik a másodikból, hiszen ha egy elem inverzének
az inverze egy harmadik elem lenne, nem állna fenn az egyértelm¶ség.
4.
(a∗b)∗(b−1 ∗a−1 ) = a∗(b∗(b−1 ∗a−1 )) = a∗((b∗b−1 )∗a−1 ) = a∗(e∗a−1 ) = e

1.2. A csoportok és elemeik rendje, részcsoportok

1.2.1. Deníció. Egy G csoport véges, ha elemeinek száma véges, ez a szám acsoport rendje.
Jele: ord(G)Nem véges elemszámú csoport rendje végtelen.

1.2.2. Deníció. Legyen a ∈ (G, ∗). Ha am = 1, m ∈ Z (a hatványozása a ∗m¶velet ismételt végrehajtása önmagával), akkor a véges rend¶, ha @n : n <m, an = 1, akkor m az a rendje. Ha nem létezik ilyen véges szám, akkor avégtelen rend¶ elem.

Jele: ord(a)1.2.1. Tétel. Ha a ∈ G rendje n, akkor am = 1-b®l n|m következik.

6

FEJEZET 1.

BEVEZETÉSAz m szám maradékos osztással el®áll m = n · q + r alakban, ahol
0 ≤ r < n, ebb®l pedig
Bizonyítás.

am = an·q+r = (an )q · ar = ar = 1

miatt r = 0.

1.2.3. Deníció. Legyen (G, ∗) csoport, H ⊆ G. Ha (H, ∗) csoport, akkor a H
csoport részcsoportja a G-nek.
1.2.2. Tétel. Egy H ⊆ G halmaz akkor és csak akkor részcsoport, ha ∀a, b ∈ H :a−1 ∗ b ∈ H .

Ha H részcsoport, akkor minden a, b ∈ H esetén a−1 ∗ b ∈ H teljesül.
A másik irány belátásának feltéltele, hogy a−1 ∗b ∈ H igaz minden a, b ∈ H -re.
Kell, hogy a csoportm¶velet asszociatív legyen a H halmazon, ez a tulajdonságörökl®dik G-b®l. Kell továbbá a neutrális elem és az inverz elemek létezése. A
feltevés szerint ∀c ∈ H : e = c ∗ c−1 ∈ H és ebb®l c−1 ∗ e ∈ H , tehát létezik
neutrális elem, és minden elemnek létezik az inverze is, tehát H részcsoportja
G-nek.
Bizonyítás.

1.2.4. Deníció. Legyen G csoport, u ∈ G, H ⊆ G részcsoportja. Ekkor az
uH = {u ∗ h|∀h ∈ H}
Hu = {h ∗ u|∀h ∈ H}

halmazokat a G csoport H részcsoport szerinti baloldali és jobboldali mellékosztályainak nevezzük.
Megjegyzés: Abel-csoportok esetén uH és Hu megegyeznek ∀u esetén.

Példa: n > 1 esetén nZ az n-el osztható számok halmaza. A (Z, +) csoport

nZ szerinti mellékosztályai a modulo n maradékosztályok.

1.2.3. Tétel. Legyen H ⊆ G részcsoport. Ekkor:
1.

c ∈ bH =⇒ cH = bH2.

bH ∩ cH = ∅ és bH = cH
közül pontosan az egyik igaz.

1. c ∈ H miatt c írható b ∗ h1 alakban, ahol h1 ∈ H . Tetsz®legesc ∗ h ∈ cH elemreBizonyítás.

c ∗ h = (b ∗ h1 ) ∗ h = b ∗ (h1 ∗ h) =⇒ c ∗ h ∈ bH =⇒ cH ⊆ bH

Hasonlóan belátható a másik irányú tartalmazás.

1.2.

A CSOPORTOK ÉS ELEMEIK RENDJE, RÉSZCSOPORTOK

7

2. Tegyük fel, hogy c ∈ aH ∩ bH . Ekkor cH = aH és cH = bH =⇒ aH = bH
Megjegyzés: ebb®l a két tulajdonságból következik, hogy a G csoport H szerinti baloldali mellékosztályai G-nek egy osztályozását adják.

1.2.4. Tétel. (Lagrange-tétel) Ha H ⊆ G részcsoportja és G véges, akkor
ord(H)|ord(G).

Legyen a G egy osztályozása a1 H, a2 H, . . . , as H . Ekkor G = a1 H ∪a2 H ∪ . . . ∪ as H , ahol i 6= j esetén ai H ∩ aj H = ∅.
ord(ai H) = ord(H), emiattBizonyítás.

|G| = |a1 H| + |a2 H| + . . . + |as H| = s|H|

1.2.5. Deníció. A G csoport egy M részhalmazát a csoport generátorrendszerének nevezzük, ha az ®t tartalmazó legsz¶kebb részhalmaz G.
1.2.6. Deníció. Az egy elemmel generált csoport neve ciklikus csoport.
Példa: Z/pZ ciklikus.
1.2.5. Tétel. Ha egy véges csoport rendje prím, akkor a csoport ciklikus.
Bizonyítás. Legyen a G csoport rendje p prím, a ∈ G a neutrális elemt®l különböz®. Az a által generált H részcsoport rendje Lagrange tétele miatt osztja G
rendjét, p-t, tehát az is egyenl® p-vel, és így H = G ciklikus csoport.

2. Diszkrét logaritmus

Ezen fejezet célja a diszkrét logaritmus problémának (DLP) és annak egy lehetséges megoldásának, az index kalkulus módszernek a bemutatása. A fejezet Raminder Ruprai az interneten fellelhet® Improvements in the Index-Calculus algorithm for Solving the Discrete Logarithm problem over Fp [3] cím¶ munkájából
merít.
2.1. A diszkrét logaritmus probléma

A diszkrét logaritmus probléma (DLP) a következ® módon értelmezhet®:ax = bahol a, b ∈ G valamilyen G csoportra, b ∈< a > (b az a által generált részcsoport
eleme), a hatványozás a csoportm¶velet ismételt végrehajtását jelöli, és az x ∈ Z
meghatározása a feladat.
A DLP legjobban Z/pZ fölött szemléltethet®, ezért a továbbiakban csak ez a
speciális eset kerül tárgyalásra.

2.1.1. Deníció. Legyenek a, b ∈ Z/pZ, p prím, a pedig generátora Z/pZ-nek.
Ekkor a diszkrét logaritmus problémája olyan x ∈ Z keresése, melyreax ≡ b(mod p)teljesül.

2.1.2. Deníció. Legyen n, p ∈ N. Az n p-sima, ha n kanonikus alakjában

fellép® összes prímtényez® nem nagyobb, mint p.

Példa: A 84 szám 84 = 22 · 3 · 7 miatt 7-sima.

9

10

FEJEZET 2.

DISZKRÉT LOGARITMUS

2.2. Az index kalkulus módszer

Legyen B egy halmaz, melynek tagjai néhány pozitív prím. Ekkor B neve faktorbázis.

2.2.1. Deníció. Egy n ∈ N szám F -sima, ha az n kanonikus alakjában fellép®
prímek mind elemei az F faktorbázisnak:
n = pr11 · pr22 · · · · · prl l
F = {. . . , p1 , p2 , . . . , pl , . . .}Az eljárás elején választunk egy véletlenszer¶ t ∈ (1 . . . p − 1) számot, és errekiszámítjuk
at ≡ c (mod p)értékét, és c-t mint egész számot faktorizájuk.
Ekkor c kanonikus alakja:
c = pr11 · pr22 · · · · · prl laAmennyiben c B -sima, úgy a kanonikus alakjának logaritmusát véve adódikt ≡ r1 loga p1 + r2 loga p2 + · · · + rl loga pl(mod p − 1)egyenlet, melyben a logaritmus értékek az ismeretlenek. Ha legalább l darab
ilyen véletlenszer¶en választott t számot találunk, akkor egy olyan egyenletrendszer nyerhet®, melyb®l a pi prímek diszkrét logaritmusa meghatározható.

Megjegyzés: A különböz® egyenletek együtthatóiból kapott szám l-esek mint

vektorok közül legalább l darab vektor lineáris függetlensége szükséges a megoldhatósághoz.
Ezzel megkaptuk a B minden elemének a diszkrét logaritmusát.
A következ® lépésben véletlenszer¶ q számokra vizsgáljuk, hogy aq · b B -simae modulo p. Ha igen, akkor
aq · b ≡ pd11 · pd22 · · · · pdnn(mod p)alakban írható, ahol pi , i ∈ {1 . . . n} a B faktorbázis elemei. Ennek a logaritmusátvéve
q + loga b ≡ d1 loga p1 + d2 loga p2 + · · · + dn loga pn(mod p)adódik, melyb®l csak a x = loga b nem ismert, ennek értéke (mely a probléma
megoldása) átrendezéssel nyerhet®.

2.3.

11

PÉLDA AZ ALGORITMUS MKÖDÉSÉRE

2.3. Példa az algoritmus m¶ködésére

A feladat: 19k = 4 (mod 5209).
A faktorbázis {2, 3, 5}.
Ekkor:
1930 ≡ 2 · 3 · 5
180≡ 2·3 ·5

274

4

19
19

2

(mod 5209)
2(mod 5209)≡ 2 ·3 ·5(mod 5209)

2

melynek logaritmusát véve
30 ≡ log19 2 + log19 3 + log19 5(mod 5208)

180 ≡ log19 2 + 2 · log19 3 + 2 · log19 5(mod 5208)

274 ≡ 4 · log19 2 + 2 · log19 3 + log19 5(mod 5208)

adódik.
Az egyenletrendszert megoldva a választott prímek logaritmusai:
log19 2 ≡ 5088

(mod 5208)

log19 3 ≡ 604(mod 5208)

log19 5 ≡ 4754

(mod 5208)

Ebb®l, és a 1960 · 4 ≡ 24 · 32 · 52 (mod 5209) kongruenciából
60 + log19 4 ≡ 4 · log19 2 + 2 · log19 3 + 2 · log19 5 ≡
4 · 5088 + 2 · 3208 + 2 · 4754 ≡ 31008 ≡ 4968

(mod 5208)

az eredmény k = 4968.

2.4. Faktorbázis és a kiválasztás módszere

A denícióban azt mondtuk, hogy a t érték véletlenszer¶en választott, de érdemes
megvizsgálni, hogy hogyan változik a lefutási id® (lépésszámokban mérve), ha ehelyett egyesével lépegetünk végig az [1 . . . p − 1]-beli egész számokon, valamint azt,
hogy ha az algoritmus bemeneténél egy adott faktorbázis helyett egy nagyobb,
például a kétszerese szerepel.
Ennek megfelel®en egy partikuláris problémát négyféleképpen fogunk megoldani,

12

FEJEZET 2.

DISZKRÉT LOGARITMUS

egyszer a t véletlenszer¶en kerül kiválasztásra, egyszer pedig befutja az [1 . . . p−1]beli egészeket mindaddig, amíg meg nem lesz a megoldáshoz elegend® számú
egyenelet. Mindkét módszert alkalmazzuk egy kisebb és egy kétszer akkora számosságú faktorbázisra.
Legyen a probléma 47k ≡ 126 (mod 25219).

Els® eset: t véletlenszer¶ választása a B = {2, 3, 5, 7} faktorbázissal:
A következ® egyenletek adódtak:

4710828 ≡ 2 · 3 · 5≡ 3 ·58299

2≡ 2·3 ·5·7

11411

4

47

47
47

3

(mod 25219)

11107

≡ 3·5

(mod 25219)(mod 25219)(mod 25219)

ahol a baloldalon álló hatványkitev®k a véletlen t értékek.
A rendszer logaritmusát véve

10828 ≡ log47 2 + log47 3 + log47 511107 ≡ 3 · log47 3 + log47 5(mod 25218)(mod 25218)

8299 ≡ log47 2 + 2 · log47 3 + log47 5 + log47 7
11411 ≡ log47 3 + 4 · log47 5(mod 25218)(mod 25218)

adódik.
Az egyenletrendszert megoldva a faktorbázis elemeinek logaritmusai:
log47 2 ≡ 1139

(mod 25219)

log47 3 ≡ 709(mod 25219)

log47 5 ≡ 8980

(mod 25219)

log47 7 ≡ 21980(mod 25219)

A megoldás k = 24537.

Második eset: t véletlenszer¶ választása a B = {2, 3, 5, 7, 11, 13, 17, 19} fak-torbázissal:
A következ® egyenletek adódtak:

2.4.

13

FAKTORBÁZIS ÉS A KIVÁLASZTÁS MÓDSZERE

47630 ≡ 22 · 32 · 5 · 7 · 11
24286

47

3

3

2

≡ 2 ·3 ·7(mod 25219)

4718342 ≡ 22 · 3 · 5 · 13 · 19
14901

47

3

2

(mod 25219)

2≡ 2 ·5 ·7(mod 25219)(mod 25219)

4714017 ≡ 2 · 32 · 7 · 11 · 13 · 17
17147

47

4

≡ 2 · 3 · 7 · 11473445 ≡ 24 · 33 · 7
17009

47

(mod 25219)(mod 25219)(mod 25219)

2≡ 2 · 7 · 17

(mod 25219)

ahol a baloldalon álló hatványkitev®k a véletlen t értékek.
A rendszer logaritmusát véve
630 ≡ 2 · log47 2 + 2 · log47 3 + log47 5 + log47 7 + log47 1124286 ≡ 3 · log47 2 + 3 · log47 3 + 2 · log47 7(mod 25218)

18342 ≡ 2 · log47 2 + log47 3 + log47 5 + log47 13 + log47 19
14901 ≡ 3 · log47 2 + 2 · log47 5 + 2 · log47 7(mod 25218)(mod 25218)(mod 25218)

14017 ≡ log47 2 + 2 · log47 3 + log47 7 + log47 11 + log47 13 + log47 1717147 ≡ log47 2 + 4 · log47 3 + log47 7 + log47 113445 ≡ 4 · log47 2 + 3 · log47 3 + log47 717009 ≡ log47 2 + 2 · log47 7 + log47 17(mod 25218)(mod 25218)(mod 25218)(mod 25218)

adódik.
Az egyenletrendszert megoldva a faktorbázis elemeinek logaritmusai:
log47 2 ≡ 1139

(mod 25219)

log47 3 ≡ 709(mod 25219)

log47 5 ≡ 8980

(mod 25219)

log47 7 ≡ 21980(mod 25219)

log47 11 ≡ 16410(mod 25219)

log47 13 ≡ 23506(mod 25219)

log47 17 ≡ 22346(mod 25219)

log47 19 ≡ 8087

(mod 25219)

A megoldás itt is k = 24537.

Harmadik eset: t sorban való próbálgatása 1-t®l 25218-ig, a B = {2, 3, 5, 7}
faktorbázissal:

14

FEJEZET 2.

DISZKRÉT LOGARITMUS

A következ® egyenletek adódtak:
4728 ≡ 2 · 33 · 7
179

47

3

≡ 2 ·7(mod 25219)(mod 25219)

4712623 ≡ 2 · 52 · 72
47

12676

2

(mod 25219)

2≡ 2 ·3 ·5(mod 25219)

ahol a baloldalon álló hatványkitev®k a véletlen t értékek.
A rendszer logaritmusát véve
28 ≡ log47 2 + 3 · log47 3 + log47 7
179 ≡ 3 · log47 2 + log47 7(mod 25218)(mod 25218)

12623 ≡ log47 2 + 2 · log47 5 + 2 · log47 7(mod 25218)

12676 ≡ 2 · log47 2 + 2 · log47 3 + log47 5(mod 25218)

adódik.
Az egyenletrendszert megoldva a faktorbázis elemeinek logaritmusai nem változtak:
log47 2 ≡ 1139

(mod 25219)

log47 3 ≡ 709(mod 25219)

log47 5 ≡ 8980

(mod 25219)

log47 7 ≡ 21980(mod 25219)

Az eredmény természetesen ismét k = 24537.

Negyedik eset: t sorban való próbálgatása 1-t®l 25218-ig, a B = {2, 3, 5, 7, 11, 13, 17, 19}
faktorbázissal:
A következ® egyenletek adódtak:

4710 ≡ 53 · 13
≡ 2·3 ·7

(mod 25219)

136≡ 2 · 3 · 13

(mod 25219)

153

6

47
47
47

12623

47

3

3

≡ 2 · 3 · 112

≡ 2·5 ·74712632 ≡ 73 · 17
12643

47

(mod 25219)

28

4≡ 2 · 192

(mod 25219)(mod 25219)(mod 25219)(mod 25219)

4712676 ≡ 22 · 32 · 5(mod 25219)

2.4.

15

FAKTORBÁZIS ÉS A KIVÁLASZTÁS MÓDSZERE

ahol a baloldalon álló hatványkitev®k a véletlen t értékek.
A rendszer logaritmusát véve
10 ≡ 3 · log47 5 + log47 13(mod 25218)

28 ≡ log47 2 + 3 · log47 3 + log47 7
136 ≡ log47 2 + log47 3 + log47 13(mod 25218)(mod 25218)

153 ≡ 6 · log47 2 + 3 · log47 3 + log47 11(mod 25218)

12623 ≡ log47 2 + 2 · log47 5 + 2 · log47 7(mod 25218)

12632 ≡ 3 · log47 7 + log47 17(mod 25218)

12643 ≡ 4 · log47 2 + log47 19(mod 25218)

12676 ≡ 2 · log47 2 + 2 · log47 3 + log47 5(mod 25218)

adódik.
Az egyenletrendszert megoldva a faktorbázis elemeinek logaritmusai:
log47 2 ≡ 1139

(mod 25219)

log47 3 ≡ 709(mod 25219)

log47 5 ≡ 8980

(mod 25219)

log47 7 ≡ 21980(mod 25219)

log47 11 ≡ 16410(mod 25219)

log47 13 ≡ 23506(mod 25219)

log47 17 ≡ 22346(mod 25219)

log47 19 ≡ 8087

(mod 25219)

A megoldás itt is k = 24537.

3. Magma kód

Itt a példák számításához használt programcsomag, a MAGMA [2] ingyenes, interneten elérhet® változatához íródott kódok találhatóak.
Az alább látható lépeget®s módszer kódjánál gyelembe kell venni azt, hogy az
alguritmus mindenféleképpen n × n-es együtthatómátrixot keres a faktorbázis elemeinek a logaritmusának megtalálásához (ahol n a faktorbázis számossága), pedig
lehetséges, hogy az kevesebb egyenletb®l is nyerhet® lenne.
IK:=function(a,b,p,FB)
FBsub:={k: k in Subsets(SequenceToSet(FB))|#k gt 0};
fac:=Factorization(p-1);
facB:=[t[1]^t[2]: t in fac];kitevok:={};
Lm1:=(p-1) div 2;
s:=1;
logMatrix:=ZeroMatrix(Integers(p-1),#FB,#FB);
logVector:=Vector(Integers(p-1),[0: l in [1..#FB]]);
k:=1;
while not s eq #FB+1 do
if not k in kitevok then
pd:=PrimeDivisors(a^k mod p);
pdm:=PrimeDivisors((-a^k) mod p);
if SequenceToSet(pd) in FBsub thenkitevo_vektor:=Vector(Integers(p-1),[Valuation(a^k mod p,FB[l]):l in [1..#FB]]);
logmatrix:=logMatrix;
logmatrix[s]:=kitevo_vektor;
if &and[Rank(ChangeRing(logmatrix,GF(t))) eq s: t in facB] thenlogVector[s]:=k;logMatrix:=logmatrix;
s:=s+1;
end if;end if;if SequenceToSet(pdm) in FBsub and s lt #FB then

17

18

FEJEZET 3.

MAGMA KÓDkitevo_vektor:=Vector(Integers(p-1),[Valuation(-a^k mod p,FB[l]):l in [1..#FB]]);
logmatrix:=logMatrix;
logmatrix[s]:=kitevo_vektor;
if &and[Rank(ChangeRing(logmatrix,GF(t))) eq s: t in facB] thenlogVector[s]:=k-Lm1;
logMatrix:=logmatrix;
s:=s+1;
end if;end if;kitevok:=kitevok join {k};end if;k:=k+1;end while;
time logSol:=Solution(Transpose(logMatrix),logVector);
kitevok2:={};
nyer:=false;
k:=1;
while not nyer do
if not k in kitevok thenpdb:=PrimeDivisors((a^k*b) mod p);
if SequenceToSet(pdb) in FBsub thenkitevo_vektor2:=Vector(Integers(p-1),[Valuation((a^k*b) mod p,
FB[l]): l in [1..#FB]]);
logeredmeny:=Integers(p-1)!((&+[kitevo_vektor2[t]*logSol[t]:t in [1..#FB]])-k);nyer:=true;
print k;end if;kitevok2:=kitevok2 join {k};end if;k:=k+1;end while;
return logMatrix,logVector,logeredmeny;end function;

A másik, véletlenszer¶en keres® algoritmus kódja:IK:=function(a,b,p,FB)
FBsub:={k: k in Subsets(SequenceToSet(FB))|#k gt 0};

19
fac:=Factorization(p-1);
facB:=[t[1]^t[2]: t in fac];kitevok:={};
Lm1:=(p-1) div 2;
s:=1;
logMatrix:=ZeroMatrix(Integers(p-1),#FB,#FB);
logVector:=Vector(Integers(p-1),[0: l in [1..#FB]]);
while not s eq #FB+1 do
k:=Random([1..p-1]);
if not k in kitevok then
pd:=PrimeDivisors(a^k mod p);
pdm:=PrimeDivisors((-a^k) mod p);
if SequenceToSet(pd) in FBsub thenkitevo_vektor:=Vector(Integers(p-1),[Valuation(a^k mod p,FB[l]):l in [1..#FB]]);
logmatrix:=logMatrix;
logmatrix[s]:=kitevo_vektor;
if &and[Rank(ChangeRing(logmatrix,GF(t))) eq s: t in facB] thenlogVector[s]:=k;logMatrix:=logmatrix;
s:=s+1;
end if;end if;if SequenceToSet(pdm) in FBsub and s lt #FB thenkitevo_vektor:=Vector(Integers(p-1),[Valuation(-a^k mod p,FB[l]):l in [1..#FB]]);
logmatrix:=logMatrix;
logmatrix[s]:=kitevo_vektor;
if &and[Rank(ChangeRing(logmatrix,GF(t))) eq s: t in facB] thenlogVector[s]:=k-Lm1;
logMatrix:=logmatrix;
s:=s+1;
end if;end if;kitevok:=kitevok join {k};end if;end while;
time logSol:=Solution(Transpose(logMatrix),logVector);
kitevok2:={};
nyer:=false;

20

FEJEZET 3.

MAGMA KÓDwhile not nyer do
k:=Random([1..p-1]);
if not k in kitevok thenpdb:=PrimeDivisors((a^k*b) mod p);
if SequenceToSet(pdb) in FBsub thenkitevo_vektor2:=Vector(Integers(p-1),[Valuation((a^k*b) mod p,
FB[l]): l in [1..#FB]]);
logeredmeny:=Integers(p-1)!((&+[kitevo_vektor2[t]*logSol[t]:t in [1..#FB]])-k);nyer:=true;
print k;end if;kitevok2:=kitevok2 join {k};end if;end while;
return logMatrix,logVector,logeredmeny;end function;

Irodalomjegyzék[1] B. Bódi. Algebra. Kossuth Lajos Tudományegyetem Természettudományi Kar, 1997.
[2] W. Bosma, J. Cannon, and C. Playoust. The Magma algebra system. I. The user
language. J. Symbolic Comput., 24(3-4):235265, 1997. Computational algebra andnumber theory (London, 1993).
[3] R. Ruprai.
Improvements in the index-calculus algorithm for solving the discrete logarithm problem over Fp .
2007.
Elérhet®:http://www.isg.rhul.ac.uk/ prai175/ISGStudentSem07/IndexCalculus.pdf.

21