Debreceni Egyetem
Természettudományi és Technológiai Kar
Matematikai Intézet
Diplomamunka

Diszkrét logaritmus problémasandpile csoportbankészı́tette:

Dsupin Krisztiántémavezető: Dr. Tengely Szabolcs
Debrecen, 2020

Tartalomjegyzék1.

Bevezetés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

2.

Sandpile modell . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

2.1.

Alapfogalmak . . . . . . . . . . . . . . . . . . . . . . . . . .

4

2.2.

Monodrómia párosı́tás . . . . . . . . . . . . . . . . . . . . .

9

2.3.

Diszkrét logaritmus probléma gráfok jacobianján . . . . . . .

10

2.4.

Algoritmus. . . . . . . . . . . . . . . . . . . . . . . . . . .

10Módosı́tott kerékgráf . . . . . . . . . . . . . . . . . . . . . . . .

12

3.1.

. . . . . .

12Négyzetes körgráf . . . . . . . . . . . . . . . . . . . . . . . . . .

18

4.1.

Cn2 -beli diszkrét logaritmus probléma megoldása . . . . . . .

19

5.

Általánosı́tott inverz . . . . . . . . . . . . . . . . . . . . . . . . .

26

6.

Függelék . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

3.

4.

W n -beli diszkrét logaritmus probléma megoldása1

Köszönetnyilvánı́tás
Ezúton szeretnék köszönetet mondani témavezetőmnek, Dr. Tengely Szabolcsnak,
aki nélkülözhetetlen tanácsaival, szakértelmével és folyamatos segı́tségével nagyban hozzájárult a diplomamunkám létrejöttéhez. Köszönettel tartozom továbbá
családomnak és barátaimnak a támogatásukért, amivel segı́tették, hogy ez a dolgozat elkészülhessen.

21. Bevezetés
Körülbelül 30 éve, 1987-ben jelent meg Bak, Tang és Wiesenfeld forradalmi cikke, melyben bemutatták a rácsmodellt, amit ők ”self-organised criticality” névvel
illettek [1]-ben. Megjelenése óta a modell erősen vizsgált témakörré vált mind
a matematikai, mind a fizikai irodalmakban. A modellben apró hatások komplex rendszerek felbukkanásához vezethetnek, mely a rendszert egy stacionáriusállapot felé mozdı́tja. Számos modellt indı́tott útjának a szerzők cikke, példáulOlami–Feder–Christensen modell [2], mely földrengések modellezését szolgálja, vagy
forest-fire modell [3], amit erdőtüzek szimulálása motivált, azonban járványok
vizsgálatakor is hasznosı́tható [4]. Ezenfelül az agykutatás területén is alkalmazott[5], az agyi aktivitások leı́rására. A teljesség igénye nélkül alkalmazott továbbá
biológiai, társadalmi területeken, és tőzsdei fluktuációk elemzésekor is.
Egy megfelelő reprezentációs csoport keresése a diszkrét logaritmus problémaszámára a mai napig egy népszerű problémakör a kriptográfiában. Az elliptikusgörbék egyre széleskörűbb használata kitűnő példa arra, hogy a diszkrét logaritmus probléma alkalmas hatékony kriptográfiai protokollok megvalósı́tására, ugyanis
az RSA mellett napjaink egyik legelterjedtebb kriptorendszere, melyet használnak
kulcscsere protokollok, digitális aláı́rások és pszeudorandom számok generálásárais.
Általánosan a diszkrét logaritmus probléma az alábbi módon fogalmazható meg.
Amennyiben G multiplikatı́v csoport, g, h P G, keresett olyan x, melyre g x “ h.
Ha H additı́v csoport P, Q P H, akkor keresett y, melyre yP “ Q. A probléma megoldása megfelelő csoportok esetén számı́tásilag nehéz, ı́gy alkalmasak kriptográfiai
protokollok felhasználására. Whitfield Diffie és Martin Hellman 1976-ban javasoltákkulcscsere megvalósı́tására, majd Taher ElGamal 1985-ben nyilvános kulcsú kriptorendszert mutatott be, melyek mind a diszkrét logaritmus problémán alapulnak.
Emellett egyéb érdekesebb nemkommutatı́v csoportokban is definiáltak diszkrét logaritmus problémát, például [6]-ban. Azonban mindennapi használatban főleg avéges testek feletti elliptikus görbék váltak elterjedté.
A két talán elsőre idegennek tűnő témakört kapcsolta össze Biggs [7]-ben. Kriptográfiai használatra javasolt bizonyos gráf családoknak sandpile modell segı́tségével
értelmezhető csoportját. Azonban egymástól függetlenül [8]-ban és [9]-ben is megmutatták ennek hatékony megoldhatóságát. A diplomamunkámban két gráfcsaládfelett értelmezett diszkrét logaritmus probléma kerül bemutatásra, azok megoldhatóságával együtt.

3

2. Sandpile modell
2.1. Alapfogalmak
2.1. Definı́ció. Legyen G “ pV, Eq multigráf, ahol V “ tv1 , . . . , vn u a csúcsok
halmaza, valamint e “ pu, vq P E Ď V ˆ V az élek halmaza, továbbá, ha u “ v,ekkor az e “ pu, vq élt hurokélnek nevezzük. Ezek megengedettek, de nem tesznek
hozzá sokat elméleti szempontból, ı́gy feltesszük, hogy G hurokélmentes.
Legyen w : V ˆ V Ñ N egy súlyfüggvény, ahol wpu, vq ą 0 pontosan akkor,
ha pu, vq P E.
Legyen u, v P V , ekkor v-t elérhetőnek nevezzük u-ból, ha létezik éleknek olyan sorozata, amely u-ban kezdődik és v-ben végződik. Egy csúcsot globálisan elérhetőnek
vagy nyelőnek nevezünk, ha G minden csúcsából elérhető. A következőkben feltesszük, hogy G-nek létezik legalább egy globálisan elérhető csúcsa.
Egy v P V csúcs kifoka alatt azt a d` pvq nemnegatı́v egészet értjük, ami a v-bőlinduló élek súlyainak összege, befoka alatt a d´ pvq-vel jelölt nemnegatı́v egészet,
ami a v-be érkező élek súlyainak összege.
2.2. Definı́ció. A pV, E, sq rendezett hármast sandpile gráfnak nevezzük, ha pV, Eq
irányı́tott multigráf, s P V pedig globálisan elérhető csúcs.
Továbbá ha d´ psq “ 0, akkor abszolút nyelőnek nevezzük. Jelölje a nemnyelő
csúcsokat Ṽ :“ V ztsu. Egy sandpile gráf nyelő csúcsának abszolút nyelőnek kelllennie, de a témakörben a legtöbb esetben érdemi változás nélkül eltávolı́thatjuk anyelőből kiinduló éleket. Továbbá egy G “ pV, E, sq sandpile gráfra gyakran csak
pV, Eq gráfként hivatkozunk.
2.1. Megjegyzés. Egy sandpile gráfra szemléletesen tekinthetünk úgy, mintha
homokszemeket helyeznénk egy gráf csúcsaira. Azt szeretnénk modellezni, hogy
hogyan viselkedik a gráf által alkotott rendszer, ha folyamatosan új homokszemeket pakolunk a csúcsaira. Ahogy a homokvárak is, amint túl sok szem kerül egy
adott pontra, akkor az ledől, és homokszemek további pontok felé mozdulnak. Egy
sandpile gráf esetében annak teherbı́rását a kifoka határozza meg, a ledőlés utánihomokszemek helyzetét pedig a ledöntött éllel szomszéd csúcsok adják.
!ÿ
)
2.3. Definı́ció. Legyen X véges halmaz, ekkor ZX “ax x | ax P Z, @x P X
xPX

egy szabad Abel-csoport X-n. Megszorı́tva nemnegatı́v együtthatókra hasonlóanadódik NX.

4

2.4. Definı́ció. Legyen G sandpile gráf v1 , . . . , vn csúcsokkal.
G Laplace-leképezése alatt a ∆ : ZV Ñ ZV csúcson értelmezett leképezést értjük,ahol:
ÿ
∆pvq :“ d` pvqv ´wpv, uqu.
uPV˜ : ZṼ Ñ ZṼ nemnyelő csúcsokon értelmezett
G redukált Laplace-leképezése alatt ∆leképezést értünk, ahol:ÿ
˜∆pvq:“ d` pvqv ´wpv, uqu.
uPṼLegyen D “ diagpd´ pv1 q, . . . , d` pv1 qq diagonális mátrix, A a G szomszédsági mátrixa,
vagyis Aij “ wpvi , vj q. Ekkor G Laplace-mátrixa L “ D ´ A.
Továbbá egy G gráf ∆ Laplace-leképezése megegyezik L transzponáltjával. A
Laplace-leképzés és Laplace-mátrix sok esetben megkönnyı́ti a számolást a sandpile
csoportban, például generátor keresésben vagy rend kiszámolásban.
2.1. Tétel (Kirchoff). Egy G gráf feszı́tő fáinak száma megegyezik tetszőleges
redukált Laplace-mátrixának determinánsával.
2.5. Definı́ció. Egy G feletti konfiguráció alatt egy c : V Ñ Z függvényt ÿértünk,
˚
amire cpvq ě 0 minden v P V esetén, továbbá cpsq “ ´
cpvq.
vPṼ

