On exponential sums and group generators for elliptic curves over finite fields

David R. Kohel; Igor E. Shparlinski

On exponential sums and group generators for elliptic curves over finite fields

David R. Kohel, Igor E. Shparlinski

School of Computing

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

57 Citations (Scopus)

Abstract

In the paper an upper bound is established for certain exponential sums, analogous to Gaussian sums, defined on the points of an elliptic curve over a prime finite field. The bound is applied to prove the existence of group generators for the set of points on an elliptic curve over F_q among certain sets of bounded size. We apply this estimate to obtain a deterministic O(q^1/2+ε) algorithm for finding generators of the group in echelon form, and in particular to determine its group structure.

Original language	English
Title of host publication	Algorithmic Number Theory
Subtitle of host publication	4th International Symposium, ANTS-IV Leiden, The Netherlands, July 2-7, 2000 Proccedings
Editors	Wieb Bosma
Place of Publication	Berlin
Publisher	Springer, Springer Nature
Pages	395-404
Number of pages	10
Volume	1838
ISBN (Electronic)	9783540449942
ISBN (Print)	3540676953
Publication status	Published - 2000
Event	4th International Symposium on Algorithmic Number Theory, ANTS 2000 - Leiden, Netherlands Duration: 2 Jul 2000 → 7 Jul 2000

Publication series

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

Other

Other	4th International Symposium on Algorithmic Number Theory, ANTS 2000
Country/Territory	Netherlands
City	Leiden
Period	2/07/00 → 7/07/00

Cite this

Kohel, D. R., & Shparlinski, I. E. (2000). On exponential sums and group generators for elliptic curves over finite fields. In W. Bosma (Ed.), Algorithmic Number Theory : 4th International Symposium, ANTS-IV Leiden, The Netherlands, July 2-7, 2000 Proccedings (Vol. 1838, pp. 395-404). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1838). Springer, Springer Nature.

Kohel, David R. ; Shparlinski, Igor E. / On exponential sums and group generators for elliptic curves over finite fields. Algorithmic Number Theory : 4th International Symposium, ANTS-IV Leiden, The Netherlands, July 2-7, 2000 Proccedings. editor / Wieb Bosma. Vol. 1838 Berlin : Springer, Springer Nature, 2000. pp. 395-404 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{921a85621fb54bdab772673154a558bb,

title = "On exponential sums and group generators for elliptic curves over finite fields",

abstract = "In the paper an upper bound is established for certain exponential sums, analogous to Gaussian sums, defined on the points of an elliptic curve over a prime finite field. The bound is applied to prove the existence of group generators for the set of points on an elliptic curve over Fq among certain sets of bounded size. We apply this estimate to obtain a deterministic O(q1/2+ε) algorithm for finding generators of the group in echelon form, and in particular to determine its group structure.",

author = "Kohel, {David R.} and Shparlinski, {Igor E.}",

year = "2000",

language = "English",

isbn = "3540676953",

volume = "1838",

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

publisher = "Springer, Springer Nature",

pages = "395--404",

editor = "Wieb Bosma",

booktitle = "Algorithmic Number Theory",

address = "United States",

note = "4th International Symposium on Algorithmic Number Theory, ANTS 2000 ; Conference date: 02-07-2000 Through 07-07-2000",

}

Kohel, DR & Shparlinski, IE 2000, On exponential sums and group generators for elliptic curves over finite fields. in W Bosma (ed.), Algorithmic Number Theory : 4th International Symposium, ANTS-IV Leiden, The Netherlands, July 2-7, 2000 Proccedings. vol. 1838, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1838, Springer, Springer Nature, Berlin, pp. 395-404, 4th International Symposium on Algorithmic Number Theory, ANTS 2000, Leiden, Netherlands, 2/07/00.

On exponential sums and group generators for elliptic curves over finite fields. / Kohel, David R.; Shparlinski, Igor E.
Algorithmic Number Theory : 4th International Symposium, ANTS-IV Leiden, The Netherlands, July 2-7, 2000 Proccedings. ed. / Wieb Bosma. Vol. 1838 Berlin: Springer, Springer Nature, 2000. p. 395-404 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1838).

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

TY - GEN

T1 - On exponential sums and group generators for elliptic curves over finite fields

AU - Kohel, David R.

AU - Shparlinski, Igor E.

PY - 2000

Y1 - 2000

N2 - In the paper an upper bound is established for certain exponential sums, analogous to Gaussian sums, defined on the points of an elliptic curve over a prime finite field. The bound is applied to prove the existence of group generators for the set of points on an elliptic curve over Fq among certain sets of bounded size. We apply this estimate to obtain a deterministic O(q1/2+ε) algorithm for finding generators of the group in echelon form, and in particular to determine its group structure.

AB - In the paper an upper bound is established for certain exponential sums, analogous to Gaussian sums, defined on the points of an elliptic curve over a prime finite field. The bound is applied to prove the existence of group generators for the set of points on an elliptic curve over Fq among certain sets of bounded size. We apply this estimate to obtain a deterministic O(q1/2+ε) algorithm for finding generators of the group in echelon form, and in particular to determine its group structure.

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

M3 - Conference proceeding contribution

AN - SCOPUS:84946822318

SN - 3540676953

VL - 1838

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

SP - 395

EP - 404

BT - Algorithmic Number Theory

A2 - Bosma, Wieb

PB - Springer, Springer Nature

CY - Berlin

T2 - 4th International Symposium on Algorithmic Number Theory, ANTS 2000

Y2 - 2 July 2000 through 7 July 2000

ER -

Kohel DR, Shparlinski IE. On exponential sums and group generators for elliptic curves over finite fields. In Bosma W, editor, Algorithmic Number Theory : 4th International Symposium, ANTS-IV Leiden, The Netherlands, July 2-7, 2000 Proccedings. Vol. 1838. Berlin: Springer, Springer Nature. 2000. p. 395-404. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

On exponential sums and group generators for elliptic curves over finite fields

Abstract

Publication series

Other

Other files and links

Fingerprint

Cite this