Functional pearl: Folding polynomials of polynomials

Chen Mou Cheng; Ruey Lin Hsu; Shin Cheng Mu

doi:10.1007/978-3-319-90686-7_5

Functional pearl: Folding polynomials of polynomials

Chen Mou Cheng^*
, Ruey Lin Hsu
, Shin Cheng Mu

^*Corresponding author for this work

National Taiwan University
National Central University
Academia Sinica Taiwan HQ

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

Abstract

Polynomials are a central concept to many branches in mathematics and computer science. In particular, manipulation of polynomial expressions can be used to model a wide variety of computation. In this paper, we consider a simple recursive construction of multivariate polynomials over a base ring such as the integers or a (finite) field. We show that this construction allows inductive implementation of polynomial operations such as arithmetic, evaluation, substitution, etc. Furthermore, we can transform a polynomial expression into in a sequence of arithmetic expressions in the base ring and prove the correctness of this transformation in Agda. Combined with our recursive construction, this allows for compiling polynomial expressions over a tower of extension fields into scalar expressions over the ground field, for example. Such a technique is not only interesting in its own right but also finds plentiful application in research areas such as cryptography.

Original language	English
Title of host publication	Functional and Logic Programming - 14th International Symposium, FLOPS 2018, Proceedings
Editors	John P. Gallagher, Martin Sulzmann, John P. Gallagher
Publisher	Springer Verlag
Pages	68-83
Number of pages	16
ISBN (Print)	9783319906850
DOIs	https://doi.org/10.1007/978-3-319-90686-7_5
State	Published - 2018
Externally published	Yes
Event	14th International Symposium on Functional and Logic Programming, FLOPS 2018 - Nagoya, Japan Duration: 09 05 2018 → 11 05 2018

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10818 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th International Symposium on Functional and Logic Programming, FLOPS 2018
Country/Territory	Japan
City	Nagoya
Period	09/05/18 → 11/05/18

Bibliographical note

Publisher Copyright:
© 2018, Springer International Publishing AG, part of Springer Nature.

Access to Document

10.1007/978-3-319-90686-7_5

Cite this

Cheng, C. M., Hsu, R. L., & Mu, S. C. (2018). Functional pearl: Folding polynomials of polynomials. In J. P. Gallagher, M. Sulzmann, & J. P. Gallagher (Eds.), Functional and Logic Programming - 14th International Symposium, FLOPS 2018, Proceedings (pp. 68-83). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10818 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-90686-7_5

Cheng, Chen Mou ; Hsu, Ruey Lin ; Mu, Shin Cheng. / Functional pearl : Folding polynomials of polynomials. Functional and Logic Programming - 14th International Symposium, FLOPS 2018, Proceedings. editor / John P. Gallagher ; Martin Sulzmann ; John P. Gallagher. Springer Verlag, 2018. pp. 68-83 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{1e919d6e79a94c01b3361c7455bfb1a9,

title = "Functional pearl: Folding polynomials of polynomials",

abstract = "Polynomials are a central concept to many branches in mathematics and computer science. In particular, manipulation of polynomial expressions can be used to model a wide variety of computation. In this paper, we consider a simple recursive construction of multivariate polynomials over a base ring such as the integers or a (finite) field. We show that this construction allows inductive implementation of polynomial operations such as arithmetic, evaluation, substitution, etc. Furthermore, we can transform a polynomial expression into in a sequence of arithmetic expressions in the base ring and prove the correctness of this transformation in Agda. Combined with our recursive construction, this allows for compiling polynomial expressions over a tower of extension fields into scalar expressions over the ground field, for example. Such a technique is not only interesting in its own right but also finds plentiful application in research areas such as cryptography.",

author = "Cheng, \{Chen Mou\} and Hsu, \{Ruey Lin\} and Mu, \{Shin Cheng\}",

note = "Publisher Copyright: {\textcopyright} 2018, Springer International Publishing AG, part of Springer Nature.; 14th International Symposium on Functional and Logic Programming, FLOPS 2018 ; Conference date: 09-05-2018 Through 11-05-2018",

year = "2018",

doi = "10.1007/978-3-319-90686-7\_5",

language = "英语",

isbn = "9783319906850",

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

publisher = "Springer Verlag",

pages = "68--83",

editor = "Gallagher, \{John P.\} and Martin Sulzmann and Gallagher, \{John P.\}",

booktitle = "Functional and Logic Programming - 14th International Symposium, FLOPS 2018, Proceedings",

address = "德国",

}

