Name
Abstract | ||
|---|---|---|
This work completes the definition of a library which provides the basic arithmetic operations in binary finite fields as a set of functional terms with very specific features. Such a functional terms have type in Typeable Functional Assembly (TFA). TFA is an extension of Dual Light Affine Logic (DLAL). DLAL is a type assignment designed under the prescriptions of Implicit Computational Complexity (ICC), which characterises polynomial time costing computations.We plan to exploit the functional programming patterns of the terms in the library to implement cryptographic primitives whose running-time efficiency can be obtained by means of the least hand-made tuning as possible.We propose the library as a benchmark. It fixes a kind of lower bound on the difficulty of writing potentially interesting low cost programs inside languages that can express only computations with predetermined complexity. In principle, every known and future ICC compliant programming language for polynomially costing computations should supply a simplification over the encoding of the library we present, or some set of combinators of comparable interest and difficulty.We finally report on the applicative outcome that our library has and which is a reward we get by programming in the very restrictive scenario that TFA provides. The term of TFA which encodes the inversion in binary fields suggested us a variant of a known and efficient imperative implementation of the inversion itself given by Fong. Our variant, can outperform Fong's implementation of inversion on specific hardware architectures. We provide a functional programming language for polytime implicit complexity.We implement binary fields arithmetic in the language.We show several general meta-combinators specific to the language.We improve the implementation of inversion in finite fields by standard languages. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.scico.2015.04.001 | Science of Computer Programming |
Keywords | Field | DocType |
Lambda calculus,Finite fields arithmetic,Type assignments,Implicit computational complexity | Affine logic,Finite field,Lambda calculus,Programming language,Functional programming,Computer science,Upper and lower bounds,Combinatory logic,Arithmetic,Cryptographic primitive,Theoretical computer science,Time complexity | Journal |
Volume | Issue | ISSN |
111 | P3 | 0167-6423 |
Citations | PageRank | References |
0 | 0.34 | 14 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Daniele Canavese | 1 | 18 | 4.03 |
| Emanuele Cesena | 2 | 37 | 5.28 |
| Rachid Ouchary | 3 | 1 | 0.70 |
| Marco Pedicini | 4 | 60 | 10.43 |
| Luca Roversi | 5 | 183 | 21.03 |