Constructing elements of large order in finite fields

Joachim Von Zur Gathen; Igor Shparlinski

doi:10.1007/3-540-46796-3_38

Constructing elements of large order in finite fields

Joachim Von Zur Gathen, Igor Shparlinski

School of Computing

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

12 Citations (Scopus)

Abstract

An efficient algorithm is presented which for any finite field Fq of small characteristic finds an extension F ^q _s of polynomially bounded degree and an element α∈ F ^q _s of exponentially large multiplicative order. The construction makes use of certain analogues of Gauss periods of a special type. This can be considered as another step towards solving the celebrated problem of finding primitive roots in finite fields efficiently.

Original language	English
Title of host publication	Applied Algebra, Algebraic Algorithms and Error-Correcting Codes
Subtitle of host publication	13th International Symposium, AAECC-13 Honolulu, Hawaii, USA, November 15–19, 1999 Proceedings
Editors	Marc Fossorier, Hideki Imai, Shu Lin, Alain Poli
Place of Publication	Berlin
Publisher	Springer, Springer Nature
Pages	404-409
Number of pages	6
Volume	1719
ISBN (Electronic)	9783540467960
ISBN (Print)	3540667237, 9783540667230
DOIs	https://doi.org/10.1007/3-540-46796-3_38
Publication status	Published - 1999
Event	13th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC - 1999 - Honolulu, United States Duration: 15 Nov 1999 → 19 Nov 1999

Publication series

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

Other

Other	13th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC - 1999
Country/Territory	United States
City	Honolulu
Period	15/11/99 → 19/11/99

Access to Document

10.1007/3-540-46796-3_38

Cite this

Von Zur Gathen, J., & Shparlinski, I. (1999). Constructing elements of large order in finite fields. In M. Fossorier, H. Imai, S. Lin, & A. Poli (Eds.), Applied Algebra, Algebraic Algorithms and Error-Correcting Codes: 13th International Symposium, AAECC-13 Honolulu, Hawaii, USA, November 15–19, 1999 Proceedings (Vol. 1719, pp. 404-409). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1719). Springer, Springer Nature. https://doi.org/10.1007/3-540-46796-3_38

Von Zur Gathen, Joachim ; Shparlinski, Igor. / Constructing elements of large order in finite fields. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes: 13th International Symposium, AAECC-13 Honolulu, Hawaii, USA, November 15–19, 1999 Proceedings. editor / Marc Fossorier ; Hideki Imai ; Shu Lin ; Alain Poli. Vol. 1719 Berlin : Springer, Springer Nature, 1999. pp. 404-409 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{9b9d299d6a5141f5a6760382803419ee,

title = "Constructing elements of large order in finite fields",

abstract = "An efficient algorithm is presented which for any finite field Fq of small characteristic finds an extension F q s of polynomially bounded degree and an element α∈ F q s of exponentially large multiplicative order. The construction makes use of certain analogues of Gauss periods of a special type. This can be considered as another step towards solving the celebrated problem of finding primitive roots in finite fields efficiently.",

author = "{Von Zur Gathen}, Joachim and Igor Shparlinski",

year = "1999",

doi = "10.1007/3-540-46796-3_38",

language = "English",

isbn = "3540667237",

volume = "1719",

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

publisher = "Springer, Springer Nature",

pages = "404--409",

editor = "Marc Fossorier and Hideki Imai and Shu Lin and Alain Poli",

booktitle = "Applied Algebra, Algebraic Algorithms and Error-Correcting Codes",

address = "United States",

note = "13th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC - 1999 ; Conference date: 15-11-1999 Through 19-11-1999",

}

Von Zur Gathen, J & Shparlinski, I 1999, Constructing elements of large order in finite fields. in M Fossorier, H Imai, S Lin & A Poli (eds), Applied Algebra, Algebraic Algorithms and Error-Correcting Codes: 13th International Symposium, AAECC-13 Honolulu, Hawaii, USA, November 15–19, 1999 Proceedings. vol. 1719, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1719, Springer, Springer Nature, Berlin, pp. 404-409, 13th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC - 1999, Honolulu, Hawaii, United States, 15/11/99. https://doi.org/10.1007/3-540-46796-3_38

Constructing elements of large order in finite fields. / Von Zur Gathen, Joachim; Shparlinski, Igor.
Applied Algebra, Algebraic Algorithms and Error-Correcting Codes: 13th International Symposium, AAECC-13 Honolulu, Hawaii, USA, November 15–19, 1999 Proceedings. ed. / Marc Fossorier; Hideki Imai; Shu Lin; Alain Poli. Vol. 1719 Berlin: Springer, Springer Nature, 1999. p. 404-409 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1719).

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

TY - CHAP

T1 - Constructing elements of large order in finite fields

AU - Von Zur Gathen, Joachim

AU - Shparlinski, Igor

PY - 1999

Y1 - 1999

N2 - An efficient algorithm is presented which for any finite field Fq of small characteristic finds an extension F q s of polynomially bounded degree and an element α∈ F q s of exponentially large multiplicative order. The construction makes use of certain analogues of Gauss periods of a special type. This can be considered as another step towards solving the celebrated problem of finding primitive roots in finite fields efficiently.

AB - An efficient algorithm is presented which for any finite field Fq of small characteristic finds an extension F q s of polynomially bounded degree and an element α∈ F q s of exponentially large multiplicative order. The construction makes use of certain analogues of Gauss periods of a special type. This can be considered as another step towards solving the celebrated problem of finding primitive roots in finite fields efficiently.

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

U2 - 10.1007/3-540-46796-3_38

DO - 10.1007/3-540-46796-3_38

M3 - Chapter

AN - SCOPUS:84957615849

SN - 3540667237

SN - 9783540667230

VL - 1719

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

SP - 404

EP - 409

BT - Applied Algebra, Algebraic Algorithms and Error-Correcting Codes

A2 - Fossorier, Marc

A2 - Imai, Hideki

A2 - Lin, Shu

A2 - Poli, Alain

PB - Springer, Springer Nature

CY - Berlin

T2 - 13th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC - 1999

Y2 - 15 November 1999 through 19 November 1999

ER -

Von Zur Gathen J, Shparlinski I. Constructing elements of large order in finite fields. In Fossorier M, Imai H, Lin S, Poli A, editors, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes: 13th International Symposium, AAECC-13 Honolulu, Hawaii, USA, November 15–19, 1999 Proceedings. Vol. 1719. Berlin: Springer, Springer Nature. 1999. p. 404-409. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-46796-3_38

Constructing elements of large order in finite fields

Abstract

Publication series

Other

Access to Document

Other files and links

Fingerprint

Preface

Cite this