Jelölésben c “ pc1 , . . . , cn q.

2.6. Definı́ció. Egy c konfigurációt stabilnak nevezünk egy v P Ṽ csúcsban, ha
cpvq ď d´ pvq. Ellenkező esetben c instabil.
Egy konfigurációt stabilnak nevezünk, ha minden csúcsban stabil.
2.7. Definı́ció. Amennyiben c instabil egy v csúcsban, ekkor v ledőlhet, ami egy c̃konfigurációba jutását jelenti, ahol redukáljuk cpvq értékét d´ pvq-vel, és v minden
w szomszédja esetén növeljük cpwq értékét egyel. Vagyis:$´’&cpuq ´ d puq, ha u “ v,c̃pvq “ cpuq ` 1,
ha u és v szomszédosak,
’
%
cpvq,
egyéb esetben.
Ha c instabil v csúcsban, akkor v ledöntését megengedettnek nevezzük.
2.2. Megjegyzés. Egy c konfigurációra alkalmazva egy megengedett ledöntési sorozat eredményeképp létrejövő konfiguráció leı́rhatóÿ˜c̃ “ c ´ d´ pvqv `wpu, vqu “ c ´ ∆v.
uPṼ

52.8. Definı́ció. Egy v1 , . . . , vk nem nyelő csúcsok sorozata megengedett ledöntésisorozat c konfigurációra nézve, amennyiben v1 megengedett, továbbá v1 , . . . , vi´1
ledöntéséből keletkező konfiguráció következtében vi ledöntése is megengedett.
Egy c konfigurációra alkalmazva egy megengedett ledöntési sorozat eredményeképp
˜létrejövő konfiguráció leı́rható c̃ “ c ´ ∆σ,ahol σ P ZṼ , σv pedig a v csúcsσ
˜előfordulásának száma a sorozatban. Ez jelölésben c ÝÑ c ´ ∆σ.
2.2. Tétel. Legyen c egy sandpile konfiguráció.
1. Ekkor létezik c̃ stabil konfiguráció, amire c Ñ c̃.
2. Tegyük fel, hogy c Ñ c̃ egy σ ledöntési vektorral, és c Ñ c̃1 egy σ 1 . Ha c̃stabil, akkor σ 1 ě σ. Ha c̃ és c̃1 is stabil, akkor c̃ “ c̃1 .
2.9. Definı́ció. Legyen c egy G feletti konfiguráció, ekkor c stabilizálása egy
egyértelmű c̃ stabil konfiguráció, amelyre c Ñ c̃, mely jelölésben c˝ .
2.10. Definı́ció. Jelölje M a nemnegatı́v, stabil konfigurációkat G felett. Ekkor
M kommutatı́v monoid a stabilizáló összeadásra nézve, vagyis
a ˚ b :“ pa ` bq˝ .
A stabilizáló összeadás NṼ -beli összeadás, amit stabilizálás követ. Az egység anulla konfiguráció.
2.11. Definı́ció. Egy c konfiguráció elérhető, ha minden a konfiguráció eseténlétezik b konfiguráció, hogy a ` b Ñ c, továbbá visszatérő, ha nemnegatı́v, elérhetőés stabil.
2.12. Definı́ció. A G feletti maximálisan stabil konfiguráció alatt az alábbit értjük:ÿcmax “pd` pvq ´ 1qv.
vPṼ

2.1. Állı́tás. Egy c konfiguráció visszatérő pontosan akkor, ha létezik olyan a ě 0
konfiguráció, hogy c “ a ˚ cmax .
2.3. Tétel. A G feletti visszatérő konfigurációk csoportot alkotnak a stabilizáló
összeadásra nézve.
2.13. Definı́ció. A G feletti visszatérő konfigurációk csoportját sandpile csoportnak nevezzük és jelölése SpGq.
2.3. Megjegyzés. 2.1 miatt egy sandpile csoport elemeit úgy is megkaphatjuk, haszisztematikusan homokszemeket adunk a cmax konfigurációhoz, majd stabilizálunk.

62.4. Megjegyzés. Szemléletesen egy konfiguráció egy a gráf minden csúcsábanadott homokszemek listája. Egy ilyen konfigurációt stabilnak mondunk, ha minden csúcsban a homokszemek száma kevesebb, mint a csúcs teherbı́rása. Ha instabil konfigurációhoz jutunk, a rendszer stabilizálja önmagát és ledönti az instabil csúcsokat. Egy instabil csúcsból annak stabilizálása során minden szomszédos
csúcsba átkerül egy homokszem, ı́gy az eredeti csúcsban a kifok mértékével csökken,
a szomszédos csúcsokban egyel-egyel nő a homokszemek száma. A rendszer stabilizálása addig tart, ameddig minden csúcs nem stabilizálódik, amely véges soklépésben megtörténik, mivel létezik nyelő csúcs, ami a rendszerben felhalmozódottinstabilitást okozó homokszemeket elnyeli.
2.14. Definı́ció. Legyen L Ă ZV Laplace-rács a ∆ képe, L̃ Ă ZṼ redukált
˜ képe. Ekkor G kritikus csoportja
Laplace-rács a ∆CpGq “ ZṼ {L̃.
2.4. Tétel. Létezik SpGq és CpGq között izomorfizmus az alábbi módon:
SpGq

Ñ

CpGq

c

ÞÑ

c ` L̃.

Továbbá az SpGq sandpile csoport η egységeleme az alábbi módon számolható:η “ ppcmax ´ p2cmax q˝ q ` cmax q˝ .
2.1. Példa. Példaként tekintsük az alábbi G gráfot:• V pGq “ tv1 , v2 , v3 , , v4 , su
• EpGq “ tpv1 , v2 , 1q, pv1 , v3 , 1q, pv1 , v4 , 1q, pv2 , s, 1q, pv3 , v4 , 1q, pv4 , s, 1quahol pvi , vj , wq jelöli a vi és vj közötti w súlyú élt.

7

Az ı́gy adódó gráf nyelő nélküli kifokai rendre p3, 2, 2, 3q, amik meghatározzák egy
adott konfiguráció stabilitását.
Vegyük például a c “ p4, 0, 1, 0q konfigurációt, amely instabil a v1 csúcsban, mivel a konfiguráció v1 -re eső eleme nagyobb, mint annak kifoka. Stabilizálásához
v1 csúcsot ledöntve egy-egy homokszem áramlik a szomszédaiba, azaz v2 , v3 , v4
csúcsokba. Így a p1, 1, 2, 1q konfigurációhoz jutunk. Ekkor azonban v3 válik instabillá, amit ledöntve a már stabil p2, 1, 0, 2q konfigurációhoz jutunk.
Összefoglalva a stabilizálást: p4, 0, 1, 0q Ñ p1, 1, 2, 1q Ñ p2, 1, 0, 2q.
A konfigurációk között akadnak olyanok, melyek érhetők önmagukból indulva legális
operációsorozat végrehajtásával. Ezek a visszatérő konfigurációk, melyek SpGq csoportot alkotják.
Az SpGq csoport elemszáma megegyezik a feszı́tő fáinak számával 2.1 miatt, melyet az L redukált Laplace-mátrixának determinánsából kapunk. Az L-ből a nyelő
csúcshoz tartozó sort és oszlopot elhagyva kapjuk:¨˛
3 ´1 ´1 ´1
˚ ´1
2
0
0 ‹
‹.
L“˚
˝ ´1
0
2 ´1 ‚´1
0 ´1
3Továbbá ekkor detpLq “ 11, ı́gy a csoport elemszáma is 11.
Mivel cmax “ p2, 1, 1, 2q, ı́gy 2.4 felhasználásával a csoport egységeleme a következő:η “ ppcmax ´ p2cmax q˝ q ` cmax q˝“ ppp2, 1, 1, 2q ´ p4, 2, 2, 4q˝ q ` p2, 1, 1, 2qq˝
“ ppp1, 1, 1, 2q ´ p1, 1, 1, 2qq ` p2, 1, 1, 2qq˝
“ ppp1, 1, 1, 2q ´ p1, 1, 1, 2qq ` p2, 1, 1, 2qq˝
“ ppp1, 1, 1, 2q ´ p1, 1, 1, 2qq ` p2, 1, 1, 2qq˝
“ pp3, 1, 1, 2qq˝
“ p2, 1, 1, 0q
Továbbá visszatérő konfigurációk az alábbiak:
c1 “ p2, 1, 1, 2q

