## NAME

`BN_GF2m_add`

,
`BN_GF2m_sub`

, `BN_GF2m_cmp`

,
`BN_GF2m_mod_arr`

,
`BN_GF2m_mod`

,
`BN_GF2m_mod_mul_arr`

,
`BN_GF2m_mod_mul`

,
`BN_GF2m_mod_sqr_arr`

,
`BN_GF2m_mod_sqr`

,
`BN_GF2m_mod_inv`

,
`BN_GF2m_mod_inv_arr`

,
`BN_GF2m_mod_div`

,
`BN_GF2m_mod_div_arr`

,
`BN_GF2m_mod_exp_arr`

,
`BN_GF2m_mod_exp`

,
`BN_GF2m_mod_sqrt_arr`

,
`BN_GF2m_mod_sqrt`

,
`BN_GF2m_mod_solve_quad_arr`

,
`BN_GF2m_mod_solve_quad`

,
`BN_GF2m_poly2arr`

,
`BN_GF2m_arr2poly`

—
arithmetic in Galois fields of
power-of-2 order

## SYNOPSIS

```
#include
<openssl/bn.h>
```

`int`

`BN_GF2m_add`

(`BIGNUM *r`,
`const BIGNUM *a`, `const BIGNUM
*b`);

`int`

`BN_GF2m_sub`

(`BIGNUM *r`,
`const BIGNUM *a`, `const BIGNUM
*b`);

`int`

`BN_GF2m_cmp`

(`const BIGNUM *a`,
`const BIGNUM *b`);

`int`

`BN_GF2m_mod_arr`

(`BIGNUM *r`,
`const BIGNUM *a`, `const int
p[]`);

`int`

`BN_GF2m_mod`

(`BIGNUM *r`,
`const BIGNUM *a`, `const BIGNUM
*p`);

`int`

`BN_GF2m_mod_mul_arr`

(`BIGNUM *r`,
`const BIGNUM *a`, `const BIGNUM
*b`, `const int p[]`, `BN_CTX
*ctx`);

`int`

`BN_GF2m_mod_mul`

(`BIGNUM *r`,
`const BIGNUM *a`, `const BIGNUM
*b`, `const BIGNUM *p`, `BN_CTX
*ctx`);

`int`

`BN_GF2m_mod_sqr_arr`

(`BIGNUM *r`,
`const BIGNUM *a`, `const int p[]`,
`BN_CTX *ctx`);

`int`

`BN_GF2m_mod_sqr`

(`BIGNUM *r`,
`const BIGNUM *a`, `const BIGNUM
*p`, `BN_CTX *ctx`);

`int`

`BN_GF2m_mod_inv`

(`BIGNUM *r`,
`const BIGNUM *b`, `const BIGNUM
*p`, `BN_CTX *ctx`);

`int`

`BN_GF2m_mod_inv_arr`

(`BIGNUM *r`,
`const BIGNUM *b`, `const int p[]`,
`BN_CTX *ctx`);

`int`

`BN_GF2m_mod_div`

(`BIGNUM *r`,
`const BIGNUM *a`, `const BIGNUM
*b`, `const BIGNUM *p`, `BN_CTX
*ctx`);

`int`

`BN_GF2m_mod_div_arr`

(`BIGNUM *r`,
`const BIGNUM *a`, `const BIGNUM
*b`, `const int p[]`, `BN_CTX
*ctx`);

`int`

`BN_GF2m_mod_exp_arr`

(`BIGNUM *r`,
`const BIGNUM *a`, `const BIGNUM
*exponent`, `const int p[]`, `BN_CTX
*ctx`);

`int`

`BN_GF2m_mod_exp`

(`BIGNUM *r`,
`const BIGNUM *a`, `const BIGNUM
*exponent`, `const BIGNUM *p`,
`BN_CTX *ctx`);

`int`

`BN_GF2m_mod_sqrt_arr`

(`BIGNUM *r`,
`const BIGNUM *a`, `const int p[]`,
`BN_CTX *ctx`);

`int`

`BN_GF2m_mod_sqrt`

(`BIGNUM *r`,
`const BIGNUM *a`, `const BIGNUM
*p`, `BN_CTX *ctx`);

`int`

`BN_GF2m_mod_solve_quad_arr`

(`BIGNUM
*r`, `const BIGNUM *a`, `const int
p[]`, `BN_CTX *ctx`);

`int`

`BN_GF2m_mod_solve_quad`

