Pseudorandom graphs from elliptic curves

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review


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).

Original languageEnglish
Title of host publicationLATIN 2008: Theoretical Informatics - 8th Latin American Symposium, Proceedings
EditorsEduardo Sany Laber, Claudson Bornstein, Loana Tito Nogueira, Luerbio Faria
Place of PublicationBerlin, New York
PublisherSpringer, Springer Nature
Number of pages9
Volume4957 LNCS
ISBN (Electronic)9783540787730, 3540787739
ISBN (Print)3540787720, 9783540787723
Publication statusPublished - 2008
Event8th Latin American TheoreticalINformatics Symposium, LATIN 2008 - Buzios, Brazil
Duration: 7 Apr 200811 Apr 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4957 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349


Other8th Latin American TheoreticalINformatics Symposium, LATIN 2008

Fingerprint Dive into the research topics of 'Pseudorandom graphs from elliptic curves'. Together they form a unique fingerprint.

Cite this