turkmath.org

We all know the Riemann-Roch theorem. I will talk about an analogue on a finite graph by M. Baker and S. Norine in [2] and related results of F. Shokrieh [3] and myself [1]. As in the classic case, we get divisors, an equivalence relation and a (abelian) divisor class group, which is the quotient group of degree 0 divisors and principal divisors. When fixing a base vertex, in each equivalence class there is exactly one reduced divisor and the divisor reduction is related with an interesting, so called, unconstrained chip firing game. Using Dhar's Burning Algorithm, the reduction can be done fast and we get an efficient arithmetic in the divisor class group. We will see some examples and conclude, that for each finite abelian group, there is a graph with this group as divisor class group. We also give a short view on a cryptographic perspective and contrary to F. Shokrieh in [3], we conclude that there are graphs suitable for cryptography.

Literature:
[1] Stefan Hellbusch, Riemann-Roch Theorie auf Graphen und Anwendungen, 2013
[2] Matthew Baker, Serguei Norine, Riemann-Roch and Abel-Jacobi Theory on a finite Graph, 2007
[3] Farbod Shokrieh, The monodromy pairing and discrete logarithm on the Jacobian of finite graphs, 2010