Binary Field Arithmetic

BFieldElt{D,R,T,L}

Represents an element in the binary field which has order $2^D$ and reduction polynomial

$x^D + x^{r_n} + \cdots + x^{r_0}$

where $R = r_n r_{n-1}\ldots r_1 r_0$ in binary. The polynomial is stored with a length L array of type T<:Unsigned words, using a StaticUInt{L,T} object (a wrapper for the type MVector{L,T} from StaticArrays).

Note: binary field arithmetic has been tested with words of type UInt8, UInt16, UInt32, UInt64 and UInt128. For any other possible word types, it is advisable to perform additional testing.

Types for points in the standard fields (taken from SEC 2, table 3) are available:

• BFieldElt113{T,L}
• BFieldElt131{T,L}
• BFieldElt163{T,L}
• BFieldElt193{T,L}
• BFieldElt233{T,L}
• BFieldElt239{T,L}
• BFieldElt283{T,L}
• BFieldElt409{T,L}
• BFieldElt571{T,L}

Each of these fields can be easily created by the functions B113(T), B131(T), etc., which take a word type T and they return a binary field element type with the smallest value of L. The function B(D, R, T) returns similar types, but for custom fields defined for D and R.

BFieldElt{D,R,T,L}(s::String) where {D,R,T,L}

Using the procedure set out in SEC 1 (version 2) 2.3.6, this converts a hex string to a field element.

==(a::BFieldElt{D,R,T,L}, b::BFieldElt{D,R,T,L}) where {D,R,T,L}

Returns true if a and b represent the same field element, and false otherwise.

+(a::BFieldElt{D,R,T,L}, b::BFieldElt{D,R,T,L}) where {D,R,T,L}

Returns a new element which is the result of $a+b$.

-(a::BFieldElt{D,R,T,L}, b::BFieldElt{D,R,T,L}) where {D,R,T,L}

Returns a new element which is the result of $a-b$.

*(a::BFieldElt{D,R,T,L}, b::BFieldElt{D,R,T,L}) where {D,R,T,L}

Returns a new element which is the result of $a \cdot b$. This is the default multiplication routine for binary field arithmetic, chosen to have high performance.

inv(a::BFieldElt{D,R,T,L}) where {D,R,T,L}

Returns a new element b such that $a b ≡ 1$ in the field represented by D and R.

/(a::BFieldElt{D,R,T,L}, b::BFieldElt{D,R,T,L}) where {D,R,T,L}

Returns a new element which is the result of $\frac{a}{b}$.

^(a::BFieldElt{D,R,T,L}, b::Integer) where {D,R,T,L}

Returns a new element which is the result of $a^b$. If squaring is required, i.e. b==2, it is faster to call square(a) directly.

square(a::BFieldElt{D,R,T,L}) where {D,R,T,L}

Returns a new element which is the result of $a^2$, using the default routine for high performance.

sqrt(a::BFieldElt{D,R,T,L}) where {D,R,T,L}

Returns b such that $b^2 \equiv a$.

mult_shiftandadd(a::BFieldElt{D,R,T,L}, b::BFieldElt{D,R,T,L}) where {D,R,T,L}

Binary field multiplication using a right-to-left shift-and-add method.

mult_shiftandadd_window(a::BFieldElt{D,R,T,L}, b::BFieldElt{D,R,T,L}, window::Int) where {D,R,T,L}

Binary field multiplication using a right-to-left shift-and-add method with a window size of window. The optimal window size for this routine is 4.

mult_threaded(a::BFieldElt{D,R,T,L}, b::BFieldElt{D,R,T,L}) where {D,R,T,L}

Binary field multiplication using a right-to-left shift-and-add method, by spawning an additional thread.

mult_threaded_window(a::BFieldElt{D,R,T,L}, b::BFieldElt{D,R,T,L}, w::Int) where {D,R,T,L}

Binary field multiplication using a windowed right-to-left shift-and-add method, by spawning an additional thread.

mult_ownreduce(a::BFieldElt{D,R,T,L}, b::BFieldElt{D,R,T,L}) where {D,R,T,L}

Binary field multiplication using a windowed right-to-left shift-and-add method, in which reduction is performed alongside multiplication.

mult_comb_rtl(a::BFieldElt{D,R,T,L}, b::BFieldElt{D,R,T,L}) where {D,R,T,L}

Binary field multiplication using a right-to-left comb method.

mult_comb_ltr(a::BFieldElt{D,R,T,L}, b::BFieldElt{D,R,T,L}) where {D,R,T,L}

Binary field multiplication using a left-to-right comb method.

mult_comb_window(a::BFieldElt{D,R,T,L}, b::BFieldElt{D,R,T,L}, window::Int) where {D,R,T,L}

Binary field multiplication using a windowed left-to-right comb method. Performs best with a window size of 4.

square_standard(a::BFieldElt{D,R,T,L}) where {D,R,T,L}

Binary field squaring performed by shifting each bit $b_i$ left by $i$.

square_window(a::BFieldElt{D,R,T,L}, window::Int) where {D,R,T,L}

Binary field squaring performed with a windowed method, in which the square of each size window block is calculated upfront. Performs best with a window size of 4.

reduce(a::BFieldElt{D,R,T,L}) where {D,R,T,L}

Returns the least element b, such that $a \equiv b$ in the field represented by D and R.

@fastreduce(D,R)

A macro to produce a specialised reduction function for the binary field denoted by $D$ and $R$. It is strongly recommended this is run for any new user-defined fields, as it achieves signficantly higher performance than the generic reduction routine.

iszero(a::BFieldElt)

Returns true if $a$ is the zero element of the binary field represented by D and R, and false otherwise.

zero(::Type{BFieldElt{D,R,T,L}}) where {D,R,T,L}

Returns the zero element (additive identity) of the specified field.

isone(a::BFieldElt)

Returns true if $a$ is equal to one (multiplicative identity), and false otherwise.

one(::Type{BFieldElt{D,R,T,L}}) where {D,R,T,L}

Returns element one (multiplicative identity) of the specified field.

random(::Type{BFieldElt{D,R,T,L}}) where {D,R,T,L}

Returns a random element of the specified field.

convert(::Type{BigInt}, a::BFieldElt)

Converts the given field point to a number (of type BigInt), following the procedure set out in SEC 1 (version 2) 2.3.9.