License | BSD-style |
---|---|
Maintainer | Danny Navarro <j@dannynavarro.net> |
Stability | experimental |
Portability | Good |
Safe Haskell | Safe-Inferred |
Language | Haskell2010 |
This module provides basic arithmetic operations over F₂m. Performance is
not optimal and it doesn't provide protection against timing
attacks. The m
parameter is implicitly derived from the irreducible
polynomial where applicable.
Synopsis
- type BinaryPolynomial = Integer
- addF2m :: Integer -> Integer -> Integer
- mulF2m :: BinaryPolynomial -> Integer -> Integer -> Integer
- squareF2m' :: Integer -> Integer
- squareF2m :: BinaryPolynomial -> Integer -> Integer
- powF2m :: BinaryPolynomial -> Integer -> Integer -> Integer
- modF2m :: BinaryPolynomial -> Integer -> Integer
- sqrtF2m :: BinaryPolynomial -> Integer -> Integer
- invF2m :: BinaryPolynomial -> Integer -> Maybe Integer
- divF2m :: BinaryPolynomial -> Integer -> Integer -> Maybe Integer
Documentation
type BinaryPolynomial = Integer Source #
Binary Polynomial represented by an integer
:: BinaryPolynomial | Modulus |
-> Integer | |
-> Integer | |
-> Integer |
Multiplication over F₂m.
This function is undefined for negative arguments, because their bit representation is platform-dependent. Zero modulus is also prohibited.
squareF2m' :: Integer -> Integer Source #
Squaring over F₂m without reduction by modulo.
The implementation utilizes the fact that for binary polynomial S(x) we have S(x)^2 = S(x^2). In other words, insert a zero bit between every bits of argument: 1101 -> 1010001.
This function is undefined for negative arguments, because their bit representation is platform-dependent.
:: BinaryPolynomial | Modulus |
-> Integer | |
-> Integer |
Squaring over F₂m.
This function is undefined for negative arguments, because their bit representation is platform-dependent. Zero modulus is also prohibited.
:: BinaryPolynomial | Modulus |
-> Integer | a |
-> Integer | b |
-> Integer |
Exponentiation in F₂m by computing a^b mod fx
.
This implements an exponentiation by squaring based solution. It inherits the
same restrictions as squareF2m
. Negative exponents are disallowed.
:: BinaryPolynomial | Modulus |
-> Integer | |
-> Integer |
Reduction by modulo over F₂m.
This function is undefined for negative arguments, because their bit representation is platform-dependent. Zero modulus is also prohibited.
:: BinaryPolynomial | Modulus |
-> Integer | a |
-> Integer |
Square rooot in F₂m.
We exploit the fact that a^(2^m) = a
, or in particular, a^(2^m - 1) = 1
from a classical result by Lagrange. Thus the square root is simply a^(2^(m
- 1))
.
:: BinaryPolynomial | Modulus |
-> Integer | |
-> Maybe Integer |
Modular inversion over F₂m.
If n
doesn't have an inverse, Nothing
is returned.
This function is undefined for negative arguments, because their bit representation is platform-dependent. Zero modulus is also prohibited.
:: BinaryPolynomial | Modulus |
-> Integer | Dividend |
-> Integer | Divisor |
-> Maybe Integer | Quotient |
Division over F₂m. If the dividend doesn't have an inverse it returns
Nothing
.
This function is undefined for negative arguments, because their bit representation is platform-dependent. Zero modulus is also prohibited.