(`BIGNUM
*r`, `const BIGNUM *a`, `const
BIGNUM *p`, `BN_CTX *ctx`);

`int`

`BN_GF2m_poly2arr`

(`const BIGNUM
*poly_in`, `int arr_out[]`, `int
arr_size`);

`int`

`BN_GF2m_arr2poly`

(`const int
arr_in[]`, `BIGNUM *poly_out`);

## DESCRIPTION

Two fields containing the same, finite number of elements are isomorphic, and the number of elements is called their order. The unique field of a given finite order is called the Galois field of that order. The following functions perform arithmetic operations on $\mathrm{GF}\left({2}^{m}\right)$ , the Galois fields of order ${2}^{m}$ , where $m$ is a natural number.

The
${2}^{m}$
elements of
$\mathrm{GF}\left({2}^{m}\right)$
are usually represented by the
${2}^{m}$
polynomials of a degrees less than
$m$
with binary coefficients. Such a polynomial can either be specified by
storing the coefficients in a `BIGNUM` object, using the
$m$
lowest bits with bit numbers corresponding to degrees, or by storing the
degrees that have coefficients of 1 in an integer array of at most
$m+1$
elements. For the functions below, the array needs to be sorted in decreasing
order and terminated by the delimiter element -1.

A specific representation of
$\mathrm{GF}\left({2}^{m}\right)$
is selected by choosing a polynomial of degree
$m$
that is irreducible with binary coefficients, called the reducing polynomial.
Making sure that
$p$
is of the correct degree and indeed irreducible is the responsibility of the
user. Typically, the following functions silently produce nonsensical
results when given a `p` argument that is of the wrong
degree or that is reducible. Storing the reducing polynomial requires
$m+1$
bits in a `BIGNUM` object or an `int`
array of up to
$m+2$
elements, including the terminating -1 element.

All functions produce correct results even if some or all of the
arguments `r`, `a`, and
`b` point to the same object.

`BN_GF2m_add`

()
adds the two polynomials `a` and `b`
with binary coefficients, which is equivalent to a pairwise exclusive OR
operation on the coefficients, and places the result into
`r`. In particular, if `a` and
`b` are elements of the same representation of the same
$\mathrm{GF}\left({2}^{m}\right)$
field, the sum of both in that representation of that field is computed (
$r=a+b$
). In contrast to most of the other functions described here, no modulo
operation is performed. Consequently, if the degree of at least one of the
arguments may be larger than or equal to
$m$
, a follow-up call to `BN_GF2m_mod_arr`

() or
`BN_GF2m_mod`

() may occasionally be useful.

`BN_GF2m_sub`

()
calculates the difference of `a` and
`b` (
$r=a-b=a+b$
). Since -1 is the same as 1 in binary arithmetic,
`BN_GF2m_sub`

() does exactly the same as
`BN_GF2m_add`

(). It is implemented as a macro.

`BN_GF2m_cmp`

()
is an alias for BN_ucmp(3). Despite its name, it does not attempt to find out whether
the two polynomials belong to the same congruence class with respect to some
Galois field.

`BN_GF2m_mod_arr`

()
and its wrapper
`BN_GF2m_mod`

()
divide the polynomial with binary coefficients `a` by
the polynomial with binary coefficients `p` and place
the remainder into `r` (
$r=a\left(\mathrm{mod}p\right)$
). If `r` and `a` point to the same
object, the modular reduction is done in place.

`BN_GF2m_mod_mul_arr`

()
and its wrapper
`BN_GF2m_mod_mul`

()
multiply `a` and `b`, divide the
result by `p`, and place the remainder in
`r` (
$r=a*b\left(\mathrm{mod}p\right)$
).

`BN_GF2m_mod_sqr_arr`

()
and its wrapper
`BN_GF2m_mod_sqr`

()
divide the square of `a` by `p` and
place the remainder in `r` (
$r=a*a\left(\mathrm{mod}p\right)$
).

`BN_GF2m_mod_inv`

()
and its wrapper
`BN_GF2m_mod_inv_arr`

()
reduce `b` modulo `p`, find the
multiplicative inverse element in
$\mathrm{GF}\left({2}^{m}\right)$
using the reducing polynomial
$p$
, and place the result into `r` (
$r=1/b\left(\mathrm{mod}p\right)$
).

`BN_GF2m_mod_div`

()
and its wrapper
`BN_GF2m_mod_div_arr`

