Pseudorandom graphs from elliptic curves

Igor E. Shparlinski

doi:10.1007/978-3-540-78773-0_25

Pseudorandom graphs from elliptic curves

Igor E. Shparlinski

School of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

1 Citation (Scopus)

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

Original language	English
Title of host publication	LATIN 2008: Theoretical Informatics - 8th Latin American Symposium, Proceedings
Editors	Eduardo Sany Laber, Claudson Bornstein, Loana Tito Nogueira, Luerbio Faria
Place of Publication	Berlin, New York
Publisher	Springer, Springer Nature
Pages	284-292
Number of pages	9
Volume	4957 LNCS
ISBN (Electronic)	9783540787730, 3540787739
ISBN (Print)	3540787720, 9783540787723
DOIs	https://doi.org/10.1007/978-3-540-78773-0_25
Publication status	Published - 2008
Event	8th Latin American TheoreticalINformatics Symposium, LATIN 2008 - Buzios, Brazil Duration: 7 Apr 2008 → 11 Apr 2008

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4957 LNCS
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Other

Other	8th Latin American TheoreticalINformatics Symposium, LATIN 2008
Country/Territory	Brazil
City	Buzios
Period	7/04/08 → 11/04/08

Access to Document

10.1007/978-3-540-78773-0_25

Cite this

Shparlinski, I. E. (2008). Pseudorandom graphs from elliptic curves. In E. S. Laber, C. Bornstein, L. T. Nogueira, & L. Faria (Eds.), LATIN 2008: Theoretical Informatics - 8th Latin American Symposium, Proceedings (Vol. 4957 LNCS, pp. 284-292). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4957 LNCS). Springer, Springer Nature. https://doi.org/10.1007/978-3-540-78773-0_25

Shparlinski, Igor E. / Pseudorandom graphs from elliptic curves. LATIN 2008: Theoretical Informatics - 8th Latin American Symposium, Proceedings. editor / Eduardo Sany Laber ; Claudson Bornstein ; Loana Tito Nogueira ; Luerbio Faria. Vol. 4957 LNCS Berlin, New York : Springer, Springer Nature, 2008. pp. 284-292 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{266e0805478d4ff2aa2aace398e1a082,

title = "Pseudorandom graphs from elliptic curves",

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

author = "Shparlinski, {Igor E.}",

year = "2008",

doi = "10.1007/978-3-540-78773-0_25",

language = "English",

isbn = "3540787720",

volume = "4957 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer, Springer Nature",

pages = "284--292",

editor = "Laber, {Eduardo Sany} and Claudson Bornstein and Nogueira, {Loana Tito} and Luerbio Faria",

booktitle = "LATIN 2008: Theoretical Informatics - 8th Latin American Symposium, Proceedings",

address = "United States",

note = "8th Latin American TheoreticalINformatics Symposium, LATIN 2008 ; Conference date: 07-04-2008 Through 11-04-2008",

}

Shparlinski, IE 2008, Pseudorandom graphs from elliptic curves. in ES Laber, C Bornstein, LT Nogueira & L Faria (eds), LATIN 2008: Theoretical Informatics - 8th Latin American Symposium, Proceedings. vol. 4957 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4957 LNCS, Springer, Springer Nature, Berlin, New York, pp. 284-292, 8th Latin American TheoreticalINformatics Symposium, LATIN 2008, Buzios, Brazil, 7/04/08. https://doi.org/10.1007/978-3-540-78773-0_25

Pseudorandom graphs from elliptic curves. / Shparlinski, Igor E.
LATIN 2008: Theoretical Informatics - 8th Latin American Symposium, Proceedings. ed. / Eduardo Sany Laber; Claudson Bornstein; Loana Tito Nogueira; Luerbio Faria. Vol. 4957 LNCS Berlin, New York: Springer, Springer Nature, 2008. p. 284-292 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4957 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - Pseudorandom graphs from elliptic curves

AU - Shparlinski, Igor E.

PY - 2008

Y1 - 2008

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

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

UR - http://www.scopus.com/inward/record.url?scp=43049142261&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-78773-0_25

DO - 10.1007/978-3-540-78773-0_25

M3 - Conference proceeding contribution

AN - SCOPUS:43049142261

SN - 3540787720

SN - 9783540787723

VL - 4957 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 284

EP - 292

BT - LATIN 2008: Theoretical Informatics - 8th Latin American Symposium, Proceedings

A2 - Laber, Eduardo Sany

A2 - Bornstein, Claudson

A2 - Nogueira, Loana Tito

A2 - Faria, Luerbio

PB - Springer, Springer Nature

CY - Berlin, New York

T2 - 8th Latin American TheoreticalINformatics Symposium, LATIN 2008

Y2 - 7 April 2008 through 11 April 2008

ER -

Shparlinski IE. Pseudorandom graphs from elliptic curves. In Laber ES, Bornstein C, Nogueira LT, Faria L, editors, LATIN 2008: Theoretical Informatics - 8th Latin American Symposium, Proceedings. Vol. 4957 LNCS. Berlin, New York: Springer, Springer Nature. 2008. p. 284-292. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-78773-0_25

Pseudorandom graphs from elliptic curves

Abstract

Publication series

Other

Access to Document

Other files and links

Fingerprint

Cite this