IRIS Pol. Torinohttps://iris.polito.itIl sistema di repository digitale IRIS acquisisce, archivia, indicizza, conserva e rende accessibili prodotti digitali della ricerca.Tue, 18 Feb 2020 21:30:40 GMT2020-02-18T21:30:40Z1021Can a Light Typing Discipline Be Compatible with an Efficient Implementation of Finite Fields Inversion?http://hdl.handle.net/11583/2514482Titolo: Can a Light Typing Discipline Be Compatible with an Efficient Implementation of Finite Fields Inversion?
Abstract: We show that an algorithm implementing the Binary-Field Arithmetic operation of multiplicative inversion exists as a purely functional term which is typeable in Dual Light Affine Logic (DLAL). As a consequence, the set ΛDLAL of functional terms typeable in DLAL is large enough to program the whole set of arithmetic operations. Second, and most important, we show
that ΛDLAL can be seen a domain specific language that forces programmer to think about algorithms under a non standard mental pattern which may result in more essential descriptions of known algorithms which, also, may be more efficient.
Wed, 01 Jan 2014 00:00:00 GMThttp://hdl.handle.net/11583/25144822014-01-01T00:00:00ZLight combinators for finite fields arithmetichttp://hdl.handle.net/11583/2623786Titolo: Light combinators for finite fields arithmetic
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.
Thu, 01 Jan 2015 00:00:00 GMThttp://hdl.handle.net/11583/26237862015-01-01T00:00:00Z