()
reduce `a` and `b` modulo
`p`, compute their quotient in
$\mathrm{GF}\left({2}^{m}\right)$
using the reducing polynomial
$p$
, and place the result into `r` (
$r=a/b\left(\mathrm{mod}p\right)$
).

`BN_GF2m_mod_exp_arr`

()
and its wrapper
`BN_GF2m_mod_exp`

()
reduce `a` modulo `p`, raise it to
the power of `exponent` in
$\mathrm{GF}\left({2}^{m}\right)$
using the reducing polynomial
$p$
, and place the result into `r` (
$r={a}^{\mathrm{exponent}}\left(\mathrm{mod}p\right)$
).

`BN_GF2m_mod_sqrt_arr`

()
and its wrapper
`BN_GF2m_mod_sqrt`

()
reduce `a` modulo `p`, calculate the
square root in
$\mathrm{GF}\left({2}^{m}\right)$
using the reducing polynomial
$p$
by raising it to the power of
${2}^{m-1}$
, and place the result into `r` (
$r=\sqrt{a}\left(\mathrm{mod}p\right)$
). This works because of the identity
${a}^{{2}^{m}}=a$
which holds for all field elements
$a$
.

`BN_GF2m_mod_solve_quad_arr`

()
and its wrapper
`BN_GF2m_mod_solve_quad`

()
reduce `a` modulo `p`, solve the
quadratic equation
${r}^{2}+r=a\left(\mathrm{mod}p\right)$
in
$\mathrm{GF}\left({2}^{m}\right)$
using the reducing polynomial
$p$
, and place the solution into `r`.

`BN_GF2m_poly2arr`

()
converts a polynomial from a bit string stored in the
`BIGNUM` object `poly_in` to an
array containing the degrees of the non-zero terms. It is the responsibility
of the caller to provide an array `arr_out` of
sufficient size and to provide the number of elements that can be stored in
the array as the `arr_size` argument. The array is
filled with the degrees in decreasing order, followed by an element with the
value -1.

`BN_GF2m_arr2poly`

()
converts a polynomial from the array `arr_in` containing
degrees to a bit string placed in the `BIGNUM` object
`poly_out`. It is the responsibility of the caller to
provide the storage for `poly_out` and to make sure that
`arr_in` is terminated with a -1 element.

## RETURN VALUES

`BN_GF2m_cmp`

() interprets
`a` and `b` as integer numbers and
returns -1 if
$\left|a\right|<\left|b\right|$
, 0 if
$\left|a\right|=\left|b\right|$
, or 1 if
$\left|a\right|>\left|b\right|$
.

`BN_GF2m_poly2arr`

() returns:

- 0 if
`poly_in`has the value 0; - a number in the range from 2 to
`arr_size`, inclusive, in case of success, specifying the number of elements that have been stored into the array; - a number greater than
`arr_size`if the function failed because the array was too small, specifying the array size that would have been needed.

The other functions return 1 for success or 0 for failure.

## ERRORS

After some cases of failure, the following diagnostics can be retrieved with ERR_get_error(3), ERR_GET_REASON(3), and ERR_reason_error_string(3):

`BN_R_NO_SOLUTION`

"no solution"- No solution exists for the equation that
`BN_GF2m_mod_solve_quad_arr`

() or`BN_GF2m_mod_solve_quad`

() attempted to solve. `BN_R_INVALID_LENGTH`

"invalid length"- In one of the functions wrapping an
`*_arr`

() variant, the`BIGNUM *p`argument had a value of zero.

## SEE ALSO

BN_add(3), BN_CTX_new(3), BN_new(3), BN_set_bit(3), EC_POINT_new(3)

Darrel Hankerson,
Julio López Hernandez, and
Alfred Menezes, Software
Implementation of Elliptic Curve Cryptography over Binary Fields,
*CHES 2000: International Workshop on Cryptographic Hardware
and Embedded Systems*, *Springer*,
*Lecture Notes in Computer Science*, vol
1965,
https://doi.org/10.1007/3-540-44499-8_1,
Worcester, MA, USA, August
2000, Algorithm 10: Modified Almost Inverse
Algorithm for inversion in FP(2^m).

*Specifications for Public-Key
Cryptography*, IEEE Standard 1363,
https://doi.org/10.1109/IEEESTD.2000.92292,
August 29, 2000,
square-and-multiply algorithm A.5.1 for exponentiation,
exponentiation algorithm A.4.1 for square roots, and algorithms A.4.7 and
A.4.6 for the quadratic equation.