g2p 1.1.0

A crate to create types that implement fast finite field arithmetic.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

# g2p
[Documentation](https://docs.rs/g2p)

This crate can generate types that implement fast finite field arithmetic.
Many error correcting codes rely on some form of finite field of the form GF(2^p), where
p is relatively small. Similarly some cryptographic algorithms such as AES use finite field
arithmetic.

While addition and subtraction can be done quickly using just a simple XOR, multiplication is
more involved. To speed things up, you can use a precomputed table. Typically this table is just
copied into the source code directly.
Using this crate, you can have the benefits in speed of precomputed table, without the need
to create your own type with custom multiplication and division implementation.

## WARNING
The types generated by this library are probably not suitable for cryptographic purposes, as
multiplication is not guaranteed to be constant time.

## Note
The implementation was tested for finite fields up to 2^17 in size, which compiles reasonably
fast. The space requirements are linear to the field size for the inversion table and log^2(N)
for the multiplication table. This means it is not feasible to use this to generate fields of
size 2^32, which would 4*4GB memory.

## Examples
```ignore
use g2p;
g2p::g2p!(GF16, 4, modulus: 0b10011);
let one: GF16 = 1.into();
let a: GF16 = 5.into();
let b: GF16 = 4.into();
let c: GF16 = 7.into();
assert_eq!(a + c, 2.into());
assert_eq!(a - c, 2.into());
assert_eq!(a * b, c);
assert_eq!(a / c, one / b);
assert_eq!(b / b, one);
```

## Performance
There is a benchmark suite comparing the result of this crate to [galois_2p8](https://crates.io/crates/galois_2p8)
and [reed-solomon-erasure](https://crates.io/crates/reed-solomon-erasure) which both implement a finite field with 256
elements.

![multiplication](doc/mul.svg) ![division](doc/div.svg)

Note that the competing libraries implement some special functionality to improve performance when one of the operands
is fixed. Here are the results:

![const operand multiplication](doc/mul_const.svg) ![const operand division](doc/div_const.svg)

## Implementation details
`g2p` generates a new type that implements all the common arithmetic operations. The
calculations are performed on either u8, u16 or u32, depending on the field size.

Addition and subtraction are implemented using regular `Xor`. For division, the divisor inverted
using a precomputed inversion table, which is then multiplied using the multiplication outlined
below

### Multiplication
Multiplication uses a number of precomputed tables to determine the result. Because a full table
would grow with the square of the field size, this approach was not deemed feasible. For
example, using a full table for GF65536 = GF(2^16), one would need 2^32 entries, which would
mean the program reserves 2*4GB just for these tables alone.

Instead a number `n` is split into 8bit components `n = a + 256 * b + 65536 * c ...`. Using this
representation we can multiply two numbers by cross-multiplying all the components
and then adding them up again. So assuming 16bit numbers `n = n0 + 256 * n1` and
`m = m0 + 256 * m1` we get `n*m = n0*m0 + 256*n0*m1 + 256*n1*m0 + 65536*n1*m1`.

We can now create precomputed tables for multiplying the different components together. There is
a table for first component times first component, first times second etc. The results then just
have to be added together using the normal finite field addition. For our GF65536 example this
means the multiplication tables use 4 * 256 * 256 entries รก 2 byte which is ~0.5MB

## License
Licensed under the Apache License, Version 2.0 [LICENSE-APACHE](LICENSE-APACHE)
or the MIT license [LICENSE-MIT](LICENSE-MIT)>, at your
option.