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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
// SPDX-License-Identifier: Apache-2.0
// This file is part of the hekate-math project.
// Copyright (C) 2026 Andrei Kochergin <andrei@oumuamua.dev>
// Copyright (C) 2026 Oumuamua Labs <info@oumuamua.dev>.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//! Binary tower fields GF(2^8) through GF(2^256), each with a
//! second, polynomial basis for carry-less multiplication hardware.
//!
//! Every level is a quadratic extension of the one below:
//! GF(2^(2m)) = GF(2^m)\[X\] / (X^2 + X + τ), τ the lower level's
//! [`TowerField::EXTENSION_TAU`]. [`Block8`] is the AES field,
//! GF(2)\[x\] / (x^8 + x^4 + x^3 + x + 1) (FIPS-197 §4.2), and [`Bit`]
//! is GF(2) inside it. A level stores its `(lo, hi)` pair as one
//! integer, `Block16(u16)` to `Block128(u128)`; `Block256` holds
//! `[u128; 2]`.
//!
//! # Two bases
//!
//! Tower elements have type `F`. The same field in the flat basis
//! has type [`Flat<F>`], and the two types never mix in arithmetic.
//! [`HardwareField::to_hardware`] maps tower to flat and
//! [`HardwareField::from_hardware`] maps back. The flat basis is
//! GF(2)\[x\] modulo:
//!
//! | Field | Flat modulus |
//! |:----------|:---------------------------|
//! | GF(2^8) | x^8 + x^4 + x^3 + x + 1 |
//! | GF(2^16) | x^16 + x^5 + x^3 + x + 1 |
//! | GF(2^32) | x^32 + x^7 + x^3 + x^2 + 1 |
//! | GF(2^64) | x^64 + x^4 + x^3 + x + 1 |
//! | GF(2^128) | x^128 + x^7 + x^2 + x + 1 |
//!
//! `Flat<Block256>` extends the GF(2^128) flat basis by
//! y^2 + y + φ(τ), φ the tower-to-flat map.
//!
//! [`PackableField`] groups `WIDTH` elements into one packed value and
//! [`PackedFlat<F>`] is its flat form. [`FlatPromote`] embeds a flat
//! subfield element into a flat superfield.
//!
//! # Timing
//!
//! By default the basis maps are bit-sliced matrix products: no
//! branch or memory access depends on the value. Timing is not
//! formally verified. The `table-math` feature swaps in lookup tables
//! for the basis maps, the subfield lifts and GF(2^8) arithmetic;
//! their memory access depends on the operands, for public data only.
//!
//! Flat multiplication from GF(2^32) up uses PMULL on aarch64 with
//! the `aes` target feature, which `aarch64-unknown-linux-gnu` leaves
//! off by default (`-C target-feature=+aes`). Other targets take a
//! software path with the same results.
//!
//! # Features
//!
//! | Feature | Default | Effect |
//! |:-------------|:--------|:--------------------------------------|
//! | `std` | yes | without it: `no_std` with `alloc` |
//! | `parallel` | yes | Rayon for FFT buffers of 1 MiB and up |
//! | `table-math` | no | variable-time lookup tables, above |
//!
//! # Contents
//!
//! [`fft`] holds the additive FFT over the Cantor basis
//! ([`AdditiveFft`], [`CantorBasis`]) and a systematic Reed-Solomon
//! encoder ([`ReedSolomon`]). [`BinaryFieldExtras`] adds square,
//! Frobenius, trace and a root of x^2 + x = c, for Block16 through
//! Block256.
//!
//! # Examples
//!
//! ## Isomorphic workflow
//!
//! ```
//! use hekate_math::{Block128, HardwareField, TowerField};
//!
//! let a = Block128::from_uniform_bytes(&[0xaa; 32]);
//! let b = Block128::from_uniform_bytes(&[0xbb; 32]);
//!
//! let product = (a.to_hardware() * b.to_hardware()).to_tower();
//! assert_eq!(product, a * b);
//! ```
//!
//! ## SIMD vectorization
//!
//! ```
//! use hekate_math::{Block32, Flat, HardwareField, PackableField};
//!
//! let data: Vec<Flat<Block32>> = (1..=8u32)
//! .map(|i| Block32::from(i).to_hardware())
//! .collect();
//!
//! let a = Flat::<Block32>::pack(&data[..4]);
//! let b = Flat::<Block32>::pack(&data[4..]);
//!
//! let mut out = [Flat::<Block32>::default(); 4];
//! Flat::<Block32>::unpack(a * b, &mut out);
//!
//! for (i, lane) in out.iter().enumerate() {
//! let expected = data[i].to_tower() * data[4 + i].to_tower();
//! assert_eq!(lane.to_tower(), expected);
//! }
//! ```
//!
//! ## Additive FFT
//!
//! ```
//! use hekate_math::{AdditiveFft, Block16, Flat, HardwareField};
//!
//! let log_n = 10;
//! let fft = AdditiveFft::<Block16>::new(log_n)?;
//!
//! let coeffs: Vec<Flat<Block16>> = (0..1u32 << log_n)
//! .map(|i| Block16::from(i).to_hardware())
//! .collect();
//!
//! let mut data = coeffs.clone();
//! fft.forward_scalar(&mut data)?;
//! fft.inverse_scalar(&mut data)?;
//!
//! assert_eq!(data, coeffs);
//! # Ok::<(), hekate_math::FftError>(())
//! ```
//!
//! # Formal verification
//!
//! Tower `mul` and `invert`, the NEON kernels, the constant-time
//! basis maps and the additive FFT have Verus proofs against a
//! GF(2^k) model, kept outside the crate build in [`verus/`][verus].
//!
//! [verus]: https://github.com/oumuamua-labs/hekate-math/tree/main/verus
extern crate alloc;
pub use BinaryFieldExtras;
pub use ;
pub use *;
pub use ;
pub use ;
pub use *;