Cheng, CM, Hsu, RL & Mu, SC 2018, Functional pearl: Folding polynomials of polynomials. in JP Gallagher, M Sulzmann & JP Gallagher (eds), Functional and Logic Programming - 14th International Symposium, FLOPS 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10818 LNCS, Springer Verlag, pp. 68-83, 14th International Symposium on Functional and Logic Programming, FLOPS 2018, Nagoya, Japan, 09/05/18. https://doi.org/10.1007/978-3-319-90686-7_5

Functional pearl: Folding polynomials of polynomials. / Cheng, Chen Mou; Hsu, Ruey Lin; Mu, Shin Cheng.
Functional and Logic Programming - 14th International Symposium, FLOPS 2018, Proceedings. ed. / John P. Gallagher; Martin Sulzmann; John P. Gallagher. Springer Verlag, 2018. p. 68-83 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10818 LNCS).

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

TY - GEN

T1 - Functional pearl

T2 - 14th International Symposium on Functional and Logic Programming, FLOPS 2018

AU - Cheng, Chen Mou

AU - Hsu, Ruey Lin

AU - Mu, Shin Cheng

PY - 2018

Y1 - 2018

N2 - Polynomials are a central concept to many branches in mathematics and computer science. In particular, manipulation of polynomial expressions can be used to model a wide variety of computation. In this paper, we consider a simple recursive construction of multivariate polynomials over a base ring such as the integers or a (finite) field. We show that this construction allows inductive implementation of polynomial operations such as arithmetic, evaluation, substitution, etc. Furthermore, we can transform a polynomial expression into in a sequence of arithmetic expressions in the base ring and prove the correctness of this transformation in Agda. Combined with our recursive construction, this allows for compiling polynomial expressions over a tower of extension fields into scalar expressions over the ground field, for example. Such a technique is not only interesting in its own right but also finds plentiful application in research areas such as cryptography.

AB - Polynomials are a central concept to many branches in mathematics and computer science. In particular, manipulation of polynomial expressions can be used to model a wide variety of computation. In this paper, we consider a simple recursive construction of multivariate polynomials over a base ring such as the integers or a (finite) field. We show that this construction allows inductive implementation of polynomial operations such as arithmetic, evaluation, substitution, etc. Furthermore, we can transform a polynomial expression into in a sequence of arithmetic expressions in the base ring and prove the correctness of this transformation in Agda. Combined with our recursive construction, this allows for compiling polynomial expressions over a tower of extension fields into scalar expressions over the ground field, for example. Such a technique is not only interesting in its own right but also finds plentiful application in research areas such as cryptography.

UR - https://www.scopus.com/pages/publications/85046818338

U2 - 10.1007/978-3-319-90686-7_5

DO - 10.1007/978-3-319-90686-7_5

M3 - 会议稿件

AN - SCOPUS:85046818338

SN - 9783319906850

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

SP - 68

EP - 83

BT - Functional and Logic Programming - 14th International Symposium, FLOPS 2018, Proceedings

A2 - Gallagher, John P.

A2 - Sulzmann, Martin

A2 - Gallagher, John P.

PB - Springer Verlag

Y2 - 9 May 2018 through 11 May 2018

ER -

Cheng CM, Hsu RL, Mu SC. Functional pearl: Folding polynomials of polynomials. In Gallagher JP, Sulzmann M, Gallagher JP, editors, Functional and Logic Programming - 14th International Symposium, FLOPS 2018, Proceedings. Springer Verlag. 2018. p. 68-83. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-90686-7_5

Functional pearl: Folding polynomials of polynomials

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this