c2 “ p2, 0, 1, 2)

c3 “ p1, 1, 1, 2q

c4 “ p1, 0, 1, 2q

c5 “ p0, 1, 1, 2q

c6 “ p1, 1, 0, 2q

c7 “ p2, 0, 0, 2q

c8 “ p2, 1, 0, 2q

c9 “ p2, 1, 0, 1q

c10 “ p2, 1, 1, 1q

c11 “ p2, 1, 1, 0q

8SpGq Cayley-táblázata az alábbi:
ˇ
ˇ
ˇ
ˇ
c
c
c
c
c
c
c
c
c
c
c
1
2
3
4
5
6
7
8
9
10
11
ˇ
ˇ
ˇ c1 c3 c4 c5 c9 c8 c10 c11 c6 c7 c2 c1 ˇˇˇ
ˇ c2 c4 c5 c9 c8 c7 c1 c10 c11 c6 c3 c2 ˇˇˇˇ c3 c5 c9 c8 c7 c6 c2 c1 c10 c11 c4 c3 ˇˇˇˇ c4 c9 c8 c7 c6 c11 c3 c2 c1 c10 c5 c4 ˇˇˇˇ c5 c8 c7 c6 c11 c10 c4 c3 c2 c1 c9 c5 ˇˇˇ
ˇ c6 c10 c1 c2 c3 c4 c7 c8 c9 c5 c11 c6 ˇˇˇ
ˇ c7 c11 c10 c1 c2 c3 c8 c9 c5 c4 c6 c7 ˇˇˇ
ˇ c8 c6 c11 c10 c1 c2 c9 c5 c4 c3 c7 c8 ˇˇˇˇ c9 c7 c6 c11 c10 c1 c5 c4 c3 c2 c8 c9 ˇˇˇˇ c10 c2 c3 c4 c5 c9 c11 c6 c7 c8 c1 c10 ˇˇˇˇ c11 c1 c2 c3 c4 c5 c6 c7 c8 c9 c10 c11 ˇ

2.2. Monodrómia párosı́tás
A továbbiakban célunk egy a csoporton értelmezett diszkrét logaritmus problémátmegoldó algoritmus bemutatása, melyet Shokrieh [9]-ben mutatott be. A sandpile
csoportok megközelı́thetőek görbeelméleti szemszögből is, melyet a mi esetünkben
az elliptikus görbéken ismert MOV támadás alapjául szolgáló bilineáris párosı́tás
motivál.
2.15. Definı́ció. Egy G gráf divizorán az alábbi V pGq által generált szabad Ábelcsoportot értjük:ÿ
DivpGq “ t av pvq | av P Zu.
vPVG divizorainak elemeire gondolhatunk úgy, mint egyész együtthatós lineáris kombináció a gráfok csúcsain. Továbbá DivpGq elemeit divizornak nevezzük. Egy D
divizor esetén egy v csúcs együtthatóját jelölje Dpvq.
Legyen MpGq “ HompV, Zq Abel-csoport, mely minden egész értékű függvényt
tartalmaz, amik a gráf csúcsain értelmezettek.
ÿLegyen f P MpGq, valamint jelölje ordv pf q “
pf puq ´ f pvqq, ekkor legyenu,vPE

divpf q “ÿ

ordv pf qv.

vPV

Tekintsük deg : DivpGq Ñ Z csoport homomorfizmust az alábbiak szerint:ÿ
def pDq “
Dpvq.
vPV

Definiálja PrinpGq “ tdivpf q P DivpGq | f P MpGqu a fő divizorok csoportját.
9

Jelölje Div 0 pGq a homomorfizmus magját, vagyis ami tartalmazza a nulla fokú
divizorokat.
G Jacobianja alatt a következőt értjük:
JacpGq “ Div 0 pGqzPrinpGq.
2.2. Állı́tás. Legyenek D1 , D2 P Div 0 pGq, továbbá m1 , m2 egészek, hogy
m1 D1 “ divpf1 q és m2 D2 “ divpf2 q, ekkor megmutatható, hogy
1 ÿ
1 ÿ
D1 pvqf2 pvq “D2 pvqf1 pvq.
m2 vPV
m1 vPV
2.16. Definı́ció. Jelölje x. , .y : Div 0 pGq ˆ Div 0 pGq Ñ Q:
xD1 , D2 y “

1 ÿ
D1 pvqf2 pvq.
m2 vPV

Ekkor a párosı́tás szimmetrikus és bilineáris.
2.17. Definı́ció. Legyen A mátrix, ekkor minden P mátrixot, melyre AP A “ A
teljesül, az A mátrix pszeudoinverzének vagy általánosı́tott inverzének nevezzük.
2.2. Példa. Legyen J az n ˆ n-es csak egyesekből álló mátrix. Ekkor Q mátrix
esetén Q` n1 J reguláris, továbbá Q` “ pQ` n1 Jq´1 ´ n1 J mátrix a Q pszeudoinverze.
Sőt ezt Q Moore-Penrose pszeudoinverzének is nevezzük, mivel ellenőrizhető, hogy
QQ` “ Q` Q “ I ´ n1 J és Q` QQ` “ Q` is teljesül.
2.5. Tétel. Legyen P tetszőleges pszeudoinverze L Laplace-mátrixnak, ekkor amonodrómia párosı́tás a következő módon adott:
xD1 , D2 y “ rD1 sT P rD2 s pmod Zq.

2.3. Diszkrét logaritmus probléma gráfok jacobianjánTekintsünk egy G gráfot, ahol Jac(G) ciklikus csoport, ekkor a csoport felett megadható diszkrét logaritmus problémát szeretnénk megoldani a monodrómia párosı́tássegı́tségével. Továbbá tegyük fel, hogy Jac(G) egy generátora is ismert.

2.4. Algoritmus
Bemenet: D1 , D2 P Div 0 pGq, ahol D2 “ x ¨ D1 teljesül Jac(G)-ben
Kimenet: x pmod ordpD1 qq

10

