fgf 3.0.2

Faster Galois Fields: SIMD and portable finite-field arithmetic (binary towers and prime fields) and vector kernels
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

//! Explore subfield embeddings, Frobenius conjugates, trace, and norm.
//!
//! Run with `just example extension_fields`, optionally with
//! `--no-default-features`. Binary trace and norm are expressed through public
//! scalar arithmetic; QuadMersenne31 also supplies conjugate and norm methods.

#![forbid(unsafe_code)]

use fgf::Field;
use fgf::{Elem, FiniteField, Mersenne31, Polynomial, QuadMersenne31};

use fgf::poly::AES;

// Callers name their own fields; the canonical `FiniteField<2, N, R>` type is the API.
type Gf16 = fgf::FiniteField<2, 16, fgf::Extension<fgf::Rijndael16, 2>>;
type FanPaar8Field = fgf::FiniteField<2, 8, fgf::Extension<fgf::FanPaar8, 2>>;
type FanPaar16Field = fgf::FiniteField<2, 16, fgf::Extension<fgf::FanPaar16, 2>>;

fn main() {
    // In the AES-rooted tower, x = a + b*u and u^2 + u + DELTA = 0.
    let a = Elem::<FiniteField<2, 8, Polynomial<AES>>>::from_raw(0x53);
    let b = Elem::<FiniteField<2, 8, Polynomial<AES>>>::from_raw(0xca);
    let x = Elem::<Gf16>::from_components([a, b]);
    let conjugate = x.pow(FiniteField::<2, 8, Polynomial<AES>>::ORDER);
    assert_eq!(conjugate, Elem::<Gf16>::from_components([a + b, b]));
    assert_eq!(
        conjugate.pow(FiniteField::<2, 8, Polynomial<AES>>::ORDER),
        x
    );
    assert_eq!(x.pow(Gf16::ORDER), x);

    // Relative trace and norm land in the embedded byte subfield.
    let trace = x + conjugate;
    let norm = x * conjugate;
    assert_eq!(
        trace,
        Elem::<Gf16>::from_components([b, Elem::<FiniteField<2, 8, Polynomial<AES>>>::ZERO])
    );
    let [norm_base, norm_extension] = norm.to_components();
    assert_eq!(
        norm_extension,
        Elem::<FiniteField<2, 8, Polynomial<AES>>>::ZERO
    );
    assert_eq!(
        norm_base,
        a.square()
            + a * b
            + Elem::<FiniteField<2, 8, Polynomial<AES>>>::from_raw(0x20) * b.square()
    );
    assert_eq!(x * x.inv(), Elem::<Gf16>::ONE);
    assert_eq!(x.to_bytes(), [a.to_raw(), b.to_raw()]);

    // The total conventions: inversion and division map zero to zero, and
    // the zeroth power is one for every element.
    assert_eq!(Elem::<Gf16>::ZERO.inv(), Elem::<Gf16>::ZERO);
    assert_eq!(x.div(Elem::<Gf16>::ZERO), Elem::<Gf16>::ZERO);
    assert_eq!(Elem::<Gf16>::ZERO.pow(0), Elem::<Gf16>::ONE);

    // The shipped generator of the Fan–Paar tower has full multiplicative
    // order, like every frozen generator in the crate.
    assert_eq!(
        Elem::<FanPaar16Field>::GENERATOR.pow(65_535),
        Elem::<FanPaar16Field>::ONE
    );
    println!("AES-rooted tower: x={x}, conjugate={conjugate}, trace={trace}, norm={norm_base}");

    // Fan–Paar has another basis. Embed via components, not by relabelling
    // an AES or polynomial-basis payload as a Fan–Paar payload.
    let c = Elem::<FanPaar8Field>::from_raw(0x53);
    let d = Elem::<FanPaar8Field>::from_raw(0xca);
    let embedded_c = Elem::<FanPaar16Field>::from_components([c, Elem::<FanPaar8Field>::ZERO]);
    let embedded_d = Elem::<FanPaar16Field>::from_components([d, Elem::<FanPaar8Field>::ZERO]);
    assert_eq!(
        embedded_c * embedded_d,
        Elem::<FanPaar16Field>::from_components([c * d, Elem::<FanPaar8Field>::ZERO])
    );
    let y = Elem::<FanPaar16Field>::from_components([c, d]);
    assert_eq!(y.mul_alpha(), y * Elem::<FanPaar16Field>::from_raw(0x0100));
    let y_conjugate = y.pow(256);
    assert_eq!(
        (y + y_conjugate).to_components()[1],
        Elem::<FanPaar8Field>::ZERO
    );
    assert_eq!(
        (y * y_conjugate).to_components()[1],
        Elem::<FanPaar8Field>::ZERO
    );
    println!(
        "Fan–Paar tower: y={y}, y * tower generator={}",
        y.mul_alpha()
    );

    // Odd-characteristic quadratic extension: z = re + im*i, i^2 = -1.
    let re = Elem::<Mersenne31>::from_raw(7);
    let im = Elem::<Mersenne31>::from_raw(11);
    let z = Elem::<QuadMersenne31>::from_components([re, im]);
    assert_eq!(
        Elem::<QuadMersenne31>::I.square(),
        -Elem::<QuadMersenne31>::ONE
    );
    assert_eq!(z.pow(Mersenne31::ORDER), z.conjugate());
    assert_eq!(z.norm(), re.square() + im.square());
    assert_eq!(
        z * z.conjugate(),
        Elem::<QuadMersenne31>::from_components([z.norm(), Elem::<Mersenne31>::ZERO])
    );
    assert_eq!(z * z.inv(), Elem::<QuadMersenne31>::ONE);
    println!(
        "QuadMersenne31: z={z}, conjugate={}, norm={}",
        z.conjugate(),
        z.norm()
    );
}