Abstract
Most of the constructions of pseudorandom graphs are based on additive or multiplicative groups of elements of finite fields. As a result the number of vertices of such graphs is limited to values of prime powers or some simple polynomial expressions involving prime powers. We show that elliptic curves over finite fields lead to new constructions of pseudorandom graphs with a new series of parameters. Accordingly, the number of vertices of such graphs can take most of positive integer values (in fact, any positive value under some classical conjectures about the gaps between prime numbers).
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N., Rónyai, L., Szabó, T.: Norm-graphs: Variations and applications. J. Combin. Theory, Ser. B 76, 280–290 (1999)
Chung, F.R.K.: Spectral graph theory. Amer. Math. Soc., Providence, RI (1997)
Cramer, H.: On the order of magnitude of the difference between consecutive prime numbers. Acta Arith. 2, 23–46 (1936)
Deuring, M.: Die Typen der Multiplikatorenringe elliptischer Funktionenkörper. Abh. Math. Sem. Hansischen Univ. 14, 197–272 (1941)
Granville, A., Shparlinski, I.E., Zaharescu, A.: On the distribution of rational functions along a curve over IF p and residue races. J. Number Theory 112, 216–237 (2005)
Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. Amer. Math. Soc. 43, 439–561 (2006)
Iwaniec, H., Kowalski, E.: Analytic number theory. Amer. Math. Soc., Providence, RI (2004)
Kohel, D.R., Shparlinski, I.E.: Exponential sums and group generators for elliptic curves over finite fields. In: Bosma, W. (ed.) ANTS 2000. LNCS, vol. 1838, pp. 395–404. Springer, Heidelberg (2000)
Krivelevich, M., Sudakov, B.: Pseudo-random graphs. In: More Sets, Graphs and Numbers. Bolyai Society Mathem. Studies 15, pp. 199–262. Springer, Heidelberg (2006)
Matomäki, K.: Large differences between consecutive primes. Quart. J. Math. 58, 489–518 (2007)
Murty, M.R.: Ramanujan graphs. J. Ramanujan Math. Soc. 18, 1–20 (2003)
Peck, A.S.: Differences between consecutive primes. Proc. London Math. Soc. 76, 33–69 (1998)
Shparlinski, I.E.: Bilinear character sums over elliptic curves. Finite Fields and Their Appl. (to appear)
Silverman, J.H.: The arithmetic of elliptic curves. Springer, Berlin (1995)
Vajaitu, M., Zaharescu, A.: Distribution of values of rational maps on the IF p -points on an affine curve. Monatsh. Math. 136, 81–86 (2002)
Tillich, J.-P., Zémor, G.: Hashing with SL2. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 40–49. Springer, Heidelberg (1994)
Zémor, G.: Hash functions and Cayley graphs. Designs, Codes and Cryptography 4, 381–394 (1994)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Shparlinski, I.E. (2008). Pseudorandom Graphs from Elliptic Curves. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds) LATIN 2008: Theoretical Informatics. LATIN 2008. Lecture Notes in Computer Science, vol 4957. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78773-0_25
Download citation
DOI: https://doi.org/10.1007/978-3-540-78773-0_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-78772-3
Online ISBN: 978-3-540-78773-0
eBook Packages: Computer ScienceComputer Science (R0)