Algoritmus:
1. Számoljuk ki xD1 , gy “ r1 ` Z és xD2 , gy “ r2 ` Z a 2.5 formula segı́tségével.
2. Oldjuk meg a r2 “ r1 x ` y diofantikus egyenletet x pmod ordpDqq értékmeghatározásához.

Algoritmus elemzése
Mivel a monodrómia párosı́tás bilineáris, ezért: xD2 , gy “ xxD, gy, vagyis r2 “
r1 x QzZ-ben. Ahhoz, hogy belássuk, hogy a diofantikus egyenlet megoldása pont
xpmod ordpDqq értéket adja, tekintsük az alábbi lemmát.
2.1. Lemma. Legyen g generátora Jac(G) ciklikus csoportban. Legyen h tetszőleges
eleme Jac(G)-nek. Ha xh, gy “ ab ` Z, ahol a, b P Z, lnkopa, bq “ 1, ekkor h rendje
Jac(G)-ben b.
Bizonyı́tás. Legyen h rendje Jac(G)-ben γ. A monodrómia párosı́tás bilinearitásamiatt:
γa` Z “ γxh, gy “ xγ ¨ h, gy “ x0, gy “ Z.
b
Vagyis emiatt b|γ.
A másik oldalrólxb ¨ h, gy “ bxh, gy “ a ` Z “ Z.
Mivel Jac(G) ciklikus és a monodrómia párosı́tás bilineáris, minden Jac(Gq-belielem triviálisan párosı́tható b ¨ h-val. A monodrómia párosı́tás nem-elfajultságamiatt b ¨ h “ 0, ami miatt γ|b.
Vagyis γ “ b.
Mivel D2 “ xD1 , ezért D2 rendje osztja D1 rendjét, ami 2.1 miatt r “ ab pa, b P
Z, lnkopa, bq “ 1q, b pedig D rendje Jac(G). Ekkor b-vel szorozva r2 “ r1 x `y-ból kapjuk ax ` by “ c egyenletet valamely c egészre. Ekkor az adott ax `by “ c plnkopa, bq “ 1q lineáris diofantikus egyenletnek létezik megoldása, és xmeghatározott modulo b.

11

3. Módosı́tott kerékgráfLegyen n pozitı́v egész, W2n`1 pedig a 2n`1 csúcsú kerékgráf, ami áll egy v1 , . . . , v2n`1
csúcsokból álló ”abroncs”, és w ”középpont” részből. Ekkor w szomszédos vi vel minden 1 ď i ď 2n ` 1 esetén. Jelölje W n azt a gráfot, amit a következő
módosı́tásokkal kapunk W2n`1 -ből: adjunk egy új v2n`2 csúcsot a gráfhoz, amiketkössön él v1 és v2n`1 csúcsokhoz, továbbá töröljük a v1 és v2n`1 csúcsokat összekötőélt.

Jelölje W n csúcsainak halmazát V , éleinek halmazát E. Valamint legyen V ˚ “V ztqu, ami szemléletesen a módosı́tott kerékgráf abroncsa.
Ekkor a G “ pV, E, wq sandpile gráfból keletkezett SpGq-n definiálható diszkrétlogaritmus probléma. Vagyis adott g generátor SpGq-n, valamint b, c P SpGq konfiguráció, ekkor keresett olyan x P Z, hogy c2 “ px ¨ c1 q˝ .

3.1. W n -beli diszkrét logaritmus probléma megoldása
Ennek megoldása a 2.4 fejezetben leı́rt módon történik. A gráf ismeretében, mely
csak egy n paramétertől függ. Ekkor kiszámı́tható az L “ D ´ A Laplace-mátrix,
valamint az ahhoz tartozó P pszeudoinverz például, 2.2 alapján. Kiszámı́tható
továbbá SpGq generátor eleme, majd a generátor
elemhez tartozó divizor, ami
ř2n`2g “ pg1 , . . . , g2n`2 q konfiguráció esetén: Dg “ p´ i“1 gi , g1 , . . . , g2n`2 q vektorralleı́rható. Hasonlóan kiszámı́tjuk a c1 és c2 konfigurációkhoz tartozó Dc1 , Dc2 divizorokat is. Majd az algoritmus 1 pontja szerint, felhasználva 2.5 állı́tást kiszámoljuk
Dc1 ¨ P ¨ Dg és Dc2 ¨ P ¨ Dg , amelyekből keletkező diofantikus egyenletet megoldva
adódik a megoldás.
3.1. Példa. Tekintsük példaként az 5 csúcsú módosı́tott kerékgráfot. Legyenek
c1 “ p2, 1, 1, 1q és c2 “ p1, 0, 2, 1q tetszőlegesen választott konfigurációk.

12

Ekkor a gráf Laplace-mátrixa:˛
3 ´1 ´1 ´1
0
˚ ´1
3 ´1
0 ´1 ‹˚‹
3 ´1
0 ‹L“D´A“˚‹.
˚ ´1 ´1
˝ ´1
0 ´1
3 ´1 ‚
0 ´1
0 ´1
2
¨

Pszeudoinverze:

¨

47
200
˚ ´1
25
˚
3
´
P “˚
˚ 200
˝ ´1
25
7
´ 50

1
3
´ 25
´ 200
17
1
´ 25
75
1
47
´ 25
200
8
1
´ 75 ´ 25
1
7
´ 25
´ 50

˛
1
7
´ 25
´ 50
8
1 ‹
´ 75
´ 25
‹
1
7 ‹
´ 25
´ 50
‹.
17
1 ‚
´
75
25
1
9
´ 25
25

Tekintve a sandpile csoportot, a generátor elem a g “ p2, 1, 1, 0q konfiguráció,
amelyből képzett divizor Dg “ p´4, 2, 1, 1, 0q.
Majd kiszámolva Dc1 “ p´5, 2, 1, 1, 1q, Dc2 “ p´4, 1, 0, 2, 1q értékek adódnak.
Továbbá tekintsük a

¨

1
3
´ 25
´ 200
17
1
´ 25
75
1
47
´ 25
200
8
1
´ 75 ´ 25
1
7
´ 25
´ 50

˛ ¨
˛
1
7
´4
´ 25
´ 50
8
1 ‹ ˚
‹
´ 75
´ 25
‹ ˚ 2 ‹ 83
1
7 ‹ ˚
´ 25 ´ 50 ‹ ¨ ˚ 1 ‹‹ “ 12
1 ‚ ˝
17
´ 25
1 ‚
75
1
9
´ 25
0
25

¨

1
3
´ 25
´ 200
17
1
´ 25
75
1
47
´ 25
200
8
1
´ 75
´ 25
1
7
´ 25 ´ 50

˛ ¨
˛
1
7
´ 25
´ 50
´4
8
1 ‹ ˚
‹
´ 75
´ 25
‹ ˚ 2 ‹ 16
1
7 ‹ ˚
´ 25 ´ 50 ‹ ¨ ˚ 1 ‹
‹“ 3
17
1 ‚ ˝
´ 25
1 ‚
75
1
9
´ 25
0
25

47
200
˚ ´1
25
˚
3
´
Dc1 ¨ P ¨ Dg “ p´5, 2, 1, 1, 1q ¨ ˚
˚ 200
˝ ´1
25
7
´ 50
47
200
˚ ´1
25
˚
3
Dc2 ¨ P ¨ Dg “ p´4, 1, 0, 2, 1q ¨ ˚
˚ ´ 200
˝ ´1
25
7
´ 50

11
Így r “ 12, r1 “ 31 adódnak, amiből a 11x ` y “ 13 lineáris diofantikus egyenletet
12
megoldva kapjuk az x “ 20 megoldást.

13

Példa a diszkrét logaritmus megoldására SageMath programban

14

15

16

17

4. Négyzetes körgráfMás sandpile gráfok esetén is felvetődik a kérdés, hogy alkalmasak-e kriptográfiai
használatra. Már Shokrieh is felvetette [9]-ben a módszere alkalmazásának lehetőségét nem ciklikus sandpile csoportokban. Az alábbi fejezetben [10] által leı́rt
Cn2 gráf sandpile csoportján értelmezett diszkrét logaritmus probléma megoldásáraalkalmazzuk Shokrieh módszerét.
4.1. Definı́ció. Legyen n pozitı́v egész, Cn pedig az n csúcsú körgráf V “ tv1 , . . . , vn u
csúcshalmazzal. Ekkor legyen Cn2 négyzetes körgráf az alábbi 4-reguláris gráf V
csúcshalmazzal, ahol minden i-edik csúcs szomszédos az i ˘ 1 pmod nq és i ˘2pmodnq csúcsokkal.

C32 , C42 és C82 gráfok

Több tanulmányban is foglalkoznak Cn2 sandpile csoportjának struktúrájának meghatározásával. A sandpile csoport elemszámának meghatározásában is fontos Cn2
feszı́tő fáinak száma τ p2n q “ nFn2 , ahol Fn az n-edik Fibonacci szám. Ezt eredetileg
Bedrosian sejtett meg, majd Kleitman és Golden bizonyı́tott [11]-ben. Továbbá
Hou, Woo és Chen [10]-ben megmutatta, hogy Cn2 sandpile csoportja két vagyhárom ciklikus csoport direkt szorzata, amik a következők:
SpCn2 q – Zpn,Fn q ‘ ZFn ‘ Z nFn .
pn,Fn qA csoport struktúrájának ismeretét és 2.4 részben leı́rtakat felhasználva oldjuk meg
a sandpile csoportban definiált diszkrét logaritmus problémát, mely az előző részhez
hasonlóan az alábbi módon adható meg. Legyen G “ Cn2 négyzetes körgráf, SpGqa gráfból keletkező sandpile csoport, továbbá c1 , c2 P SpGq konfigurációk. Keresettolyan 2 ď x ď ordpSpGqq, hogy c2 “ px ¨ c1 q˝ . Ekkor n paraméter megválasztásátólfüggően a sandpile csoport két vagy három csoport direkt szorzatára bomlik fel.

18

4.1. Cn2 -beli diszkrét logaritmus probléma megoldása
Az alapötlet Shokrieh algoritmusának használata, melyet alkalmazzunk az egyes
ciklikus részcsoportokra, majd részmegoldásokból a kı́nai maradéktétel alkalmazásával
adjuk meg az eredeti probléma megoldását.
A gráf ismeretében kiszámoljuk L Laplace-mátrixát, valamint annak P pszeudoinverzét a korábban ismertetett módon. A problémában adott c1 és c2 konfigurációkhoz adott divizorokat jelölje Dc1 és Dc2 hasonlóan az előző fejezethez,melyek a részcsoportok számától függetlenül ugyanazok.

Két generátoros eset
Amennyiben lnkopn, Fn q “ 1, ekkor SpGq “– ZFn ‘ Z nFn . Legyenek g1 és g2
pn,Fn qgenerátorai az egyes részcsoportoknak. Ekkor minden c P SpGq konfiguráció eseténc “ pn1 ¨ g1 ` n2 ¨ g2 q˝ , ahol ni P N és 0 ď ni ď ordpgi q i “ 1, 2. A generátorok ismeretében kiszámolhatóak a generátor konfigurációkhoz tartozó divizorok, melyeket
jelölje Dg1 és Dg2 .
Az egyes generátorok alkotta részcsoportokban használjuk Shokrieh módszerét.
Ismételten a 2.5 állı́tást felhasználva kiszámoljuk Dc1 ¨ P ¨ Dg1 és Dc2 ¨ P ¨ Dg1értékeket.
Amelyekből adódik egy x1 , mely a keletkező diofantikus egyenlet megoldását adja
modulo ord(g1 ). Hasonlóan Dc1 ¨ P ¨ Dg2 és Dc1 ¨ P ¨ Dg2 értékekből is adódik x2
megoldás modulo ord(g2 ).

Három generátoros eset
Amennyiben pn, Fn q ‰ 1, ekkor SpGq “ Zpn,Fn q ‘ ZFn ‘ Z nFn . Legyenek g1 , g2
pn,Fn qés g3 generátorai az egyes részcsoportoknak. Ekkor minden c P SpGq eseténc “ pn1 ¨ g1 ` n2 ¨ g2 ` n3 ¨ g3 q˝ , ahol ni P N és 0 ď ni ď ordpgi q i “ 1, 2, 3.
A generátorok ismeretében kiszámolhatóak a generátor konfigurációkhoz tartozódivizorok, melyeket jelölje Dg1 , Dg2 és Dg3 .
A két generátoros esetben már megoldott módon megkapjuk x1 és x2 megoldásokat
a g1 és g2 generátorok által generált részcsoportokban. Hasonlóan g3 generátort
felhasználva Dc1 ¨ P ¨ Dg3 és Dc1 ¨ P ¨ Dg3 értékekből keletkező diofantikus egyenletet
megoldva adódik x3 modulo ord(g3 ).
Mindkét esetben hasonlóan eljárva a kapott x1 , x2 , és esetleges x3 megoldásokbóladódó kongruencia rendszert a kı́nai maradéktétel segı́tségével megoldva adódik a
diszkrét logaritmus probléma megoldása SpCn2 q-ben.

194.1. Példa. Tekintsük példaként a 7 csúcsú négyzetes kerékgráfot. Legyenek
c1 “ p1, 3, 3, 2, 0, 1q és c2 “ p3, 1, 3, 2, 2, 0q tetszőlegesen választott konfigurációk.
Ekkor a gráf Laplace-mátrixa:
¨
4
˚ ´1
˚
˚ ´1
˚
L“˚
˚ 0
˚ 0
˚
˝ ´1
´1

´1
4
´1
´1
0
0
´1

0
´1
´1
4
´1
´1
0

´1
´1
4
´1
´1
0
0

0
0
´1
´1
4
´1
´1

´1
0
0
´1
´1
4
´1

˛
´1
´1 ‹
‹
0 ‹
‹
0 ‹
‹.
´1 ‹
‹
´1 ‚
4

Pszeudoinverze:
¨

18
91
˚ ´1
˚ 91
˚ ´2
˚ 91
6
P “˚
˚ ´ 91
˚ ´6
˚ 91
˝ ´2
91
1
´ 91

1
2
´ 91
´ 91
18
1
´ 91
91
1
18
´ 91
91
2
1
´ 91
´ 91
6
2
´ 91 ´ 91
6
6
´ 91
´ 91
2
6
´ 91
´ 91

6
6
´ 91
´ 91
2
6
´ 91 ´ 91
1
2
´ 91
´ 91
18
1
´ 91
91
1
18
´ 91
91
2
1
´ 91
´ 91
6
2
´ 91
´ 91

2
´ 91
6
´ 91
6
´ 91
2
´ 91
1
´ 91
18
91
1
´ 91

˛
1
´ 91
2 ‹
´ 91
‹
6 ‹
´ 91
‹
6 ‹
´ 91
‹.
2 ‹
´ 91
‹
1 ‚
´ 91
18
91

Tekintve a sandpile csoportot, mely két részcsoport direkt szorzatára bomlik fel, agenerátor konfigurációk a következők:• g1 “ p1, 1, 3, 2, 3, 0q• g2 “ p1, 1, 3, 2, 3, 0q.
Ezekből képzett divizorok:• Dg1 “ p´10, 1, 3, 3, 2, 0, 1q• Dg2 “ p´11, 3, 1, 3, 2, 2, 0q.
Továbbá kiszámoljuk Dc1 “ p´5, 2, 1, 1, 1q, Dc2 “ p´4, 1, 0, 2, 1q divizorokat.
A g1 generátort felhasználva tekintsük az alábbiakat
¨
˚
˚
˚
˚
Dc1 ¨ P ¨ Dg1 “ p´10, 1, 3, 3, 2, 0, 1q ˚
˚
˚
˚
˝
“

381
,
13

18
91
1
´ 91
2
´ 91
6
´ 91
6
´ 91
2
´ 91
1
´ 91

1
´ 91
18
91
1
´ 91
2
´ 91
6
´ 91
6
´ 91
2
´ 91

20

2
´ 91
1
´ 91
18
91
1
´ 91
2
´ 91
6
´ 91
6
´ 91

6
´ 91
2
´ 91
1
´ 91
18
91
1
´ 91
2
´ 91
6
´ 91

6
´ 91
6
´ 91
2
´ 91
1
´ 91
18
91
1
´ 91
2
´ 91

2
´ 91
6
´ 91
6
´ 91
2
´ 91
1
´ 91
18
91
1
´ 91

˛¨
˛
1
´ 91
´10
2 ‹˚
‹
´ 91
‹˚ 1 ‹
6 ‹˚
‹
´ 91
1
‹˚
‹
6 ‹˚
‹“
3
´ 91
‹
˚
‹
2 ‹˚
‹
2
´ 91
‹
˚
‹
1 ‚˝
3 ‚
´ 91
18
0
91

¨
˚
˚
˚
˚
Dc2 ¨ P ¨ Dg1 “ p´11, 3, 1, 3, 2, 2, 0q ˚
˚
˚
˚
˝
“

425
,
13

18
91
1
´ 91
2
´ 91
6
´ 91
6
´ 91
2
´ 91
1
´ 91

1
´ 91
18
91
1
´ 91
2
´ 91
6
´ 91
6
´ 91
2
´ 91

2
´ 91
1
´ 91
18
91
1
´ 91
2
´ 91
6
´ 91
6
´ 91

6
´ 91
2
´ 91
1
´ 91
18
91
1
´ 91
2
´ 91
6
´ 91

6
´ 91
6
´ 91
2
´ 91
1
´ 91
18
91
1
´ 91
2
´ 91

2
´ 91
6
´ 91
6
´ 91
2
´ 91
1
´ 91
18
91
1
´ 91

˛
˛¨
1
´ 91
´10
2 ‹˚
‹
´ 91
‹˚ 1 ‹6 ‹˚´ 91 ‹ ˚ 1 ‹
‹
6 ‹˚
3 ‹
´ 91
˚
‹
‹
2 ‹˚
2 ‹
´ 91
˚
‹
‹
1 ‚˝
3 ‚
´ 91
18
0
91

4
9
Így az algoritmusban használt jelöléseket megtartva r “ 13, r1 “ 13adódnak, amiből4
9
a 13 x`y “ 13 lineáris diofantikus egyenletet megoldva kapjuk az x1 “ 12 megoldást
modulo 13.

A g2 generátort felhasználva tekintsükaz alábbiakat
¨
˚
˚
˚
˚
Dc1 ¨ P ¨ Dg2 “ p´10, 1, 3, 3, 2, 0, 1q ˚
˚
˚
˚
˝
“

381
,
13
¨

˚
˚
˚
˚
Dc2 ¨ P ¨ Dg2 “ p´11, 3, 1, 3, 2, 2, 0q ˚
˚
˚
˚
˝
“

425
.
13

18
91
1
´ 91
2
´ 91
6
´ 91
6
´ 91
2
´ 91
1
´ 91

1
´ 91

18
91
1
´ 91
2
´ 91
6
´ 91
6
´ 91
2
´ 91
1
´ 91

1
´ 91

18
91
1
´ 91
2
´ 91
6
´ 91
6
´ 91
2
´ 91

18
91
1
´ 91
2
´ 91
6
´ 91
6
´ 91
2
´ 91

2
´ 91
1
´ 91
18
91
1
´ 91
2
´ 91
6
´ 91
6
´ 91

2
´ 91
1
´ 91
18
91
1
´ 91
2
´ 91
6
´ 91
6
´ 91

6
´ 91
2
´ 91
1
´ 91
18
91
1
´ 91
2
´ 91
6
´ 91

6
´ 91
2
´ 91
1
´ 91
18
91
1
´ 91
2
´ 91
6
´ 91

6
´ 91
6
´ 91
2
´ 91
1
´ 91
18
91
1
´ 91
2
´ 91

6
´ 91
6
´ 91
2
´ 91
1
´ 91
18
91
1
´ 91
2
´ 91

2
´ 91
6
´ 91
6
´ 91
2
´ 91
1
´ 91

˛
˛¨
1
´ 91
´11
2 ‹˚
‹
´ 91
‹˚ 3 ‹
6 ‹˚
‹
´ 91
1
‹
‹˚
6 ‹˚
‹“
3
´ 91
‹
˚
‹
2 ‹˚
‹
2
´ 91
‹
˚
‹
1 ‚˝
2 ‚
´ 91
18
0
91

2
´ 91
6
´ 91
6
´ 91
2
´ 91
1
´ 91

˛¨
˛
1
´ 91
´11
2 ‹˚
‹
´ 91
‹˚ 3 ‹6 ‹˚´ 91 ‹ ˚ 1 ‹
‹
6 ‹˚
3 ‹
´ 91
‹
˚
‹
2 ‹˚
2 ‹
´ 91
‹
˚
‹
1 ‚˝
2 ‚
´ 91
18
0
91

18
91
1
´ 91

18
91
1
´ 91

Így r “ 41, r1 “ 89adódnak, amiből a 41x ` y “ 89lineáris diofantikus egyenletet
91
91
91
91
megoldva kapjuk az x2 “ 51 megoldást modulo 91.
Végezetül tekintve a diofantikus egyenletek megoldásait, az alábbi kongruencia
rendszer adódik:x “ 12 pmod 13q.
x “ 51 pmod 91q
Ezt megoldva adódik a diszkrét logaritmus probléma x “ 51 megoldása.

21

Példa a diszkrét logaritmus megoldására SageMath programban

22

23

24

25

5. Általánosı́tott inverz
A következő fejezetben a Cn2 gráf sandpile csoportja felett értelmezett diszkrét logaritmus probléma megoldását szeretnénk leegyszerűsı́teni, egy általánosan használhatóparametrizált formula megadásával. Ehhez a gráf Laplace-mátrixának pszeudoinverzét szeretnénk általánosan megadni.
5.1. Definı́ció. Egy A “ paij q négyzetes mátrixot Toeplitz-mátrixnak nevezünk,
ha a főátlóval párhuzamos elemei megegyeznek, azaz az alábbi formájú:
¨
˛
a0
a1
a2
. . . an´1
˚ a´1
a0
a1
. . . an´2 ‹
˚
‹
˚ a´2
a´1
a0
. . . an´3 ‹
A“˚
‹.
˚ ..
..
..
.. ‹
.
.
˝ .
.
.
.
. ‚
a´n`1 a´n`2 a´n`3 . . . a0
A négyzetes körgráf Laplace-mátrixa egy speciális Toeplitz-mátrix, melyet ciklikusmátrixnak is neveznek.
5.2. Definı́ció. Egy A “ paij q négyzetes mátrixot k-ciklikus mátrixnak nevezünk,
melynek sorai ciklikusan ismétlődnek, azaz az alábbi formájú:
˛
¨
a0
a1
a2 . . . an´1
˚kan´1 ka0
a1 . . . an´2 ‹‹˚˚‹A “ ˚kan´2 kan´1 a0 . . . an´3 ‹ .
˚ ..
..
.. . .
.. ‹
˝ .
.
.
.
. ‚
ka1
ka2 ka3 . . . a0
Ha k “ 1 az A mátrixot egyszerűen ciklikusnak nevezzük, ahol aij “ aj´i , q ďi, j ď n. Az ilyen alakú mátrixok struktúrájával Cline, Plemmons és Worm [12]munkájukban foglalkoztak. A mi esetünkben a sandpile csoport jellemzésébeneredményeik közül a ciklikus mátrixok pszeudoinverze játszik majd kulcsszerepet.
Ehhez egy általánosabb inverz fogalmat vezetünk be. Az 3 és 4 fejezetekben már
előkerült a pszeudoiverz fogalma, azonban ennek általánosı́tásához tekintsük az
alábbiakat.
5.3. Definı́ció. Egy M nˆm mátrix pszeudoinverze alatt egy M 1 mátrixot értünk,
melyre M “ M M 1 M teljesül. Továbbá, amennyiben M 1 teljesı́ti az M 1 “ M 1 M M 1
feltételt, akkor M és M 1 egymás fél-inverzei. Azt az egyedi fél-inverzet, melyre
M M 1 és M 1 M hermitikussága is teljesül, Moore-Penrose inverznek nevezik, melynek
jelölése M ` .
Jelölje Cn az n ˆ n komplex mátrixok félcsoportját a szorzásra nézve. Minden
A P Cn esetén, A-nak valamely hatványa egy H maximális Cn -beli részcsoporthoz
26

tartozik. A legkisebb ilyen p pozitı́v egész számot, melyre Ap P H azt A indexének
nevezzük. Ha A indexe 1, akkor A1 , mely A pszeudoinverze H-ban van, melyet A
csoport inverzének nevezünk.
Az [13]-ban A-nak olyan A1 fél-inverzeit tekintik, melyben a A1 nemnulla sajátértékei
reciprokai az A nemnulla sajátértékeinek, ezeket spektrál inverznek nevezik. Továbbá
Scroggs és Odell megmutatják, hogy egy A nemnulla mátrixnak pontosan akkor
létezik spektrál inverze, ha A indexe 1. A spektrál inverz felhasználásával a gráfunk
sandpile csoportjának Laplace-mátrixának is megadható spektrál inverze, mely ar12s-ből adódóan megegyezik a Moore-Penrose pszeudoinverzzel.
Jelölje Z az n ˆ n mátrixokat, melynek sajátértékei különbözőek. Ekkor CZ -belimátrixok zártak a szorzásra nézve és félcsoportot alkotnak.
5.1. Tétel. Minden A P CZ indexe 1, és az egyedüli As spektrál inverz az egyetlen
pszeudoinverze A-nak. Továbbá ha Z normális, akkor As “ A`5.2. Tétel. Legyen A egy n ˆ n-es k-ciklikus mátrix a0 , . . . , an´1 első sorral ésµ0 , . . . , µn´1 sajátértékkel. Legyen ω primitı́v n-edik egységgyök, és λn “ k. Ekkor
As első sora b0 , . . . , bn´1 , ahol
bi “

ÿ
1 n´1
βj pλω j q´i ,n j“0továbbá
βj “

#
0
1
µj

i “ 0, 1, . . . , n ´ 1,
ha µj “ 0;ha µj ‰ 0.

5.3. Tétel. Legyen A k-ciklikus és szinguláris, ekkor A` is k-ciklikus pontosan
akkor, ha k az egységkörön van.
5.1. Következmény. Ha A k-ciklikus valamilyen k esetén, amikor k az egységkörön van, akkor As “ A`A Cn2 gráf esetén alkalmazható a 5.2 tétel k “ 1 esetén, továbbá a gráf ismeretében
Laplace-mátrixa jól leı́rható. Ezek segı́tségével a pszeudoinverz paraméteres felı́rása
is megadható.
5.1. Példa. Példaként tekintsük C42 gráfot, mely 4 reguláris és szomszédsági mátrixa
segı́tségével megadható Laplace-mátrixa, mely¨˛
4 ´1 ´2 ´1
˚ ´1
4 ´1 ´2 ‹‹.
L“˚˝ ´2 ´1
4 ´1 ‚´1 ´2 ´1
4
Látható, hogy a gráf 1-ciklikus, ı́gy Ls “ L` . Legyen ω “ i “
miatt L sajátértékei megadhatók a következőképpen:µj “ 2 ` ω j ´ ω 2j ,27

j “ 0, 1, 2, 3.

?
´1, ekkor REF

Vagyis µ0 “ 0, µ1 “ 6, µ2 “ 4, µ3 “ 6. Továbbá 5.2 alkalmazásával A` első sora az
alábbi módon adódik:ω ´t
ω ´3t ¯1´1``
, t “ 0, 1, 2, 3.
bi “
4 2 3`i 3´i71
11
Ebből b0 “ 48
, b1 “ 16, b2 “ ´ 48
, b3 “ 16, amely a pszeudoinverz első sorát adja,
ami hasonlóan L-hez 1-ciklikus, ı́gy
¨ 7
˛
1
1
1
´
´
´
48
16
48
16
7
1
1 ‹
˚ ´1
´
´
`
16
48
16
48 ‹ .
L “˚71 ‚˝ ´1 ´1
´ 16
48
16
48
1
7
1
1
´ 16
´ 48
´ 16
48

Az alábbi általánosı́tás segı́tségével tekintsük Cn2 sandpile csoportján adott disztkrétlogaritmus probléma megoldását. Legyenek SpCn2 q Laplace-mátrixa L, peszeudoinverze P “ L` , továbbá generátorai n paraméterétől függően gi “ pgi,0 , . . . , gi,n´1 q
i “ 1, 2 vagy i “ 1, 2, 3. Adott cj “ pcj,0 , . . . , cj,n´1 q j “ 1, 2 konfigurációk esetén akeresett diszkrét logaritmus probléma px ¨ c1 q˝ “ c2 esetén x megadása. Ekkor az
2.4 algoritmusbeli ri,j “ cj ¨ P ¨ gi párosı́tások értékeinek számı́tása egyszerűsödikle.
Először tekintsük az alábbi kifejezést:
¨
˛ ¨
˛ ¨
˛
p0 p1 . . . pn´1
gi,0
vi,0
˚pn´1 p0 . . . pn´2 ‹ ˚ gi,1 ‹ ˚ vi,1 ‹
˚
‹ ˚
‹ ˚
‹
P ¨ gi “ ˚ ..
..
.. ‹ ¨ ˚ .. ‹ “ ˚ .. ‹ ,˝ .
.
. ‚ ˝ . ‚ ˝ . ‚p1
ahol

p2 . . .

p0

$n´1
ÿ
’
’
’
pl ¨ gl&vi,k “

l“0
n´1
ÿ

’
’
’
%

gi,n´1vi,n´1ha k “ 0;“ vi .

¨pl´k p mod nq ¨ gl

ha k ‰ 0.

l“0

Innen
cj ¨ vi “

n´1
ÿ
l“0

cj,l ¨ vi,l “ c0 ¨n´1ÿpl ¨ gl `

l“0

n´1
ÿ

ck

n´1
ÿ

k“1

ahonnan pi elemek 5.2 szerint explicit kiszámolhatók.

28

l“0

pl´k p mod nq ¨ gl ,

6. Függelék12
34

def w_graph(n):G=graphs.WheelGraph(2*n+3)
V = G.vertices()
G.delete_edge(V[0],V[2*n+2])

5
6

return(G)

7
8
9
10
11
12

def cn2_graph(n):G = graphs.CycleGraph(n)G.allow_multiple_edges(True)for i in range(0, n):G.add_edge(i, (i + 2) % n)

13
14

return(G)

15
16
17

def config_vector(c):return vector([b for a,b in c.items()])

18
19
20

def divisor_vector(v):return vector([-1*sum(v)] + list(v))

21
22
23
24
25
26

def graph_figure(G, sink_vertex):
G = G.to_directed()
G.allow_multiple_edges(True)
G.to_directed()
G_edges = list(G.edges())

27
28
29
30

for e in G_edges:
if e[0] == sink_vertex:list(G.edges()).remove(e)

31
32
ãÑ

G.relabel(list(range(0,sink_vertex))+['sink']+list(range(sink_vertex+1,order(G)+1)

33
34

return G

35
36
37
38
39
40
41

example_list_wgraph = [[[(2, 1, 1, 1), (1, 0, 2, 1)],[(2, 2, 1, 0), (2, 2, 1, 1)],[(2, 1, 2, 1), (2, 2, 2, 0)],[(2, 2, 1, 1), (1, 2, 2, 1)],[(0, 1, 2, 1), (1, 1, 2, 1)]],

42
43
44

[[(1, 2, 2, 1, 2, 1), (2, 1, 0, 2, 1, 1)],[(2, 1, 1, 2, 1, 0), (2, 0, 1, 2, 2, 0)],

29

45
46
47

[(1, 1, 2, 1, 2, 1), (2, 2, 2, 1, 2, 1)],[(2, 2, 2, 1, 0, 1), (2, 0, 2, 0, 1, 1)],[(0, 1, 1, 1, 2, 1), (0, 1, 2, 1, 2, 1)]],

48
49
50
51
52
53

[[(2, 1, 2, 1, 1, 2, 2, 1), (2, 1, 1, 2, 2, 2, 1, 1)],[(2, 1, 0, 1, 2, 2, 2, 0), (2, 2, 0, 2, 0, 2, 1, 1)],[(2, 2, 0, 2, 1, 0, 2, 0), (2, 1, 0, 2, 2, 1, 0, 1)],[(0, 1, 1, 2, 0, 2, 2, 1), (1, 2, 2, 0, 2, 2, 1, 1)],[(1, 1, 0, 2, 2, 1, 2, 1), (2, 2, 0, 1, 1, 2, 1, 0)]]]

54
55
56
57
58
59
60

example_list_cn2graph = [[[(3, 2, 2, 1, 2), (1, 2, 2, 3, 2)],[(2, 3, 2, 0, 3), (1, 2, 0, 3, 2)],[(1, 3, 3, 3, 3), (2, 3, 2, 0, 3)],[(1, 2, 0, 3, 2), (3, 2, 0, 1, 2)],[(3, 2, 2, 1, 0), (0, 1, 2, 2, 3)]],

61
62
63
64
65
66

[[(1, 3, 3, 2, 0, 1), (3, 1, 3, 2, 2, 0)],[(3, 2, 0, 2, 1, 3), (3, 2, 2, 0, 3, 1)],[(2, 3, 2, 0, 2, 1), (2, 3, 2, 2, 0, 3)],[(3, 0, 1, 2, 2, 2), (3, 3, 2, 3, 2, 2)],[(3, 2, 2, 1, 3, 3), (0, 3, 1, 3, 2, 2)]],

67
68
69
70
71
72

[[(2, 2, 3, 2, 3, 1, 3), (3, 3, 0, 3, 1, 2, 1)],[(3, 3, 3, 1, 3, 2, 2), (3, 3, 3, 1, 2, 3, 1)],[(3, 3, 3, 2, 3, 3, 2), (3, 3, 3, 2, 0, 3, 3)],[(3, 3, 3, 0, 2, 1, 3), (3, 2, 0, 2, 1, 3, 3)],[(2, 0, 3, 2, 3, 3, 0), (3, 2, 2, 3, 1, 0, 2)]],

73
74
75
76
77
78

[[(1, 3, 0, 3, 1, 1, 3, 2), (3, 3, 2, 2, 2, 2, 3, 3)],[(2, 3, 2, 2, 3, 2, 3, 0), (3, 0, 1, 2, 2, 3, 3, 2)],[(3, 2, 3, 0, 1, 3, 3, 0), (3, 2, 3, 1, 2, 3, 2, 2)],[(2, 3, 2, 3, 3, 1, 2, 3), (3, 3, 1, 1, 3, 0, 3, 3)],[(3, 1, 0, 3, 1, 2, 3, 3), (3, 2, 3, 2, 3, 0, 1, 3)]],

79
80
81
82
83
84

[[(3, 2, 2, 3, 1, 2, 0, 2, 3), (3, 1, 3, 1, 3, 2, 2, 3, 3)],[(3, 3, 3, 2, 2, 2, 1, 1, 3), (1, 3, 3, 3, 3, 3, 2, 2, 1)],[(0, 3, 1, 3, 3, 2, 3, 1, 2), (2, 3, 2, 2, 1, 2, 1, 2, 2)],[(2, 3, 1, 3, 1, 2, 1, 3, 2), (3, 3, 1, 3, 3, 1, 1, 3, 2)],[(3, 3, 3, 2, 2, 3, 1, 1, 3), (2, 2, 2, 1, 2, 2, 3, 3, 1)]]]

85
86
87

def dlp_print():
pretty_print('Legyenek a választott konfigurációk {0} ésãÑ{1}\n'.format(c1_vector, c2_vector))

88
89
90

G_figure = graph_figure(G, 0)
G_figure.show()

91

30

92

93
94

95
96
97

pretty_print('Adott $G$ gráf esetén számı́tsuk ki Laplace matrixát,ãÑmajd annak pszeudoinverzét.')
print
pretty_print('\nAz igy kapott $L = D-A$ Laplace mátrix:',ãÑlaplacian_matrix)
print
pretty_print('$L$ pszeudoinverze: \n', pseudo_inverse);
print

98
99
100
101
102

pretty_print('A $\mathcal{S}(G)$ sandpile csoport generátor eleme:')for g in Generator_vector:
pretty_print(g)
print

103
104
105
106
107

pretty_print("A generátor elemb}ol kapott divisor vektor:")for g in Generator_divisor:pretty_print(g)
print

108
109

110
111
112

pretty_print("A választott konfigurációkból kapott divisor
ãÑ
vektorok:")pretty_print("$D_b={0}$".format(c1_divisor))
pretty_print("$D_c={0}$".format(c2_divisor))
print

113
114
115
116
117

def dlp_objects():
global c1_configuration, c2_configuration, c1_divisor, c2_divisor
c1_configuration = SandpileConfig(S, list(c1_vector))
c2_configuration = SandpileConfig(S, list(c2_vector))

118
119
120

c1_divisor = divisor_vector(c1_vector)
c2_divisor = divisor_vector(c2_vector)

121
122
123

global group_ordergroup_order = S.group_order()

124
125
126
127

global laplacian_matrix, pseudo_inverse
laplacian_matrix = S.laplacian_matrix()
pseudo_inverse = laplacian_matrix.pseudoinverse()

128
129

130
131
132
133

global generator_divisor, Generator, Generator_order,
ãÑGenerator_vector, Generator_divisor
Generator = S.group_gens()
Generator_order = [order(g) for g in Generator]
Generator_vector = [config_vector(g) for g in Generator]
Generator_divisor = [divisor_vector(g) for g in Generator_vector]

134
135

31

136
137
138

def dlp_sandpile():Generator_order_temp = copy(Generator_order)
Solutions = []

139
140
141
142

for i in range(0, len(Generator)):pretty_print('Az {0}. generátor felhasználásval:'.format(i+1))
print

143
144
145

pairing1 = c1_divisor*pseudo_inverse*Generator_divisor[i]pairing2 = c2_divisor*pseudo_inverse*Generator_divisor[i]

146
147
148

r1 = pairing1 - floor(pairing1)
r2 = pairing2 - floor(pairing2)

149
150

151

152
153
154

155
156

divisor_temp = Matrix(len(Generator_divisor[i]), 1,
ãÑGenerator_divisor[i])pretty_print('$D_b \cdot P \cdot D_g=$',c1_divisor,'$\cdot$',ãÑ
pseudo_inverse, '$\cdot$', divisor_temp, '$=$',
pairing1,'$=$', floor(pairing1), '$+$', r1)
print
pretty_print('$D_c \cdot P \cdot D_g=$',c2_divisor,'$\cdot$',ãÑ
pseudo_inverse, '$\cdot$', divisor_temp, '$=$',
pairing2,'$=$', floor(pairing2), '$+$', r2)
print

157
158
159

if r1.denominator() != Generator_order[i]:Generator_order_temp[i] = r1.denominator()

160
161
162

var('x,y')solution_diof_eq = solve_diophantine(r1*x+y==r2)

163
164

165

pretty_print('Keressük az alábbi lineáris diofantikus egyenletãÑmegoldását:',r1,'$x + y =$',r2)
print

166
167
168
169

if solution_diof_eq != 0:
solution = int(mod(int(solution_diof_eq[0](t_0 = 0)),ãÑGenerator_order_temp[i]))

170
171
172
173
174
175

176

else:
solution = 0
Generator_order_temp[i] = 1
pretty_print('A diofantikus egyenlet megoldása:')
pretty_print('$x_{0} = {1} \; (mod \ {2})$'.format(i+1, solution,
ãÑGenerator_order_temp[i]))
print

177

32

178

Solutions.append(solution)

179
180

dlp_solution = CRT_list(Solutions, Generator_order_temp)

181
182

return(dlp_solution)

183
184
185
186
187
188

189
190
191

#CODE W
@interact(layout=[['n','g']])def _(n = slider([1 .. 3], label = 'Gráf mérete', default = 2)):@interactdef _(selected_elements = selector(example_list_wgraph[n-1], label =ãÑ'Választott konfigurációk', default =ãÑexample_list_wgraph[n-1][0])):global c1_vector, c2_vector
c1_vector = selected_elements[0]c2_vector = selected_elements[1]

192
193
194
195

global S, G
G = w_graph(n)S = Sandpile(G,0)

196
197
198

dlp_objects()
dlp_print()

199
200

solution = dlp_sandpile()

201
202

pretty_print('A diszkrét logaritmus probléma megoldása az $x =ãÑ{0}.$'.format(solution))

203
204
205
206
207
208

209
210
211

#CODE CN2
@interact(layout=[['n','g']])def _(n = slider([6 .. 10], label = 'Gráf mérete', default = 8)):@interactdef _(selected_elements = selector(example_list_cn2graph[n-6], labelãÑ= 'Választott konfigurációk', default =ãÑexample_list_cn2graph[n-6][0])):global c1_vector, c2_vector
c1_vector = selected_elements[0]c2_vector = selected_elements[1]

212
213

global S, G

214
215
216

G = cn2_graph(n)S = Sandpile(G,0)

217
218
219

dlp_objects()
dlp_print()

220

33

221

solution = dlp_sandpile()

222
223

224

pretty_print('A diofantikus egyenletek megolásaiból, a Kı́naiãÑ
maradéktétel segı́tségével adódik a probléma megoldása.')
pretty_print('A diszkrét logaritmus probléma megoldása az $x =ãÑ{0}.$'.format(solution))34

Irodalomjegyzék[1] Per Bak, Chao Tang, and Kurt Wiesenfeld. Self-organized criticality: An
explanation of 1/f noise. Physical Review Letters, 59:381–384, 08 1987.
[2] Kim Christensen and Zeev Olami. Variation of the Gutenberg-Richter b values
and nontrivial temporal correlations in a Spring-Block Model for earthquakes.
Journal of Geophysical Research, 97:8729–8735, 06 1992.
[3] Peter Grassberger. On a self-organized critical forest-fire model. Journal of
Physics A: Mathematical and General, 26:2081, 01 1999.
[4] C.J. Rhodes and R.M. Anderson. Forest-fire as a model for the dynamics of
disease epidemics. Journal of the Franklin Institute, 335(2):199 – 211, 1998.
Part Special Issue on Biomathematics.
[5] John Beggs and Dietmar Plenz. Neuronal Avalanches in Neocortical Circuits.
The Journal of Neuroscience, 23:11167–11177, 12 2003.
[6] Ivana Ilic. The Discrete Logarithm Problem in Non-abelian Groups. PhD
thesis, Boca Raton, FL, USA, 2010.
[7] Norman Biggs. The critical group from a cryptographic perspective. Bulletinof the London Mathematical Society, 39, 08 2007.
[8] Simon Blackburn. Cryptanalysing the Critical Group: Efficiently Solving
Biggs’s Discrete Logarithm Problem. IACR Cryptology ePrint Archive,
2008:170, 11 2008.
[9] Farbod Shokrieh. The monodromy pairing and discrete logarithm on the Jacobian of finite graphs. Journal of Mathematical Cryptology, 4, 07 2009.
[10] Yaoping Hou, Chingwah Woo, and Pingge Chen. On the sandpile group of thesquare cycle Cn2. Linear Algebra and its Applications, 418:457–467, 10 2006.
[11] D. J. Kleitman and B. Golden. Counting Trees in a Certain Class of Graphs.
The American Mathematical Monthly, 82(1):40–44, 1975.
[12] R.E. Cline, R.J. Plemmons, and G. Worm. Generalized inverses of certain
Toeplitz matrices. Linear Algebra and its Applications, 8(1):25 – 33, 1974.
35

[13] James E. Scroggs and Patrick L. Odell. An Alternate Definition of a Pseudoinverse of a Matrix. SIAM Journal on Applied Mathematics, 14(4):796–810,
1966.
[14] David Perkinson, Jacob Perlman, and John Wilmes. Primer for the algebraic
geometry of sandpiles. 605, 12 2011.
[15] Dmitry Zhukov, Valery Kanishchev, and Sergey Lyamin. Application of the
Theory of Self-Organized Criticality to the Investigation of Historical Processes. SAGE Open, 6:215824401668321, 10 2016.

36