Repository: ergoplatform/sigma-rust (language: rust)

Issue:
[800 SigmaUSD] Arithmetic operations and polynomial interpolation over Galois fields GF(2^192)
### Implementation details
Extract https://github.com/ergoplatform/sigma-rust/blob/develop/ergotree-interpreter/src/sigma_protocol/gf2_192.rs and https://github.com/ergoplatform/sigma-rust/blob/develop/ergotree-interpreter/src/sigma_protocol/gf2_192poly.rs into a separate crate `gf2_192` and implement according to existing implementation in Scala https://github.com/ScorexFoundation/sigmastate-interpreter/blob/prepare-v5.0-evaluator/sigmastate/src/main/java/gf2t/GF2_192.java , https://github.com/ScorexFoundation/sigmastate-interpreter/blob/prepare-v5.0-evaluator/sigmastate/src/main/java/gf2t/GF2_192_Poly.java

### Testing 
Implement tests according to the tests in Scala version in https://github.com/ScorexFoundation/sigmastate-interpreter/blob/prepare-v5.0-evaluator/sigmastate/src/test/java/gf2t/GF2_192Test.java

### References
https://github.com/reyzin/GF2t

Existing Rust implementation for Galois fields GF(2^256):
https://github.com/djsweet/galois_2p8
https://github.com/geky/gf256


Discussion / hints:
Starting this one!

Fix patch:
diff --git a/Cargo.toml b/Cargo.toml
index 510c68020..735617a45 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -10,6 +10,7 @@ members = [
     "ergo-p2p",
     "ergo-chain-types",
     "ergo-nipopow",
+    "gf2_192",
     "bindings/ergo-lib-wasm",
     "bindings/ergo-lib-c-core",
     "bindings/ergo-lib-c",
diff --git a/ergotree-interpreter/Cargo.toml b/ergotree-interpreter/Cargo.toml
index 06e8be445..b9081084e 100644
--- a/ergotree-interpreter/Cargo.toml
+++ b/ergotree-interpreter/Cargo.toml
@@ -16,6 +16,7 @@ crate-type = ["cdylib", "rlib"]
 [dependencies]
 sigma-util = { version = "^0.3.0", path = "../sigma-util" }
 ergotree-ir = { version = "^0.14.0", path = "../ergotree-ir" }
+gf2_192 = { version = "^0.14.0", path = "../gf2_192" }
 indexmap = "1.3.2"
 k256 = { version = "0.9.6", features = ["zeroize", "arithmetic", "ecdsa"] }
 elliptic-curve = {version = "0.10.6", features = [ "zeroize", "ff"]}
diff --git a/ergotree-interpreter/src/sigma_protocol.rs b/ergotree-interpreter/src/sigma_protocol.rs
index f66bcdc67..6287bd4ba 100644
--- a/ergotree-interpreter/src/sigma_protocol.rs
+++ b/ergotree-interpreter/src/sigma_protocol.rs
@@ -12,7 +12,6 @@ mod dht_protocol;
 mod dlog_protocol;
 mod fiat_shamir;
 mod gf2_192;
-mod gf2_192poly;
 mod proof_tree;
 mod sig_serializer;
 mod unchecked_tree;
diff --git a/ergotree-interpreter/src/sigma_protocol/challenge.rs b/ergotree-interpreter/src/sigma_protocol/challenge.rs
index ab7967c44..15e221b56 100644
--- a/ergotree-interpreter/src/sigma_protocol/challenge.rs
+++ b/ergotree-interpreter/src/sigma_protocol/challenge.rs
@@ -10,7 +10,7 @@ use std::convert::TryInto;
 /// Challenge in Sigma protocol
 #[cfg_attr(feature = "arbitrary", derive(Arbitrary))]
 #[derive(PartialEq, Eq, Debug, Clone)]
-pub struct Challenge(FiatShamirHash);
+pub struct Challenge(pub(crate) FiatShamirHash);
 
 impl From<Challenge> for Scalar {
     fn from(v: Challenge) -> Self {
diff --git a/ergotree-interpreter/src/sigma_protocol/gf2_192.rs b/ergotree-interpreter/src/sigma_protocol/gf2_192.rs
index c86183740..3be2ba24a 100644
--- a/ergotree-interpreter/src/sigma_protocol/gf2_192.rs
+++ b/ergotree-interpreter/src/sigma_protocol/gf2_192.rs
@@ -1,19 +1,40 @@
-// TODO: remove after all todo! are implemented
-#![allow(clippy::todo)]
+use std::convert::TryFrom;
 
-use super::challenge::Challenge;
-
-#[derive(PartialEq, Debug, Clone)]
-pub(crate) struct Gf2_192 {}
+use super::{challenge::Challenge, fiat_shamir::FiatShamirHash, SOUNDNESS_BYTES};
+use gf2_192::{
+    gf2_192::Gf2_192,
+    gf2_192poly::{CoefficientsByteRepr, Gf2_192Poly},
+};
 
 impl From<Gf2_192> for Challenge {
-    fn from(_: Gf2_192) -> Self {
-        todo!()
+    fn from(e: Gf2_192) -> Self {
+        let bytes = <[u8; 24]>::from(e);
+        Challenge(FiatShamirHash(Box::new(bytes)))
     }
 }
 
 impl From<Challenge> for Gf2_192 {
-    fn from(_: Challenge) -> Self {
-        todo!()
+    fn from(c: Challenge) -> Self {
+        let bytes: [u8; SOUNDNESS_BYTES] = c.0.into();
+        Gf2_192::from(bytes)
     }
 }
+
+/// Create a `Gf2_192Poly` instance from given challenge and byte array of other coefficients.
+/// Note:
+///  - `challenge` is viewed as an element of `GF(2^192)` (see the trait impls above) and serves as
+///    the degree-zero coefficient in the resulting polynomial.
+///  - `other_coefficients` represents the other coefficients of the polynomial starting from degree
+///    one. Each coefficient is represented by slice of `[u8; 24]`.
+pub(crate) fn gf2_192poly_from_byte_array(
+    challenge: Challenge,
+    other_coefficients: Vec<u8>,
+) -> Result<Gf2_192Poly, gf2_192::Gf2_192Error> {
+    let c0 = Gf2_192::from(challenge);
+    let coeff0 = <[u8; 24]>::from(c0);
+    let cc = CoefficientsByteRepr {
+        coeff0,
+        more_coeffs: &other_coefficients,
+    };
+    Gf2_192Poly::try_from(cc)
+}
diff --git a/ergotree-interpreter/src/sigma_protocol/gf2_192poly.rs b/ergotree-interpreter/src/sigma_protocol/gf2_192poly.rs
deleted file mode 100644
index b2dd69e88..000000000
--- a/ergotree-interpreter/src/sigma_protocol/gf2_192poly.rs
+++ /dev/null
@@ -1,30 +0,0 @@
-// TODO: remove after all todo! are implemented
-#![allow(clippy::todo)]
-
-use super::challenge::Challenge;
-use super::gf2_192::Gf2_192;
-
-#[derive(PartialEq, Debug, Clone)]
-pub struct Gf2_192Poly {}
-
-impl Gf2_192Poly {
-    pub(crate) fn from_byte_array(_challenge: Challenge, _: Vec<u8>) -> Self {
-        todo!()
-    }
-
-    pub(crate) fn evaluate(&self, _idx: usize) -> Gf2_192 {
-        todo!()
-    }
-
-    pub(crate) fn interpolate(
-        _points: Vec<u8>,
-        _values: Vec<Gf2_192>,
-        _value_at_zero: Gf2_192,
-    ) -> Gf2_192Poly {
-        todo!()
-    }
-
-    pub(crate) fn to_bytes(&self) -> Vec<u8> {
-        todo!()
-    }
-}
diff --git a/ergotree-interpreter/src/sigma_protocol/prover.rs b/ergotree-interpreter/src/sigma_protocol/prover.rs
index 46e39140e..343b6e5c0 100644
--- a/ergotree-interpreter/src/sigma_protocol/prover.rs
+++ b/ergotree-interpreter/src/sigma_protocol/prover.rs
@@ -10,7 +10,7 @@ use crate::sigma_protocol::crypto_utils::secure_random_bytes;
 use crate::sigma_protocol::dht_protocol;
 use crate::sigma_protocol::fiat_shamir::fiat_shamir_hash_fn;
 use crate::sigma_protocol::fiat_shamir::fiat_shamir_tree_to_bytes;
-use crate::sigma_protocol::gf2_192poly::Gf2_192Poly;
+use crate::sigma_protocol::gf2_192::gf2_192poly_from_byte_array;
 use crate::sigma_protocol::proof_tree::ProofTree;
 use crate::sigma_protocol::unchecked_tree::UncheckedDhTuple;
 use crate::sigma_protocol::unproven_tree::CandUnproven;
@@ -22,6 +22,9 @@ use crate::sigma_protocol::UnprovenLeaf;
 use crate::sigma_protocol::SOUNDNESS_BYTES;
 use ergotree_ir::sigma_protocol::sigma_boolean::SigmaBoolean;
 use ergotree_ir::sigma_protocol::sigma_boolean::SigmaConjectureItems;
+use gf2_192::gf2_192poly::Gf2_192Poly;
+use gf2_192::gf2_192poly::Gf2_192PolyError;
+use gf2_192::Gf2_192Error;
 use std::convert::TryInto;
 use std::rc::Rc;
 
@@ -65,6 +68,9 @@ pub enum ProverError {
     /// Failed to evaluate ErgoTree
     #[error("Evaluation error: {0}")]
     EvalError(EvalError),
+    /// `gf2_192` error
+    #[error("gf2_192 error: {0}")]
+    Gf2_192Error(Gf2_192Error),
     /// Script reduced to false
     #[error("Script reduced to false")]
     ReducedToFalse,
@@ -103,6 +109,18 @@ impl From<FiatShamirTreeSerializationError> for ProverError {
     }
 }
 
+impl From<Gf2_192Error> for ProverError {
+    fn from(e: Gf2_192Error) -> Self {
+        ProverError::Gf2_192Error(e)
+    }
+}
+
+impl From<Gf2_192PolyError> for ProverError {
+    fn from(e: Gf2_192PolyError) -> Self {
+        ProverError::Gf2_192Error(Gf2_192Error::Gf2_192PolyError(e))
+    }
+}
+
 /// Prover
 pub trait Prover {
     /// Secrets of the prover
@@ -556,14 +574,16 @@ fn step4_simulated_threshold_conj(
     if let Some(challenge) = ct.challenge_opt.clone() {
         let unproven_children = cast_to_unp(ct.children.clone())?;
         let n = ct.children.len();
-        let q = Gf2_192Poly::from_byte_array(
+        let q = gf2_192poly_from_byte_array(
             challenge,
             secure_random_bytes(SOUNDNESS_BYTES * (n - ct.k as usize)),
-        );
+        )?;
         let new_children = unproven_children
             .enumerated()
             .mapped(|(idx, c)| {
-                let one_based_idx = idx + 1;
+                // Note the cast to `u8` is safe since `unproven_children` is of type
+                // `SigmaConjectureItems<_>` which is a `BoundedVec<_, 2, 255>`.
+                let one_based_idx = (idx + 1) as u8;
                 let new_challenge = q.evaluate(one_based_idx).into();
                 c.with_challenge(new_challenge)
             })
@@ -826,10 +846,12 @@ fn step9_real_threshold(ct: CthresholdUnproven) -> Result<Option<ProofTree>, Pro
         }
 
         let value_at_zero = challenge.into();
-        let q = Gf2_192Poly::interpolate(points, values, value_at_zero);
+        let q = Gf2_192Poly::interpolate(&points, &values, value_at_zero)?;
 
         let new_children = ct.children.clone().enumerated().mapped(|(idx, child)| {
-            let one_based_idx = idx + 1;
+            // Note the cast to `u8` is safe since `ct.children` is of type
+            // `SigmaConjectureItems<_>` which is a `BoundedVec<_, 2, 255>`.
+            let one_based_idx = (idx + 1) as u8;
             match &child {
                 ProofTree::UnprovenTree(ut) if ut.is_real() => {
                     child.with_challenge(q.evaluate(one_based_idx).into())
diff --git a/ergotree-interpreter/src/sigma_protocol/sig_serializer.rs b/ergotree-interpreter/src/sigma_protocol/sig_serializer.rs
index c19d583ac..4460ea031 100644
--- a/ergotree-interpreter/src/sigma_protocol/sig_serializer.rs
+++ b/ergotree-interpreter/src/sigma_protocol/sig_serializer.rs
@@ -2,6 +2,7 @@
 
 use std::convert::TryInto;
 
+use super::gf2_192::gf2_192poly_from_byte_array;
 use super::prover::ProofBytes;
 use super::unchecked_tree::UncheckedConjecture;
 use super::unchecked_tree::UncheckedLeaf;
@@ -9,7 +10,6 @@ use super::unchecked_tree::UncheckedTree;
 use super::GROUP_SIZE;
 use super::SOUNDNESS_BYTES;
 use crate::sigma_protocol::dht_protocol::SecondDhTupleProverMessage;
-use crate::sigma_protocol::gf2_192poly::Gf2_192Poly;
 use crate::sigma_protocol::unchecked_tree::UncheckedDhTuple;
 use crate::sigma_protocol::Challenge;
 use crate::sigma_protocol::GroupSizedBytes;
@@ -25,6 +25,7 @@ use ergotree_ir::sigma_protocol::sigma_boolean::SigmaConjecture;
 use ergotree_ir::sigma_protocol::sigma_boolean::SigmaProofOfKnowledgeTree;
 
 use derive_more::From;
+use gf2_192::Gf2_192Error;
 use k256::Scalar;
 use thiserror::Error;
 
@@ -214,14 +215,16 @@ fn parse_sig_compute_challenges_reader<R: SigmaByteRead>(
                 let buf_size = n_coeff * SOUNDNESS_BYTES;
                 let mut coeff_bytes = vec![0u8; buf_size];
                 r.read_exact(&mut coeff_bytes)?;
-                let polynomial = Gf2_192Poly::from_byte_array(challenge.clone(), coeff_bytes);
+                let polynomial = gf2_192poly_from_byte_array(challenge.clone(), coeff_bytes)?;
 
                 let children =
                     ct.children
                         .clone()
                         .enumerated()
                         .try_mapped_ref(|(idx, child)| {
-                            let one_based_index = idx + 1;
+                            // Note the cast to `u8` is safe since `ct.children` is of type
+                            // `SigmaConjectureItems<_>` which is a `BoundedVec<_, 2, 255>`.
+                            let one_based_index = (idx + 1) as u8;
                             let ch = polynomial.evaluate(one_based_index).into();
                             parse_sig_compute_challenges_reader(child, r, Some(ch))
                         })?;
@@ -240,6 +243,9 @@ fn parse_sig_compute_challenges_reader<R: SigmaByteRead>(
 /// Errors when parsing proof tree signatures
 #[derive(Error, PartialEq, Eq, Debug, Clone, From)]
 pub enum SigParsingError {
+    /// `gf2_192` error
+    #[error("gf2_192 error: {0}")]
+    Gf2_192Error(Gf2_192Error),
     /// IO error
     #[error("IO error: {0}")]
     IoError(String),
diff --git a/ergotree-interpreter/src/sigma_protocol/unchecked_tree.rs b/ergotree-interpreter/src/sigma_protocol/unchecked_tree.rs
index 93f60689e..fc070a507 100644
--- a/ergotree-interpreter/src/sigma_protocol/unchecked_tree.rs
+++ b/ergotree-interpreter/src/sigma_protocol/unchecked_tree.rs
@@ -5,10 +5,10 @@ use ergotree_ir::sigma_protocol::sigma_boolean::ProveDlog;
 use ergotree_ir::sigma_protocol::sigma_boolean::SigmaBoolean;
 use ergotree_ir::sigma_protocol::sigma_boolean::SigmaConjectureItems;
 use ergotree_ir::sigma_protocol::sigma_boolean::SigmaProofOfKnowledgeTree;
+use gf2_192::gf2_192poly::Gf2_192Poly;
 
 use super::dht_protocol::FirstDhTupleProverMessage;
 use super::dht_protocol::SecondDhTupleProverMessage;
-use super::gf2_192poly::Gf2_192Poly;
 use super::proof_tree::ConjectureType;
 use super::proof_tree::ProofTree;
 use super::proof_tree::ProofTreeConjecture;
diff --git a/ergotree-interpreter/src/sigma_protocol/unproven_tree.rs b/ergotree-interpreter/src/sigma_protocol/unproven_tree.rs
index a6a71a938..c2dae8450 100644
--- a/ergotree-interpreter/src/sigma_protocol/unproven_tree.rs
+++ b/ergotree-interpreter/src/sigma_protocol/unproven_tree.rs
@@ -1,7 +1,6 @@
 //! Unproven tree types
 
 use super::dht_protocol::FirstDhTupleProverMessage;
-use super::gf2_192poly::Gf2_192Poly;
 use super::proof_tree::ConjectureType;
 use super::proof_tree::ProofTree;
 use super::proof_tree::ProofTreeConjecture;
@@ -16,6 +15,7 @@ use ergotree_ir::sigma_protocol::sigma_boolean::ProveDlog;
 use ergotree_ir::sigma_protocol::sigma_boolean::SigmaBoolean;
 use ergotree_ir::sigma_protocol::sigma_boolean::SigmaConjectureItems;
 use ergotree_ir::sigma_protocol::sigma_boolean::SigmaProofOfKnowledgeTree;
+use gf2_192::gf2_192poly::Gf2_192Poly;
 use k256::Scalar;
 
 extern crate derive_more;
diff --git a/gf2_192/Cargo.toml b/gf2_192/Cargo.toml
new file mode 100644
index 000000000..12ee450d6
--- /dev/null
+++ b/gf2_192/Cargo.toml
@@ -0,0 +1,15 @@
+[package]
+name = "gf2_192"
+version = "0.14.0"
+license = "CC0-1.0"
+authors = ["Timothy Ling (@kettlebell)"]
+description = "Arithmetic operations and polynomial interpolation over Galois fields GF(2^192)"
+repository = "https://github.com/ergoplatform/sigma-rust"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
+derive_more = "0.99"
+rand = "0.8.4"
+thiserror = "1"
diff --git a/gf2_192/src/gf2_192.rs b/gf2_192/src/gf2_192.rs
new file mode 100644
index 000000000..d81aaaf06
--- /dev/null
+++ b/gf2_192/src/gf2_192.rs
@@ -0,0 +1,1042 @@
+//!  By Leonid Reyzin
+//!  This is free and unencumbered software released into the public domain.
+//!
+//!  Anyone is free to copy, modify, publish, use, compile, sell, or
+//!  distribute this software, either in source code form or as a compiled
+//!  binary, for any purpose, commercial or non-commercial, and by any
+//!  means.
+//!
+//!  In jurisdictions that recognize copyright laws, the author or authors
+//!  of this software dedicate any and all copyright interest in the
+//!  software to the public domain. We make this dedication for the benefit
+//!  of the public at large and to the detriment of our heirs and
+//!  successors. We intend this dedication to be an overt act of
+//!  relinquishment in perpetuity of all present and future rights to this
+//!  software under copyright law.
+//!
+//!  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+//!  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+//!  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+//!  IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
+//!  OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
+//!  ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+//!  OTHER DEALINGS IN THE SOFTWARE.
+//!
+//!  For more information, please refer to <http://unlicense.org>
+
+use crate::{lrs_i64, lrs_i8, Gf2_192Error};
+
+/// using irreducible polynomial x^192+x^7+x^2+x+1
+/// We need only the last word
+static IRRED_PENTANOMIAL: i64 = (1i64 << 7) | (1i64 << 2) | (1i64 << 1) | 1i64;
+
+/// IRRED_PENTANOMIAL times 0, 1, x, x+1, x^2, x^2+1, x^2+x, x^2+x+1, x^3, x^3+1, x^3+x, x^3+x+1, x^3+x^2, x^3+x^2+1, x^3+x^2+x, x^3+x^2x+1.
+/// Need only the last word, because the leading two words are 0
+static IRRED_MULS: [i64; 16] = [
+    0i64,
+    IRRED_PENTANOMIAL,
+    IRRED_PENTANOMIAL << 1,
+    (IRRED_PENTANOMIAL << 1) ^ IRRED_PENTANOMIAL,
+    IRRED_PENTANOMIAL << 2,
+    (IRRED_PENTANOMIAL << 2) ^ IRRED_PENTANOMIAL,
+    (IRRED_PENTANOMIAL << 2) ^ (IRRED_PENTANOMIAL << 1),
+    (IRRED_PENTANOMIAL << 2) ^ (IRRED_PENTANOMIAL << 1) ^ IRRED_PENTANOMIAL,
+    IRRED_PENTANOMIAL << 3,
+    (IRRED_PENTANOMIAL << 3) ^ IRRED_PENTANOMIAL,
+    (IRRED_PENTANOMIAL << 3) ^ (IRRED_PENTANOMIAL << 1),
+    (IRRED_PENTANOMIAL << 3) ^ (IRRED_PENTANOMIAL << 1) ^ IRRED_PENTANOMIAL,
+    (IRRED_PENTANOMIAL << 3) ^ (IRRED_PENTANOMIAL << 2),
+    (IRRED_PENTANOMIAL << 3) ^ (IRRED_PENTANOMIAL << 2) ^ IRRED_PENTANOMIAL,
+    (IRRED_PENTANOMIAL << 3) ^ (IRRED_PENTANOMIAL << 2) ^ (IRRED_PENTANOMIAL << 1),
+    (IRRED_PENTANOMIAL << 3)
+        ^ (IRRED_PENTANOMIAL << 2)
+        ^ (IRRED_PENTANOMIAL << 1)
+        ^ IRRED_PENTANOMIAL,
+];
+
+/// Represents an element of the Galois field GF(2^192)
+#[derive(PartialEq, Eq, Copy, Clone, Debug)]
+pub struct Gf2_192 {
+    word: [i64; 3],
+}
+
+impl Gf2_192 {
+    /// Returns the 0 field element
+    pub fn new() -> Self {
+        Gf2_192 { word: [0, 0, 0] }
+    }
+
+    /// Returns true iff `Self == 0`
+    pub fn is_zero(&self) -> bool {
+        self.word[0] == 0 && self.word[1] == 0 && self.word[2] == 0
+    }
+
+    /// Returns true iff `Self == 1`
+    pub fn is_one(&self) -> bool {
+        self.word[0] == 1 && self.word[1] == 0 && self.word[2] == 0
+    }
+
+    /// Computes a times b.
+    /// Uses table lookups, which may not preserve the secrecy of the inputs in case of side-channel
+    /// attacks.
+    pub fn multiply(a: Gf2_192, b: Gf2_192) -> Gf2_192 {
+        // Implements a sort of times-x-and-add algorithm, except instead of multiplying by x
+        // we multiply by x^4 and then add one of possible 16 precomputed values
+
+        // contains a*0, a*1, a*x, a*(x+1), a*x^2, a*(x^2+1), a*(x^2+x), a*(x^2+x+1)
+        // a*x^3, a*(x^3+1), a*(x^3+x), a*(x^3+x+1), a*(x^3+x^2), a*(x^3+x^2+1), a*(x^3+x^2+x), a*(x^3+x^2+x+1), all mod reduced
+        // First word of each is in a0 muls, second word of each is in a1muls, third word of each is in a2muls
+        let mut a0muls: [i64; 16] = Default::default();
+        let mut a1muls: [i64; 16] = Default::default();
+        let mut a2muls: [i64; 16] = Default::default();
+
+        // a0muls[0], a1muls[0] and a2muls[0] are already correctly initialized to 0
+
+        a0muls[1] = a.word[0];
+        a1muls[1] = a.word[1];
+        a2muls[1] = a.word[2];
+
+        // a*x, a*x^2, a*x^3
+        for i in [2, 4, 8] {
+            // multiply a*x^{log_2 i/2} by x to get a*x^{log_2 i}
+            let prev = i / 2;
+            a0muls[i] = a0muls[prev] << 1;
+            a1muls[i] = (a1muls[prev] << 1) | lrs_i64(a0muls[prev], 63);
+            a2muls[i] = (a2muls[prev] << 1) | lrs_i64(a1muls[prev], 63);
+            // mod reduce
+            a0muls[i] ^= IRRED_MULS[lrs_i64(a2muls[prev], 63) as usize];
+        }
+
+        // a*(x+1)
+        a0muls[3] = a0muls[1] ^ a0muls[2];
+        a1muls[3] = a1muls[1] ^ a1muls[2];
+        a2muls[3] = a2muls[1] ^ a2muls[2];
+
+        // a*(x^2+1), a*(x^2+x), a*(x^2+x+1)
+        for i in 1..4 {
+            a0muls[4 | i] = a0muls[4] ^ a0muls[i];
+            a1muls[4 | i] = a1muls[4] ^ a1muls[i];
+            a2muls[4 | i] = a2muls[4] ^ a2muls[i];
+        }
+
+        // a*(x^3+1), a*(x^3+x), a*(x^3+x+1), a*(x^3+x^2), a*(x^3+x^2+1), a*(x^3+x^2+x), a*(x^3+x^2+x+1)
+        for i in 1..8 {
+            a0muls[8 | i] = a0muls[8] ^ a0muls[i];
+            a1muls[8 | i] = a1muls[8] ^ a1muls[i];
+            a2muls[8 | i] = a2muls[8] ^ a2muls[i];
+        }
+
+        let mut w0 = 0;
+        let mut w1 = 0;
+        let mut w2 = 0;
+
+        for j in (0..=2).rev() {
+            let multiplier = b.word[j];
+            for i in (0..=60).rev().step_by(4) {
+                // Multiply by x^4
+                let mod_reduce_index = lrs_i64(w2, 60) as usize;
+                w2 = (w2 << 4) | lrs_i64(w1, 60);
+                w1 = (w1 << 4) | lrs_i64(w0, 60);
+                // MOD REDUCE ACCORDING TO mod_reduce_index by XORing the right value
+                w0 = (w0 << 4) ^ IRRED_MULS[mod_reduce_index];
+                //w0 = (w0<<4)^(IRRED_PENTANOMIAL*(mod_reduce_index&8))^(IRRED_PENTANOMIAL*(mod_reduce_index&4))^(IRRED_PENTANOMIAL*(mod_reduce_index&2))^(IRRED_PENTANOMIAL*(mod_reduce_index&1));
+
+                // Add the correct multiple of a
+                let index = (lrs_i64(multiplier, i) & 15) as usize;
+                w0 ^= a0muls[index];
+                w1 ^= a1muls[index];
+                w2 ^= a2muls[index];
+            }
+        }
+        Gf2_192 { word: [w0, w1, w2] }
+    }
+
+    /// Computes a times b. More efficient than `mul`
+    pub fn mul_by_i8(a: Gf2_192, b: i8) -> Gf2_192 {
+        let mut w0 = 0;
+        let mut w1 = 0;
+        let mut w2 = 0;
+
+        for i in (0..=7).rev() {
+            let w3 = lrs_i64(w2, 63);
+            w2 = (w2 << 1) | lrs_i64(w1, 63);
+            w1 = (w1 << 1) | lrs_i64(w0, 63);
+            w0 <<= 1;
+            let t = (lrs_i8(b, i) & 1) as i64;
+            w2 ^= a.word[2] * t;
+            w1 ^= a.word[1] * t;
+            w0 ^= (a.word[0] * t) ^ (IRRED_PENTANOMIAL * w3); // mod reduce
+        }
+        Gf2_192 { word: [w0, w1, w2] }
+    }
+
+    /// Compute multiplicative inverse `1/Self`.
+    pub fn invert(z: Gf2_192) -> Gf2_192 {
+        // Computes z^{2^192-2} = z^{exponent written in binary as 191 ones followed by a single zero}
+        // (by Fermat's little theorem, this is the correct inverse)
+
+        // contains z raised to the power whose binary representation is 2^k ones
+        let mut z_to_2_to_k1s = z;
+
+        // Square res to get its exponent to be 10 in binary
+        let mut res = z * z;
+
+        // contains z raised to the power whose binary representation is 2^k ones followed by 2^k zeros
+        let mut z_to_2_to_k1s_2_to_k0s = res;
+
+        let mut k = 0;
+        while k < 6 {
+            k += 1;
+            // Fill in the zeros in the exponent of z_to_2_to_k1s_2_to_k0s with ones
+            z_to_2_to_k1s = z_to_2_to_k1s_2_to_k0s * z_to_2_to_k1s;
+            // z_to_2_to_k1s_2_to_k0s = power_2_to_2_to_k with 2^k zeros appended to the exponent
+            z_to_2_to_k1s_2_to_k0s = Gf2_192::power_2_to_2_to_k(z_to_2_to_k1s, k);
+            // prepend 2^k ones to res
+            res = res * z_to_2_to_k1s_2_to_k0s;
+        }
+        z_to_2_to_k1s_2_to_k0s = Gf2_192::power_2_to_2_to_k(z_to_2_to_k1s_2_to_k0s, k);
+        res * z_to_2_to_k1s_2_to_k0s
+    }
+
+    /// Squares z. Same as `power_2_to_2_to_k(z, 0)`. About same efficiency as mul(res, z, z) (more
+    /// efficient implementations are possible, but not provided here because of risk of
+    /// side-channel attacks)
+    pub fn sqr(z: Gf2_192) -> Gf2_192 {
+        Gf2_192::power_2_to_2_to_k(z, 0)
+    }
+
+    /// Raises z to the power 2^{2^k}. Same `sqr(z, z)` 2^k times.
+    /// Takes only about as much time as mul(z, z) (even more efficient implementations are possible,
+    /// but not provided here because of risk of side-channel attacks)
+    pub fn power_2_to_2_to_k(z: Gf2_192, k: usize) -> Gf2_192 {
+        if k >= 7 {
+            // By Fermat's little theorem, z^{2^{2^k}} = z^{2^{2^k} mod (2^{192}-1)}
+            // If k>=7, then 2^{2^k} mod (2^{192}-1) = 2^64 when k is even and 2^128 when k is odd (proof below),
+            // so that's what we compute.
+            // Note that we have no precomputed table for k=7 (i.e., 2^128), because we don't expect
+            // this to be needed -- only up to k=6 is used in inversion.
+            // Here's the proof: let m = 64. 2^{2^k} mod (2^{192}-1) = 2^{mn} mod (2^{3m}-1) for n = 2^{k-6}.
+            // Let d = n div 3 and r = n mod 3.
+            // Then 2^{mn} = (2^{3m}-1) (2^{m(n-3}}+2^{m(n-6)}+...+2^{m-nd})+2^{nr}
+            // So the remainder is 2^{nr}. r is 2 when k is odd and 1 when k is even.
+
+            let res = Gf2_192::power_2_to_2_to_k(z, 6);
+            if k % 2 == 1 {
+                Gf2_192::power_2_to_2_to_k(res, 6)
+            } else {
+                res
+            }
+        } else {
+            // powTable0[k][i] contains the result of raising x^i to the power 2^k for i = 0...63
+            // powTable0[k][i-64] contains the result of raising x^i to the power 2^k for i = 64...127
+            // powTable0[k][i-128] contains the result of raising x^i to the power 2^k for i = 128...191
+            // Because raising to the power 2^k is linear over any field of characteristic 2,
+            // we just need to XOR the values in these tables at indices i where z is 1.
+            // This selection is done via multiplication by 0 or 1, to avoid having an input-dependent path
+            // through the code, thus reducing the chance of side-channel attacks.
+            //
+            // Note that more efficient tables can be precomputed -- for example, the result of raising
+            // every one of 16 possible 4-bit nibbles at every one of 32 possible nibble positions.
+            // But indexing into these tables will be input-dependent, which may make side-channel attacks easier.
+
+            let mut t0 = 0;
+            let mut t1 = 0;
+            let mut t2 = 0;
+            let mut max_index: usize = 0;
+            let mut i = 0;
+            for mut w in z.word {
+                max_index += 64;
+                while i < max_index {
+                    let multiplier = w & 1;
+                    // No "if w&1 == 0" here, to avoid a data-dependent path through the code,
+                    // thus reducing the chance of side channel attacks
+                    t0 ^= POW_TABLE_0[k][i] * multiplier;
+                    t1 ^= POW_TABLE_1[k][i] * multiplier;
+                    t2 ^= POW_TABLE_2[k][i] * multiplier;
+                    w = lrs_i64(w, 1);
+                    i += 1;
+                }
+            }
+            Gf2_192 { word: [t0, t1, t2] }
+        }
+    }
+
+    /// Write out byte representation to the given `slice` at position `pos`.
+    pub fn to_i8_slice(&self, slice: &mut [i8], pos: usize) -> Result<(), Gf2_192Error> {
+        if slice.len() < pos + 24 {
+            return Err(Gf2_192Error::Gf2_192ToByteArrayError);
+        }
+        for j in 0..3 {
+            for i in 0..8 {
+                slice[pos + i + 8 * j] = ((self.word[j] >> (i << 3)) & 0xFF) as i8;
+            }
+        }
+        Ok(())
+    }
+}
+
+impl Default for Gf2_192 {
+    /// Returns the 0 field element
+    fn default() -> Self {
+        Self::new()
+    }
+}
+
+impl std::ops::Add for Gf2_192 {
+    type Output = Self;
+    fn add(self, rhs: Self) -> Self {
+        let mut word = [0, 0, 0];
+        word[0] = self.word[0] ^ rhs.word[0];
+        word[1] = self.word[1] ^ rhs.word[1];
+        word[2] = self.word[2] ^ rhs.word[2];
+        Gf2_192 { word }
+    }
+}
+
+impl std::ops::Mul for Gf2_192 {
+    type Output = Self;
+
+    fn mul(self, rhs: Self) -> Self {
+        Gf2_192::multiply(self, rhs)
+    }
+}
+
+impl From<[i64; 3]> for Gf2_192 {
+    fn from(word: [i64; 3]) -> Self {
+        Gf2_192 { word }
+    }
+}
+
+impl From<Gf2_192> for [i64; 3] {
+    fn from(e: Gf2_192) -> Self {
+        e.word
+    }
+}
+
+impl From<Gf2_192> for [u8; 24] {
+    fn from(e: Gf2_192) -> Self {
+        let mut bytes: [u8; 24] = Default::default();
+        for j in 0..3 {
+            for i in 0..8 {
+                bytes[i + 8 * j] = ((e.word[j] >> (i << 3)) & 0xFF) as u8;
+            }
+        }
+        bytes
+    }
+}
+
+impl From<Gf2_192> for [i8; 24] {
+    fn from(e: Gf2_192) -> Self {
+        let mut bytes: [i8; 24] = Default::default();
+        for j in 0..3 {
+            for i in 0..8 {
+                bytes[i + 8 * j] = ((e.word[j] >> (i << 3)) & 0xFF) as i8;
+            }
+        }
+        bytes
+    }
+}
+
+impl From<i32> for Gf2_192 {
+    /// Returns an instance whose 32 least significant bits are bits of that and rest are 0
+    fn from(value: i32) -> Self {
+        Gf2_192 {
+            word: [(value as i64) & 0xFFFFFFFF, 0, 0],
+        }
+    }
+}
+
+impl<'a> TryFrom<&[i8]> for Gf2_192 {
+    type Error = Gf2_192Error;
+
+    fn try_from(value: &[i8]) -> Result<Self, Self::Error> {
+        if value.len() < 24 {
+            return Err(Gf2_192Error::Gf2_192TryFromByteArrayError);
+        }
+        let mut word: [i64; 3] = [0, 0, 0];
+        for i in 0..8 {
+            word[0] |= (value[i] as i64 & 0xFF) << (i << 3);
+            word[1] |= (value[i + 8] as i64 & 0xFF) << (i << 3);
+            word[2] |= (value[i + 16] as i64 & 0xFF) << (i << 3);
+        }
+        Ok(Gf2_192 { word })
+    }
+}
+
+impl<'a> TryFrom<&[u8]> for Gf2_192 {
+    type Error = Gf2_192Error;
+
+    fn try_from(value: &[u8]) -> Result<Self, Self::Error> {
+        if value.len() < 24 {
+            return Err(Gf2_192Error::Gf2_192TryFromByteArrayError);
+        }
+        let mut word: [i64; 3] = [0, 0, 0];
+        for i in 0..8 {
+            word[0] |= (value[i] as i64 & 0xFF) << (i << 3);
+            word[1] |= (value[i + 8] as i64 & 0xFF) << (i << 3);
+            word[2] |= (value[i + 16] as i64 & 0xFF) << (i << 3);
+        }
+        Ok(Gf2_192 { word })
+    }
+}
+
+impl From<[u8; 24]> for Gf2_192 {
+    fn from(bytes: [u8; 24]) -> Self {
+        let mut word: [i64; 3] = [0, 0, 0];
+        for i in 0..8 {
+            word[0] |= (bytes[i] as i64 & 0xFF) << (i << 3);
+            word[1] |= (bytes[i + 8] as i64 & 0xFF) << (i << 3);
+            word[2] |= (bytes[i + 16] as i64 & 0xFF) << (i << 3);
+        }
+        Gf2_192 { word }
+    }
+}
+
+impl From<[i8; 24]> for Gf2_192 {
+    fn from(bytes: [i8; 24]) -> Self {
+        let mut word: [i64; 3] = [0, 0, 0];
+        for i in 0..8 {
+            word[0] |= (bytes[i] as i64 & 0xFF) << (i << 3);
+            word[1] |= (bytes[i + 8] as i64 & 0xFF) << (i << 3);
+            word[2] |= (bytes[i + 16] as i64 & 0xFF) << (i << 3);
+        }
+        Gf2_192 { word }
+    }
+}
+
+#[rustfmt::skip]
+static POW_TABLE_0: [[i64; 192]; 7] = [
+[1,4,16,64,256,1024,4096,16384,65536,262144,1048576,4194304,16777216,67108864,268435456,1073741824,4294967296,17179869184,68719476736,274877906944,1099511627776,4398046511104,17592186044416,70368744177664,281474976710656,1125899906842624,4503599627370496,18014398509481984,72057594037927936,288230376151711744,1152921504606846976,4611686018427387904,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,135,540,2160,8640,34560,138240,552960,2211840,8847360,35389440,141557760,566231040,2264924160,9059696640,36238786560,144955146240,579820584960,2319282339840,9277129359360,37108517437440,148434069749760,593736278999040,2374945115996160,9499780463984640,37999121855938560,151996487423754240,607985949695016960,2431943798780067840,-8718968878589280256,2017612633061982208,8070450532247928832,-4611686018427387904,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,270,1080,4199,],
+[1,16,256,4096,65536,1048576,16777216,268435456,4294967296,68719476736,1099511627776,17592186044416,281474976710656,4503599627370496,72057594037927936,1152921504606846976,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,135,2160,34560,552960,8847360,141557760,2264924160,36238786560,579820584960,9277129359360,148434069749760,2374945115996160,37999121855938560,607985949695016960,-8718968878589280256,8070450532247928832,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1080,16405,262480,4199680,67194880,1075118080,17201889280,275230228480,4403683655680,70458938490880,1127343015854080,18037488253665280,288599812058644480,4617596992938311680,94575592174780416,1513209474796486656,5764607523034234880,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,540,8640,138375,2214635,35434160,566946560,9071144960,145138319360,2322213109760,37155409756160,594486556098560,9511784897576960,152188558361231360,2435016933779701760,2066782793056124928,-3824963458521104384,-5859183115209015296,-1513209474796486656,-5764607523034234880,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,270,4199,65620,1048694,16777290,],
+[1,65536,4294967296,281474976710656,0,0,0,0,0,0,0,0,135,8847360,579820584960,37999121855938560,0,0,0,0,0,0,0,0,16405,1075118080,70458938490880,4617596992938311680,0,0,0,0,0,0,0,0,2214635,145138319360,9511784897576960,-3824963458521104384,0,0,0,0,0,0,0,4199,268435729,17592203935744,1152922677132918784,76842668642009088,0,0,0,0,0,0,0,552960,36238823415,2374947531325440,8070608823267622912,-8072983807038324736,0,0,0,0,0,0,1080,67194880,4403688133701,288600105530228736,5783840476780036096,6072259672578981888,0,0,0,0,0,0,138375,9071137756,594486085783387,2066751970480947200,-7784595809881817088,-8116893903405187072,0,0,0,0,0,270,16777290,1099511627845,72057594037993729,4311810048,282578783305728,72339069014638592,0,0,0,0,0,34560,2264924160,148434069749895,-8718968878580398201,582094356480,38148135746273280,-8680969756733341696,0,0,0,0,0,4199680,275230228480,18037488253681685,1513209475875820821,70735243837440,4635704940130467840,6130806467734798336,0,0,0,0,8640,566946560,37155409756160,2435016933781924651,-1513209329119911445,9547060033028096,-1513172181595455488,2444047222778626048,0,0,0,0,1048694,68719546624,4503604207554663,300166943871232,1224996759836561425,1157443864920915968,1229500363472633856,1157706579210928128,0,0,0,2160,141557895,9277138794240,607986568019867760,40522537422618480,-646134085450172169,8680969174647242752,-38147594580393984,8716435603798884352,0,0,0,262480,17201906733,1127344162226488,94650720833590632,4923631783780892776,4685244537110860101,6130877201840930816,4635630379498209280,1244400872037810176,0,0,540,35434160,2322211272620,152188437960410523,-5867073703402003989,-608753751841641685,5021550739930207323,2435017087666290688,-1503124363304501248,-3144919914788159488,0,0,65620,4294967417,281474976710691,16,118,65641,],
+[1,0,0,268435729,0,0,72057594037993729,0,8640,1224996759836561425,0,2322211272620,4295032833,0,-3824963458521104384,1152940269605290257,67194880,-8116893903405048697,72340168543043841,18037488253681685,2444084377648024256,1152940269335812193,4923631783780892776,8706684044243276764,575525617665,0,2214635,6917686146403139857,0,594486068876182,109923151000961281,0,-1508668585977835444,-42651198216466415,17201907249,-1503124363304500630,37718226699878401,4617597137004134400,-3834029160147512970,-79200059939786479,5542457468742751288,72653179618366162,-8718686828065942650,6157755589565773013,-427524231241125731,-7636548200255303383,2349380831670242920,-1503122247285515780,1,16405,36240966940,268435729,4403688133701,-8718374392512378660,72057594037993729,1513209475874772323,2019996756866529500,1224996759976022166,4684963044965832011,5021552416478667632,37999126150971393,4684939972385783829,-4989366934530337413,-6920043528899271987,72339069031416121,-8680822410973408226,-6391613922127811155,1153203052884328721,5891559298491384716,-7528422813418094127,35172261,-608824726141909180,575525617798,9441498026213649,3487211355411353591,6917686182105090782,-4416945885376472588,6063073012436278090,-8753160638328035514,-5605497289716500368,-5610075583180945114,90149276037394458,339026464814167628,369965729453364929,-3860411569319034860,-7219661873698413202,-7217141859998432150,1806743557951716919,-8790878027314019100,-8686366285709925551,-9018771827274447141,-3500033589960484657,-6239661070421212278,-7022774006793486301,-5486222289147287496,6557835543537224962,1,4403688117328,268435729,268435729,1513213877407514960,72057594037993729,72057594179551622,6054338822752200080,1224996759836570065,1262995881831960726,4685176399308498684,2326506170314,-8110982924599230463,-7012597109688626096,-2672024288427437773,1760926221464557073,-8193431732091728425,-8188932805459047229,-702248183304599069,2358520128326754357,3596724480578929564,2653562374675748729,7558329885135416404,8706684602589025248,611764439881,-4354323463508992325,6917686146405354490,-1801282968903807655,9071577101557338822,109381790017557217,8696092877002101742,-4668327226503048164,1475308329743286364,128146801688724317,-8390330629760215797,-1531869438861569413,-4617320090730090391,5541920254930687988,3761689569789112577,-2327319826622658605,-6182158405047794621,-41970731974321979,-4950437438052009930,-3752274221890333889,1476151931308439890,5613176216134850767,289726897646273736,-1503122247017080678,594453066058452,4437244711257,72057630278829085,7782810071065752468,-7925740857026315255,-7637528022863553386,-3839220191352824283,6705067445074182019,6637312287860931618,-2154173082950753382,-8117068327749574457,4645236792527042077,3567261728918198996,-1570715894964224286,3851762367547029496,-1282481202581286367,604372413954671920,7336273916715742398,8984291365106642911,-3520346153016046579,-3001672072993760708,5487223282412062341,3220238017403266817,-7526201328351032492,-6651737113209978849,-876842992662428725,2730222910065286284,4666291884953713058,27885208784216435,-3464689086048100177,9074463908856611112,6089525621414736771,-344374184071824754,-4138339726157814851,90460192285484837,7003316425532605053,2325362866034789830,6377579351440235774,-5484290407194710110,3204252260295655770,4952583157325034207,-8782555314696362611,-2316049681279009322,-1127600795797440159,7751601582170687883,-6463181785702448409,7121056025054547704,6485777949499231279,],
+[1,-3006172399682371634,2600966637154804214,8641,8525113116679455864,-2145144163292000430,2019996756799457565,-1850476282776554867,-4889822090580977265,909561413152654253,-25001132819151504,7726439241120171362,7303489125464870298,4332131768403656981,2962048663402138678,-2892279489278463047,-4733651509025142792,1063143929388429494,-1197895461363724390,3525840681984842667,-4695277565342099683,5146529997701558317,7435951619486932058,-2724786844429777139,40504930336318985,876946985023164340,5608484252067120944,-6816077621382648259,-4033654809715777901,-4081572395912436435,-8636364450456842826,7120123665156854152,-2739360841521830815,4179210361336297309,-5035580621240300693,5024856697532411216,-5583726119146644383,1447126495187071743,-2586987284404803098,8837846401203718243,6684981609574125625,1540466829568951558,-4848578993616133096,531411902399629160,-8097992882751386397,5836923291160128631,2657822116024759531,5082038816076700909,7237486007293790522,5252165852497928096,-6943891580396708852,-2358876157997055033,2004344792661408502,6922719691033397220,-6115771057843578790,-882977230851385180,4445218069992821756,5905786485590667688,-8952895028275913749,6335857422495481096,-1336747599306330073,-295017526585807725,6427842712075527612,6136969228259728187,8790718804228268581,-7649524091336109629,-5994405249073919640,4313678309655720149,1583534994170157977,5606445082714174951,6853837681080604556,-8485637026077231303,7790525872849806729,5940658092022763209,8602473577714766584,2936249914771413453,-5521212179187796747,4711968172455986094,-4922856425548406499,130141881968551392,3536227681426168034,1538274929948045556,2319096648797621624,-390137264770768181,8029329512101034001,-7020589058068074770,3265911137432880136,8114665243288440240,1727024161912275448,7211866768629281013,-3130723513389854793,-7216856759928143716,3533195878158403511,3984449705890310687,-8379049565896909567,-8388101802220698225,-1001505570555522767,-2621811112096768870,603025228237669646,-4855786637640829169,-8861801597506211630,5171117103964917160,-6016899467464669218,574486107801798403,1346751909104125183,6265319601178024276,3065092470199993307,-3544361000120591516,-6311655751958887780,5850322626671860616,-2175699856332693179,2849507709866937883,-5020421862032512214,-4568858551591370457,-2431265188066595845,-8732538833975482925,49029378622487761,948188484528056399,685766231005340987,-6108229294291709748,-6619503736528295873,2499319692519687998,-8241104250166498648,-6283823462790380478,-1799922584861092054,-6240401189323759144,5497064944286443280,6723566846653152186,-7200823809060633542,-8991399666593498102,3696845228942259783,5525150667579715560,949595271893899961,4431634865357028469,-7719973862985677490,-6034475957088628470,-4268733492881789978,6756633516157056278,-1957554544632307580,7121101677918762223,-2926994538817486764,5070148293018691908,-3164346027824263021,-8065527601021753218,-7393579279100902671,1578925030408104064,-5470498100570909442,-9059484745764947078,8728828886428453065,876414647339389056,-4691346483920214801,271068101201614328,-1328948676306083414,-601927494426833593,-1580410200329916588,-4326051892200391110,5551955200782384943,214408676534699021,892732170117421280,-6779792031755998944,8533716818059729780,873315600166044946,8844237596764485904,4304845159865160138,5606488036825769410,425090181770096226,-1135909175464444990,-4725116773226449403,5897643684611700155,1650595387261410562,-7317473568888247260,-8317376280642525522,524782793988048123,-6713202495631135192,-4939556292506913402,-5609869695293186861,-4230589026387944683,-724065909912518572,-2110301323783658314,1029673643630214818,-5297873999180537788,-8928073349900829853,7277641038077141425,6527157727335254212,-3946003823558145331,8063768130289328687,4522053259152859193,675627983587702560,-1137165482193899852,8414663288495567717,-8436820189876267996,7876837133135388570,],
+[1,-5169860002514781635,-2589809952505784534,8777364680166470481,-8830656417429304044,3176782973934494582,109797415759816827,1076956885061792565,7914398690249482831,8011904680480159185,8410793115243855507,6266439534501642392,-336875557465114730,4038138302048025623,-8101148793053570270,1124933003446523927,8391412732637477197,2199881538445059432,719775327569887587,-4825086212853447750,-7314323185577824224,4891665885256984545,7598126349271893834,-3239373303059569532,-659203789875424936,7692138112394859210,-193023354580355438,1661409395237152970,-867709405024660660,-4774852438416084051,1013518333030173816,3485843496410831696,188315317670329959,-7626348485928744434,4785373727715537048,-2557360640145528783,815573462730278215,2725495643400585416,763815832452911292,-1234416280134845253,3031628907175299520,6164952807644926203,-6906157987463386683,8750285495619286011,-2944268397760272112,-8571087382226582932,7349937386463951048,7786267339579184516,337223540666190292,1366638621193514276,5979097440737272663,-8229072190234731287,-7464767416008336370,2196188713781264658,-6606956754260663431,8497668204436713713,7806277383834821447,591641631205476095,6045490875774248095,456224709346991991,-7218871130131209394,580163022797824109,-3693397793970743538,-1855672627986562453,1785325366189117080,-5612555377205332105,-294341367983285122,2445160339032774813,7132278192002140706,878326058396851309,3921174184439993950,5853022697017928950,-2825405099755624515,-7030859599219471492,-8473806211642996024,-8498195465917087535,-4182645819142121229,726866375401350017,-4123860299531460321,67135272333132065,238539200704091067,9069168069279185101,-8554967853203633945,-1798135605252717890,-359730572749547446,4493519132539194015,4958647882027071589,-911149761898967393,-5156659928190548061,1295304005530223213,-6977343558102121156,6922621878872799870,6666583055979266042,7292171483456095852,-1969457853973942746,-6898392144047603629,5756338153240882170,6504592230467093280,169954543499997878,8244762795686741102,-7702335274149853320,170612181012260678,-1167924627447415726,6330133554527618692,-670458599026908667,-5475429905606927886,-4407322762187867157,-8580599370684241560,3285212811372363965,7894963086517678484,8569304869073834915,-6544807253825008820,-5996237358893605511,-3042468804887085356,2374190430796422836,3894653610967932827,3898642019578338045,-5362019755573200863,4402246476084717913,3291977739464152007,3674469931224113236,-44278192132845207,-146130534644405364,5382065438553845456,6785308159791913441,4538149016807450869,8422045206362267535,-751406355315423454,8999771730341663411,-990169186945997877,1777800203227879507,-4856230533325857618,6591273902673649307,4756065680746518619,-8504746896788247085,4474109455375415963,7512977545114097664,-4994667515641620176,-4624712674055432963,-7581435093848090518,-3374583368016299959,-6772163028506140599,-4597352927609652442,7074576231879668500,8699761606660221174,-1460827062303528567,8015141181709918285,-1169566320418753181,-4781112204804977330,1888326456844245676,8052564071464611668,8677658026519325509,8196795344534159240,-6189127939919551760,-756836619992549632,3275904360037766197,8063439441889441129,-7331287930982412507,5909316323417099098,7555764543220595192,5975647989155847506,3542169932787954825,3572787110578921974,-4910033269362933281,4127048709984103372,-8249546761957136187,2136513283148217767,6914147571605817471,-1401967832836965144,8407424200159619086,3198875950909199105,2570623872214327259,6598776223519113019,-8548723600459949403,1542874467657402904,5132064706814079464,-8697292868739094825,7457266453233910833,-1093418532865160497,3247028061820159553,-1424542897552112257,5068257691790424406,5880873780866162489,-3102632713002543235,1263997674554416274,5364397535996490566,-6980107079961147736,-3471995143361337385,6641708940048027257,1135429108619021836,5387343206428796059,-6804247660018484977,],
+[1,1073223059898794450,-2038813369256918412,5304323081406240818,3303538589997961255,-8242543733483560526,-3361776038394087875,-7966401800695747134,3661948208390050674,6880986284844289330,2763308461018415133,1781656665212037754,6138182394991053453,-7512225217435664149,-2696439080506022889,-2583065046819908147,-3131915636955022563,-2889357217172249387,-5802605454962117101,-2436895282174351119,-1766568650463350318,-377122117525974673,1776581853777064707,-308611149542073169,-540314814780534625,8467843478952328360,3468583091456007095,505744836808219017,-5428914123150493339,-7776987036728855764,-6102268671949303457,3494341367960380577,2418782979535889063,4679473505413000143,-6441695285033044392,6265164336385959504,-7246211974952246812,-531598530841805554,7617543382550044362,7304030873573479981,-32281324903020730,5445701030230371763,252311267739668938,7731413305529340107,4792829355971906114,3012742833337443711,7376323673068462242,2937445380659696069,9159469984575429466,4180661836353763848,9102205873245014544,-9157654341755851144,-5917184808139238532,-913012161319772394,3520965615244733154,1105108204046932414,3640346287517683383,2610854371735641718,3369140582718399805,-167503450741461836,7612537899180910062,4647612969614095840,3109561378106990004,8745335350416839074,-298291418130746473,-2193685336892597509,-3205646479549694138,-6912700853529572321,-5285985482282474664,-8011420405948338685,-20608671900365787,2461277845240147045,-8794182113545320389,-4143692325726628162,-5206060059250865124,-7341828269574673748,5997074990730119543,-6983875851493091721,5190016632970933241,-1133665158084916157,-7711757776416462528,958657918611969015,2998347888694802671,-176777484057504605,5157771292309956459,-8999461217390585327,4257577863211723393,-3385462713578387432,5581805654425926531,-6981668768611461067,6619449109488021267,8273870493873208839,6305391702152098821,-7738026482851978733,-7424370079506352431,1130290113791392248,5736936187682728875,-1889540322116193194,6918453404219483036,-258362754443186269,1740351069027290592,2990762037699987674,2598835903464008375,-6081928830422087295,5388584501900900268,-3101635458397415306,5560630914118636896,5540181403154305832,-5050504706493546867,2482421493273885212,8345872426056290435,-114929197746482490,-1411535166620560130,1955447843789378400,-4415727728018118178,174849678320512726,-5578523943478722759,5785969583518444021,-2232487152186233036,3347165569852915762,8597084251364200641,-8637378221001354125,1905787365039574668,-5764297333239831537,-6887855556896782846,-7466419285184801288,3561228892785125799,-6025847770670435502,7880903838892214728,4831723645980851507,-8700410925103051535,5167047152144011193,-5589950774695842572,-6975863374495850197,8636325743490381438,-5393462740365964783,758109935525139289,8449824526047483324,2882040775719318333,8722862970638278922,652288902771973384,-5889783177719394690,-3211436433657712007,1362735929528070085,8025013999877916656,8057121196213509424,-597152196419816458,-3731606026680532941,-6814641654656904693,-2513538531416010165,-1449817420573805572,7983703381157839238,4136435098211692276,-1331213617861613522,-289183771021882356,-3100859045837937046,536889653442631647,1933334157013614393,-3378838522188481907,59059052034778512,-9070778615901588520,-8561634908355121490,8646082716902511799,-7190394898230747028,2223190096772479452,-625200368095748196,-7695499964415613072,-2925720374223602748,7859320007538329711,-8590024973885119823,8447867896928955011,-8341487853447061366,1319006032904755853,5631657808401138749,2597687022492864406,7575706244535104411,-5270921382190007475,3486972365953290955,67197056587467249,-542829327793657434,-8188837871581890476,-3908705513843534551,-8566981112648480966,-6798624665298914527,9174760941175519307,-5792872140589943835,-2219700069287782459,-6440926725540882731,687123600828336407,6695459205124198333,5752186679888935902,3823361293471306013,],
+];
+
+#[rustfmt::skip]
+static POW_TABLE_1: [[i64; 192]; 7]  = [
+[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,4,16,64,256,1024,4096,16384,65536,262144,1048576,4194304,16777216,67108864,268435456,1073741824,4294967296,17179869184,68719476736,274877906944,1099511627776,4398046511104,17592186044416,70368744177664,281474976710656,1125899906842624,4503599627370496,18014398509481984,72057594037927936,288230376151711744,1152921504606846976,4611686018427387904,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,8,33,135,540,2160,8640,34560,138240,552960,2211840,8847360,35389440,141557760,566231040,2264924160,9059696640,36238786560,144955146240,579820584960,2319282339840,9277129359360,37108517437440,148434069749760,593736278999040,2374945115996160,9499780463984640,37999121855938560,151996487423754240,607985949695016960,2431943798780067840,-8718968878589280256,2017612633061982208,8070450532247928832,-4611686018427387904,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,],
+[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,16,256,4096,65536,1048576,16777216,268435456,4294967296,68719476736,1099511627776,17592186044416,281474976710656,4503599627370496,72057594037927936,1152921504606846976,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,8,135,2160,34560,552960,8847360,141557760,2264924160,36238786560,579820584960,9277129359360,148434069749760,2374945115996160,37999121855938560,607985949695016960,-8718968878589280256,8070450532247928832,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4,64,1025,16405,262480,4199680,67194880,1075118080,17201889280,275230228480,4403683655680,70458938490880,1127343015854080,18037488253665280,288599812058644480,4617596992938311680,94575592174780416,1513209474796486656,5764607523034234880,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,33,540,8650,138414,2214635,35434160,566946560,9071144960,145138319360,2322213109760,37155409756160,594486556098560,9511784897576960,152188558361231360,2435016933779701760,2066782793056124928,-3824963458521104384,-5859183115209015296,-1513209474796486656,-5764607523034234880,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,],
+[0,0,0,0,1,65536,4294967296,281474976710656,0,0,0,0,0,0,0,0,135,8847360,579820584960,37999121855938560,0,0,0,0,0,0,0,0,16405,1075118080,70458938490880,4617596992938311680,0,0,0,0,0,0,0,33,2214635,145138319360,9511784897576960,-3824963458521104384,0,0,0,0,0,0,0,4096,268435729,17592203935744,1152922677132918784,76842668642009088,0,0,0,0,0,0,8,552960,36238823415,2374947531325440,8070608823267622912,-8072983807038324736,0,0,0,0,0,0,1025,67194948,4403688133701,288600105530228736,5783840476780036096,6072259672578981888,0,0,0,0,0,2,138414,9071137783,594486085783387,2066751970480947200,-7784595809881817088,-8116893903405187072,0,0,0,0,0,256,16777216,1099511627777,72057594037993729,4311810048,282578783305728,72339069014638592,0,0,0,0,0,34560,2264924160,148434069749895,-8718968878580398201,582094356480,38148135746273280,-8680969756733341696,0,0,0,0,64,4199680,275230228480,18037488253681749,1513209475875820821,70735243837440,4635704940130467840,6130806467734798336,0,0,0,0,8650,566946560,37155409756193,2435016933781924608,-1513209329119911445,9547060033028096,-1513172181595455488,2444047222778626048,0,0,0,16,1048577,68719546624,4503604207554576,300166943871248,1224996759836561425,1157443864920915968,1229500363472633856,1157706579210928128,0,0,0,2160,141557903,9277138794248,607986568019867768,40522537422618488,-646134085450172169,8680969174647242752,-38147594580393984,8716435603798884352,0,0,4,262480,17201906772,1127344162226437,94650720833590549,4923631783780892757,4685244537110860101,6130877201840930816,4635630379498209280,1244400872037810176,0,0,540,35434131,2322211272589,152188437960410544,-5867073703402004022,-608753751841641693,5021550739930207323,2435017087666290688,-1503124363304501248,-3144919914788159488,0,1,65536,4294967296,],
+[0,135,0,0,36238823415,0,0,-8718968878580398201,0,1048577,-646134085450172169,0,281474976710656,579829432455,33,76842668642009088,8072983807037771767,9071137783,72339069031416064,-8680821320398633081,2435016933781924608,1153203052884328721,8072983770657683879,-608753751841642177,1,70995809403015,0,268435737,2325224901419503607,0,72057596286140673,-4047941590536714361,8650,1828479723647826040,5198580908436257015,2322211206545,281479271743623,4652851823974482055,-3824945721178980319,1229782974218235903,-8359203940994719823,-7785153702193098917,-8790878036300495359,1551279595255904722,1157478821306368048,-1231840126630824042,-2244067483645952701,-5867073703402004022,16404,135,2214635,4403419698516,36238823415,594486085783387,1441151881837827092,-8718968878580398137,-1513209329246797650,5766090787059466581,-646134068292338525,4987494515535258582,351930695303188,4617597572767748231,4989366934530869954,4995636651726742868,2616027333969501107,-8680969754468382976,6148982769688008083,-3255113792571260030,8108459549707964399,6110225865917094366,2616023978973555122,4330401300,9440922232176661,70995809419410,1162434420959906814,-6650882093460728755,2325229302423405341,1510550969824680745,-4696143385879816939,-3255272293030243662,299538383934670116,899585657599261095,-6421298510395728011,4987212465024951234,-8439804607159910222,4722974330230397517,2604241862179011578,2945765058557585494,-4172586336866215245,-7908298668497926605,3292917456527349333,-1778416807812019587,-2687845494699988046,-1568533776661182301,-7153308993320401295,-751561123640744348,135,135,594486083601840,36238823415,36238823351,-1512615122307666256,-8718968878580398201,-8718968861378493549,-5859145822004578895,-646134085451220746,-5251909112208802653,5012764771064815280,282054806696071,1463670458724844711,-8184224933876447855,8149678041610583920,8167559115579133249,-8179721325835109289,-8788221579835704968,-2069077196422502013,-4705347465926991951,6955256496823371726,-7524108394299359031,7563110548872886158,70995809403014,75399497649272,-8947147165825350487,2325224901151067886,3838472271485441641,-8942843533514592335,-4119999182185003507,4329109129124827895,-6421336103236948990,5891272723926220804,-1804055540449515934,8460564669008640934,-3753081440134336504,-3860138431806531030,-7856653449343714193,-7595651990768072831,-4052283364874674317,5532806268997719779,5288704387223848300,-8744239686539652327,-8855053725810232034,6006015969448097578,1347435800541178025,2211897868760481646,36238839779,72061997459758636,590093403544079,-8718964475161218279,360860506022940844,-72057449430616578,-2087283856937846165,2955844742563665725,1563985813813261386,-7320240988429897084,-6688021649094603968,123717882122878262,-370210050093239481,6069896046897945042,-8123643723470492874,3483026182173742943,-7835963269163963083,629692079040326967,-2397767918274165203,2307919561648830965,-44914365399010368,599544380208996432,-597294467434364901,-6964430688229133911,2334920026170350992,-5605342300067343405,3551021258077608539,609035323518161084,-6721022405297278944,3504310508963389432,-7283152471191799613,-8722198899053206729,-1250874794737731711,9074608179003201540,1810628635239662178,-6451776899373758723,-4615694538393549295,-4362275103790198702,-3792222432303245256,-1559692666614209616,-98431217577796539,-9029920801466639058,-7109365235188542407,-946677770089042793,-182592247182753593,-2637452241563314774,6124864149863968072,5021550739898464339,],
+[0,-675700754464725196,-7400245184483749183,2325224865180680192,4308854149351096230,4087632387066765743,-7275283868590567591,998815193966931967,-2143796421407463834,6056625504733376525,-4045721824789864836,-858530229944418774,94575875809256316,-7495074221927422752,-3628564631334774117,-6872602957773652666,-8837670072557268635,2150855273413160557,5842706246122142201,-8874354114744897075,-7498620451270880714,8345255364170114647,8675725534108615393,-628718379448202296,7213058728673621187,8697600085574001635,569941992076422209,2101729217045010600,-869272563270581351,6349834165615373008,-8278423197265695468,-289667629372155284,-4996188247313713002,-4193590892988300734,-7808747067947116470,5740222723455656079,-1004293179227928657,-7378027571087326870,1850676172401126584,4102071215454560899,7259757191991660866,-3263750637324313573,-7101095927535849009,2960944838505603741,7960409200978162151,-1380919195139420544,-7265787777315546970,8696134004788876257,4459615944721376107,357711267766598467,-6591463393386029767,6213350576813261001,2844246054154448404,-3029083139417290328,2245638225067189479,8617601719125400457,2128220270181946136,3470499785866555218,132066871132521002,5517882414738609434,-2003374013673959323,3739836398962945633,4448468942318558050,5616161409774106646,-1642714353533004129,3432917397076393183,-7631234578304800051,1381553953950798900,4023962110129311253,8644710097507238632,-1197417248055046378,-9214470001404003712,1609372195130461718,-1978500250962778826,-4911048255582930948,6141651141653126100,-2210543824408560838,-6093993786564968581,-2331300188278471014,301965068498387180,-4793576488484320667,-5125824936144379883,-5544211551818536164,4552272197317892247,-7837278238339183834,-8761637332466461638,147364084060044539,-6064825681333790105,-9198755709530655411,-1778124120876162064,-1861492150822659393,4745713929342438769,6861768606120208380,5182389685193931296,-8534340902764341615,-3590390582013687815,30073544289745672,5662918870480130927,8401074218837039520,-3162537045663256753,-3696184205999945570,-4122514099598642296,-7789756672013896695,-287966903401783401,-6507490048846866302,-4916032157138151070,-5141347076922627105,-5155040494742911856,7430428299516436592,7568914190360801521,8976947262451327251,-823811253246772689,3192421721340291099,-2321904427011346487,-7001545068850142391,-8141745164608837714,-8484695803346689573,-5018197261793538831,-4680980064014602375,-3442898850200611643,-5222684558521265456,7664587417491999280,-1184664264514778096,-6690427770995712658,-4105408088494675476,-4179651232527412888,4672902529451387521,-4929725195951149496,1568605474300434685,9132692739037808736,1067330377231330106,6234823338025250317,5513535159769997480,-6296592138893575335,1857768573899923229,-7795052510154389180,-7305898577268848196,-4018600913292308304,5464682203804131280,4913993492957390835,7057555747515730451,-4522471330477326797,4668369156558985260,4477286195984166923,7381389311118714077,-7376279152378820185,2001470970870984953,-6267077529255448638,2308580872094892292,-3732951464203912308,6769597213437287237,7233920586946777352,2580562194308495651,-5163189941835227305,6315713421482690203,4098234801449939167,-209812842733548776,-7894469765614518540,-2554059219807878625,1903444257061664607,9182030862387586589,-3109633788736425272,6389430618268296347,2129494461042385878,6329472897410366361,-91499458815143634,1221682685580272771,9196639794739742553,3102002862952173801,-2224431388243524627,346567882230063653,-5437991707734288744,-2709888611820883348,-2920666756321254869,4930390194078211174,-6753455264900793669,8186033625824413668,2517429022687892375,-591051196767852614,-4262657608111575498,-3159880638279040943,-5917782714799358545,-2681282764713948442,-2318918853231809968,-6811170076728669460,3266419467001559315,-515756142318178599,-3869312023589911625,1976731212099439882,-8842932614801981568,3225246888378129325,8664993276476894618,],
+[0,6888918647020560317,6616704076946383887,72307319579008765,5019028484594594082,-3189487582568884878,2134511505384836107,-8664850887478530773,4653976163382426028,-7552953056849816027,6722895949646321714,-6956540475216209151,-5858062716999869069,-6264590843552634074,5887677734908074113,2474629020427595354,-7967281225152887102,185220160216387872,-5760623994813845340,-2535719245014115912,5111362823887419820,8505227612259241925,9012934128161153438,-3454844884687058304,2688606500979393393,257493182509576689,3669454563593192799,-5918660207704940910,989805058886100772,-7949845614554438917,-8650932953258294805,3719293863967856435,5524498832277079871,-8204898049315048076,7429706311125713887,-3392350091536387004,8803967679232678927,-6709573047928675008,3993787092655773756,-3869147372389115171,-5407630961212543773,-3635696971192372537,-4123255486571580111,7821261793194743720,-8259701755427194463,8778804536940933206,-2390355563131639991,-6022268794344148517,-7704290986577360513,-5411054657730165929,6563199634835578546,-6179985290346013130,-1779710405126312658,3860946749005281310,2894361089265489575,3315776251307050326,6320628998837644363,-4720130451255879792,-7396858832460579381,4947792566457792928,-771597949057082277,-6283874120936860908,7751617974029105049,-3171781932687118992,-4986583824628389869,7554891199116256466,440872917012743287,8832529013462318719,6930378999847853276,-6172476313572563251,6597889588190964693,-3923014422236362697,4997044127822541429,-7107806937807475144,-6289965583375946716,-3044570048596622809,-582961432760897161,-5961388502855958672,-7194944488185970118,-2808201162094710660,2825505208148432617,-7328788671423443242,-981277169914054735,5488327868523545998,8289151770336172410,4907413581236102050,-5687370805778312995,59381471987291070,-6444452561966471140,8634477550854188789,6207648744164223412,-101963300189371393,7848638498504197321,3498348962566120926,-5579914395407433825,-2545139183283670919,5130648017855629422,563110260262788563,2135475898455702366,7684314690515735551,-7002326702731443230,3880977581557303704,-8637342854207977051,8496120004406519552,8560768772188447329,2594230810807943255,4337654442994597095,-4585888647597749639,-7892855638664835779,1565051773613738620,-1693518853642867805,5567975317132003788,2962765293309317965,-3913616984206243549,-5558808830930587106,-8050075131445890472,-8457438218982837752,-2386212332821275776,6035074888470767028,-7849778513431525815,3298946049141257047,7780989528292148686,7259205837724911376,4482330118862142166,-6537500962732474747,-3022706756077921906,7148848233164372316,5077131755656950340,7912726786975152439,4848423276587831069,-3830309290120570642,4508033649949774926,6846300513888811901,6242882741110337747,4170945278743029343,-8127216801805486969,-7852480183891607774,3990619336327845960,-5983515027675199463,-5175175724494917100,-1281849133123778903,6285841989812053065,-6067528458241089448,7576477052240298304,-36164364831076984,-60994174189450074,-8529533350870615239,-4817148324041097753,-4640927619693149134,1872208642623965689,5240297214938900007,1572132602803588846,-650696111471122406,-6683156123433455837,4545617032206292763,-5495059938487344780,6556517553578965713,-2511396774410513113,-2176872386175367579,-8143603626268702413,-8219576026727867109,5228455090572155705,-8048532819979278350,-2942421454182291603,-7739452100314543781,5339545143011211455,431828781909893989,6504224558731934448,1325434730767337764,9044277964768096581,-2012199912615250454,2239476923138147060,5446470907191488828,-8988608972356041587,318526050097438911,4497994325831131702,2421970446587647365,8944762431294272394,-1575644653468915716,-7480808359693534377,-8386442038249850993,-4826695226202864144,-2040524201209064254,1185655104167734601,9208155472300323928,5181480307949496453,7213432351073135570,3512466954668360697,-4638794086271207228,-5040741222494255775,2246055029297786978,-2407449019420128263,],
+[0,4331831946986922092,5039137575310318944,6572365103720100214,-3372926667923484384,-804959452957560038,5319341503317224386,6670307960034794050,9122331677505366914,8132210050240438928,1856212684185378577,-2418012329048383413,2221935190602818642,-686940626615845117,1911412200771311721,-8073430757900621106,3214975954359082910,-4390346519891573401,-3501449563817128233,2931745286610574473,6196837566508069630,-7985185842868269260,-242763400354519042,-4762972334960522653,-1128709856992935914,-3133210263897755440,-6300878854527293186,7341789762184517091,-742546840681255590,-7168808549419220445,-4984050358805078354,5072732112695304142,2078982868474422173,-6351627917229293982,-5889560863851129253,-6131615849942787808,6542639951406636963,8480740463682186660,183168288556720330,-336660061516138115,-1410356938699911649,926150233093626212,-2881764498566629282,-1145487279366622181,2351884447002867207,-5662126631020168770,-2882202962071256822,6804440515561204260,-7645812423207814611,4621144061789925334,-2353433576646516057,-664832534192041661,-554535101160684318,-2377767015672774851,2162245627601598447,7482066041309690120,8259346317988151315,-3846765727327599638,1731326869372517225,-1980000664251113326,800694689332165758,2515205999128895054,-1997432734072953419,4672602758053323554,6952202226827626829,1161365306867490106,-8384523961905918605,-733116767785239559,5682995397931390212,-3325241677131986932,-7594435646578169790,1216932035765251873,7076597346109630370,4335245905675328559,-8507624828826261297,-6137869528790051691,-2990757269081501860,8207981314338567695,-211809688264439807,-3940005235808670096,1182929724269347747,4877641380646887291,-7648008948030491945,6628446266965226465,-2970852163554202170,-4670164336893474473,-153630879029846201,-3309814009518565346,1753932513542224524,-5251791855420722187,-6759963098607779538,-8872083893346595943,-3120155793324540715,5978602003840494141,7512687430188190283,562835420304739569,4904579120205325277,-3683422392650008109,7042500995660740987,-1972180833418385981,6346437281268254654,-2243185610911458224,9026737040177775190,4993647529943791743,288019624394432352,-4353118648656339247,-5420873398923132591,1549704053713244983,3614498467424513972,-9027385653029153084,1629718615812967730,-2759637422881662616,8432531436503595927,611355542547437884,-3281181767178975456,-6653389075112192169,-6767829238387607677,-18377277181334064,3726999606378779346,8982897182547291075,-7270818405218871784,7385860370779663565,8974928614734018492,291006976587948877,5300536609199764342,-5751424882775853301,4349796007363489739,-6969537113022603028,6155372982161835515,2778638126408133418,-5347543214912549170,-9027306700095574549,30249368683249826,7438665593684814940,2922690888626912628,-8180978412153428577,-7237995582212279627,416623024707852752,-6898030889740364442,7422011222211524550,-1171936184535606480,-6766055360615975733,1731128074959168128,-4607795217355720589,-3213029979791539367,-5255952104659057192,-2314414383739670603,4396632171704966086,3006711910774356251,5778933548260329613,4157127632653091975,7318697691457423286,569409338780015498,4153168956437659929,-1756599119278225307,-3314455936932684387,342118048129659290,-7569984731692337361,7663926015038805676,-7070277473562255822,289945662752184113,7974238619106446240,738352690694983924,831937267866542901,-7662231404878724479,-6989417225990538386,4271423021483837384,-4850149730195086768,3731768127773306728,7364897548779496026,-2756767884644196684,-1753950093378288022,7143078809577818863,4597090775987743317,7848087705354908100,1905884943523277834,-6153674769862497703,7016308115898147045,-1899771811690011877,7221196628836046154,-4199539233852873704,-8773468848938902681,3961256666769655818,-3407671319284954837,3336711503507566638,1628300123613068774,-6944467362566050167,5759866442005474216,-2680310850292804557,-8904643492625661829,6625111154478727695,-8756613211059540532,],
+];
+
+#[rustfmt::skip]
+static POW_TABLE_2: [[i64; 192]; 7]  = [
+[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,4,16,64,256,1024,4096,16384,65536,262144,1048576,4194304,16777216,67108864,268435456,1073741824,4294967296,17179869184,68719476736,274877906944,1099511627776,4398046511104,17592186044416,70368744177664,281474976710656,1125899906842624,4503599627370496,18014398509481984,72057594037927936,288230376151711744,1152921504606846976,4611686018427387904,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,8,33,135,540,2160,8640,34560,138240,552960,2211840,8847360,35389440,141557760,566231040,2264924160,9059696640,36238786560,144955146240,579820584960,2319282339840,9277129359360,37108517437440,148434069749760,593736278999040,2374945115996160,9499780463984640,37999121855938560,151996487423754240,607985949695016960,2431943798780067840,-8718968878589280256,2017612633061982208,8070450532247928832,-4611686018427387904,],
+[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,16,256,4096,65536,1048576,16777216,268435456,4294967296,68719476736,1099511627776,17592186044416,281474976710656,4503599627370496,72057594037927936,1152921504606846976,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,8,135,2160,34560,552960,8847360,141557760,2264924160,36238786560,579820584960,9277129359360,148434069749760,2374945115996160,37999121855938560,607985949695016960,-8718968878589280256,8070450532247928832,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4,64,1025,16405,262480,4199680,67194880,1075118080,17201889280,275230228480,4403683655680,70458938490880,1127343015854080,18037488253665280,288599812058644480,4617596992938311680,94575592174780416,1513209474796486656,5764607523034234880,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,33,540,8650,138414,2214635,35434160,566946560,9071144960,145138319360,2322213109760,37155409756160,594486556098560,9511784897576960,152188558361231360,2435016933779701760,2066782793056124928,-3824963458521104384,-5859183115209015296,-1513209474796486656,-5764607523034234880,],
+[0,0,0,0,0,0,0,0,1,65536,4294967296,281474976710656,0,0,0,0,0,0,0,0,135,8847360,579820584960,37999121855938560,0,0,0,0,0,0,0,0,16405,1075118080,70458938490880,4617596992938311680,0,0,0,0,0,0,0,33,2214635,145138319360,9511784897576960,-3824963458521104384,0,0,0,0,0,0,0,4096,268435729,17592203935744,1152922677132918784,76842668642009088,0,0,0,0,0,0,8,552960,36238823415,2374947531325440,8070608823267622912,-8072983807038324736,0,0,0,0,0,0,1025,67194948,4403688133701,288600105530228736,5783840476780036096,6072259672578981888,0,0,0,0,0,2,138414,9071137783,594486085783387,2066751970480947200,-7784595809881817088,-8116893903405187072,0,0,0,0,0,256,16777216,1099511627777,72057594037993729,4311810048,282578783305728,72339069014638592,0,0,0,0,0,34560,2264924160,148434069749895,-8718968878580398201,582094356480,38148135746273280,-8680969756733341696,0,0,0,0,64,4199680,275230228480,18037488253681749,1513209475875820821,70735243837440,4635704940130467840,6130806467734798336,0,0,0,0,8650,566946560,37155409756193,2435016933781924608,-1513209329119911445,9547060033028096,-1513172181595455488,2444047222778626048,0,0,0,16,1048577,68719546624,4503604207554576,300166943871248,1224996759836561425,1157443864920915968,1229500363472633856,1157706579210928128,0,0,0,2160,141557903,9277138794248,607986568019867768,40522537422618488,-646134085450172169,8680969174647242752,-38147594580393984,8716435603798884352,0,0,4,262480,17201906772,1127344162226437,94650720833590549,4923631783780892757,4685244537110860101,6130877201840930816,4635630379498209280,1244400872037810176,0,0,540,35434131,2322211272589,152188437960410544,-5867073703402004022,-608753751841641693,5021550739930207323,2435017087666290688,-1503124363304501248,-3144919914788159488,],
+[0,0,16405,0,0,4403688133701,0,0,1513209475875820821,0,141557903,4685244537110860101,0,37999121855938560,70460013625365,4096,-8072983807038324728,6072259672646177861,1099511627777,-8680969754468382976,6148844231222908181,300166943871248,8108459549707964415,6072264093493673942,0,135,9441497757794325,0,36238822398,-4344883889898761147,0,-8718968601253017721,-4731747198132988651,1048577,-132789517139225323,-1552739068514332347,281474985492480,37999701685387285,-8439804064927760332,79200023969402880,-4437309755392,5541920255199135408,72340746325590273,-7908297577503485241,-6110106313622404075,8676465578921629935,-326184747196674646,-3477858389994040487,1,2214508,16405,268435729,594453068185772,4403688133701,72057594037993793,7782220301781673580,1513209475875828959,1224996777003865156,-5568602317731943389,4685246687521203912,4617315522256633857,46947281589357164,-3824892998506958796,4995636651659171088,8116893894401741024,-2657538287028282471,6130806742969226560,27400700751995177,6195590254004767622,1157782445580441636,-3782275202737413550,-2658220304921737954,575525634069,1162363457633372907,9441497759976190,6917681753729944802,-5498814577540363438,-4345476997192759376,1551110792602277236,5891520892378292651,6144410812500239428,634601418098493862,1774375360755843061,132652009187043017,4653133841193683532,-2595690203251959175,72110664981553453,-1230337829717287256,-6188909812282035538,6456071231484419289,-2320958359203443879,1835508870757419369,2040370669282281878,6661217468141030217,-8423640389371565403,-8499405260925408371,268435728,16405,16405,72057594306428944,4403688133701,4403688142223,1152939165798699280,1513209475875820821,1513211798084813650,1224996764271055007,4685244537241932234,-8363651757808097592,1190939387166195984,38069581936595025,5021584044531862713,-6992383705976074216,-2597990945295154084,-363348139508661757,-7600368554163986847,-7582301154678812143,894948077087235353,6955255921298015887,6959836035952832632,3211452494295328458,6917685570877522327,9441497757794450,10016896989796619,7027313512938572782,-4344883925063770117,2927870116789082016,8786239407365985943,4131336578943587486,-4726948581212862695,127865309502915844,6074982671291646492,-3775267067956559256,-79200059939802875,-8744009164630305692,4615764723498800113,-8718682424587484521,-6158288432344557974,-5261638342178675313,-9059672762503245484,5519878846588365914,-4436464087703865944,1518927025456563280,1468085383922929905,2639105496201891805,270650237,4403690315305,-8718374425263534908,72652047106048429,1513803926786430456,-7346953228811164402,9007217061455705778,3243811299122139894,6753230224894884636,-5602660768557635367,-883519440648577041,-116177230604955516,-2323053257641285469,-8482307462680691891,-5549874877820869559,958020971772365464,-4991544269364360344,6363309982556444943,7331190440433981494,5015726139678737532,-2043388114386413778,5482647037605624617,1206745860518513047,2086309373276999127,8079745281175912599,-3273465508891764574,315336160138416834,3834475922849262099,38021128702995733,3474027448873074912,-4358775760477723763,-5618657038833202186,-1545654340300590546,-2631227852331219336,-8776825519658677635,-2327823662365475282,5194557473419685442,-4092526298777937177,-916312845293823853,-2363175478922554126,-4978193684293897722,-6320440829497657480,-2670705166203992950,8762236708630736962,-5599128477180867553,5323899568776667617,-5564129564103000826,-3382740581917399352,],
+[0,2716622788963031847,40846672993527025,1513209509967159019,4621053680045158388,-2903996173352235569,-8072983807038316094,-7575455417369363805,8071326617522633051,-7258922398541384564,8704697640774031947,-6681570071551204221,-1562641326068657855,-883532926705604284,956268130454475388,1215539162648774541,-426414134220978363,5270683299884762747,2330181287926686005,6134726476362434106,-2325959145524659347,4329716150192313480,-8392881078967907522,-1802165835817182982,-8100388729951545868,1867951006267200589,7919618595933494384,-8980269885778783131,4071040395359672573,-312862961573357955,-2941873227506952960,-8115294874401740510,5303426865933611246,2958139355704065308,1463694019776869652,-8976074711962363925,5268644657139266566,6964861625476310538,-1517608123673286513,-2915846685277558710,5550751346972347727,2112780311210561748,-1828007150056065159,6384500303152980510,-906389597981947895,4410709334475405688,-6483486400246371702,-8147255517704438781,-6120938892653523797,3199011783477797964,-6761726043452623010,-7047017470580974912,1462717182584096488,-7023268205675315115,-2989303706422286108,3180460850976781138,-298416058831618501,-7266836423948921205,6663350365655515731,-8359063233001334572,9056022989288353575,7798619345308693609,-44616847615569961,3192155203687896874,1239389723220221729,-4986248400106757818,4108171716624422170,-4173733134437352158,-8125352421416488169,-1185374074307245661,-2966673101544610810,2704683786991607858,1515177657563554330,5601341054180475457,2983614494542029933,3582348994995344418,-7227381997475091214,375800204207924206,2993383011336056468,-8189001996079290037,682068580983257903,948844863510518846,-5027244184536956601,1827155836971693192,-1870457681157527590,1442861833621761616,-7501553589451368346,7570278778816122784,2996106664946480472,-8781991581739643752,-1791985321944155905,-867682135916918265,-3280503815586869540,323928290362912952,-5799577295755596577,7265376777009662712,-5900142203173808917,-1517427944723435699,8119832848073844820,-3536200579017813566,-3797880052796029066,2953127755774818207,7848593138406357335,-3561467074012037304,-7337175485261886469,5807093610353856481,4150266656318619307,5586315349794142210,3173004702088493577,-4041319562043822090,3864667468337058586,3273021938862095623,1830503478934844635,3749676212788847170,3555683139611306856,2307286949526856026,-6923475262585040711,-701796416470938392,-1858770742650766417,5567697607330176830,-7615393280240676601,8367577308384162142,1289903960876064367,2964316419676655924,103719735714153803,115707662404946645,7038009716978659739,6993618381930301556,-4413073683489083550,-5009032023647056184,8984906013653963103,4426963583202880421,-6178068367693439722,3477129417051532148,-6090672487045910366,-6135241880902941518,-1212340631615108657,-3815125365865109228,-9071677335252123805,-1160367325517043426,2955609817225945308,-1003634050197601548,5820534109579904411,-2426268040301780073,-8146151533873453013,606046764860835901,6365109532573370147,-6149510524360813181,8739343454238347465,-2972886873342710445,-8078313491105835340,-8453826761140217942,2610148900125924178,4094047797743140623,1798485114169935380,4998884408623716905,8950537777569088369,1259580490436590913,-315040158391152316,4404501065226543846,8146418735010981422,-3207553747699863543,8675392909711600921,2405040524590938945,3011427288135051459,-7505026985532373362,-717246331947472893,-1249163693485939994,-5296945757900320134,4406943265523691209,-7262817264707461431,4641142375242104030,974365924473300426,5883429614278840526,1752533021582360374,4682777309199078800,3204063093503561410,-363155732334907633,-2346835733169282527,-8137667428439140060,-5206973815505988715,-6974909107915889500,8764043288183918255,-4092038371708175209,3554060350791641111,8798581772638267674,683285472572572424,7214985925390295205,-2157639133813705666,-1448249137206045231,3845284593116750432,-491254275194118919,],
+[0,-9067886894117383031,-8765631554449913793,-351960140370164101,-3809828891435867380,709347176573105019,6367995667762707277,-2306580641000201140,-3294298272065609853,4371465194278568200,2607306921379681548,-417323118857018121,-7881922716238547623,1742624878807396150,6417633233153038438,7245011226171800446,8165326897970180555,-3243122380933127165,-6714040292093312106,5299517670423801760,1162621650998540887,-2644879706039864385,5228558976169295831,-4391072266260069004,5007015542307306646,4682900706152011413,-2123901141179325738,-1563119241267841448,-7901984116490304069,3479726911851668567,2328631765004444895,4163098372279135427,-1162220268661065413,7829988552306176969,3774955113097750561,-2924095674636243058,-3804005518905654993,4738269630527809961,5850935874683467236,8655960374699796185,-9059189580654183421,4147746414725146890,24509238664879977,-7300123086118785535,4751556328478914134,1176138900156266839,-2121425120505405076,7247247000762229134,9000592214487314811,-889874608502765498,7236795550799772071,4974622482278556577,-420560834611630453,-3768646734241421044,-6934105751774839201,2969065130293732380,1157896836976407312,-1559291870109505818,-2713062981234471322,-7531022569765588290,885491871452046438,8154994685434777085,-6183517998680799133,-1006560964259624252,-3294584533985251232,8399396859432285260,4941554285858435526,-6156845871586263088,-3284695794597124922,1532126679216399071,8710324980140137084,-5829657872686309788,-8769115779063538072,6935866645975431778,3597238061932133376,2900308539208720779,-2048705180801093564,7055281952541030950,-7002220757486340324,964568490678066690,-8767317763140366030,-7051357021415343791,-4942724421035409788,-3480567531822663066,97030438992350687,6148848201715609829,8190673576143502363,-582873467951437833,2647318604324937637,-6741961242409679499,-3005976745528477871,6997691635910859134,-1554393429201478263,5312146010243409080,8436439012567294277,-6630723209210577509,-8673971494977105192,3562527997978101964,3222754741725930251,-5514361182259644100,8086871624387515496,-1467927774684365475,8787210120862734018,3868688879557973489,6456800047903216186,2070752891678043017,-2941591783186713651,-8183443290798012978,8647945886161088410,-1841819063379755142,7860120982846312859,-8493947801835772681,-8772774970693045973,-5241215312398964897,-2611583395517621586,-6102100345907364588,1496816916737236359,-7037938107874011031,1848097601417926664,-3280842067707319343,9059361377927179923,3282174138875773780,-4916481664416226618,3886169231649272478,-1162360497370278599,637220995047853939,2885978966316747573,6728781912350490111,2328479630147269651,5554304721491051724,-6390247834560005501,678119673988273692,8651416760092589714,3253782092936323383,-1172981379019092788,-2681934234447846106,2685869215896638688,3821621354052583845,-2684383087845706054,8084097633656028849,-8363538709557862805,-4959083379007699006,-636423994845221856,-6174337185251636501,-8181624222422079238,5775773648593308303,2958061024555050145,-5902970918704504061,-2311021221920430097,-1163971532460119016,7608815371737216021,-2151017459333583787,-4990542649899559495,-7513884523432741003,4393693670759726766,-6124974036012512535,4359543309307998296,-7037830908455507891,9041027053538546397,-4965851250845680310,-2710962042488783523,-8360351447962823382,8718758072633673592,6091137861253238579,3170648231776465081,7255519673286422939,-7053661224901986133,-915340883967460252,58498294164417086,-3484407801438382424,-5784099705119286635,4125777477825819372,-6146926288831583310,-3273005006573409355,3494948349508696583,-5006780570108823652,1464644271341482461,8662100360049866867,-8213718696027725861,6111700097284965138,8732551933992222890,-2625466519519768621,7604239518435423389,-7828716348124971154,-7235290890666697460,5948056974595294574,1526856277675902747,6112243656016507212,-5496701154568696152,-3510748376081434273,-8169496792421316254,-8879479780209390885,],
+[0,3140177619151565,1460417631189212726,2353554947493303907,-8202113219766144441,-6445610874707668273,608805251577783707,5576331011745724676,-4616645954249110408,-8150056064724481814,-4375043884813768089,61489915732671441,2417003783109232201,-5797177228338315992,2030419241542275643,3535467551177747619,8160953148558434627,3783933582983994877,-395558155134838237,-9037492967799507046,-5583543374553761415,-3766787778222337249,83690989555392614,586532773118624438,6753062925187026745,-8948265279136309565,-6410106965476177336,4682508874368457020,-295508894803101770,8755364544425811426,-6946865691886399246,-4998699326132353090,-4913666944514812110,6656002279105587104,-4102330896140732563,4073773542208959172,1868016903708504679,5519576265667760424,-4364728854253647198,-4053216048524447777,6663500710558038858,6972529717731021777,-3207571042298769577,-3888399221174842362,420006135991670627,8470075279405824658,7027685758317034910,2040544246752732537,-3800680914792011602,2040759759708548109,-9015248103296315503,652011287933867814,-7782739132326567829,-2317801922460293066,2611886844620986012,-8984631646102328554,891896526125902634,-367951637747449086,-3497113700860363823,5236614907167581294,4114633954038032258,-7512497826449542169,3242179150310062402,5331743182358224881,7796816641120626796,-2424392677330210781,-8144516314316042367,675811259852555579,-4634618573840023378,4925946102011935067,-4976229192152584784,-3306578665043743720,-6377989030567179047,3293903018441646805,618512784046332063,53396408973512940,-972771490037569515,-6449609039165015841,-4713122490770203220,5807317894024892376,-2670957669784138572,3253385083202136062,4051471174117632380,-6471306451500783400,6958488026378472944,-5240312948719888335,-8730122111509150856,-391530967442739522,5304728157073167586,-8727565006975506202,-2051755253763667777,-3562176666377319713,7612155015414030601,1518046426766570808,-307960163954445386,-4612626700850755125,-7636305212757699943,697133298319656099,-4630649231468148194,5297521963269776703,-9050284098059359704,-9005170998800333392,2690681881609407239,-6345572204046605232,5811140775354848418,-7583858705664828398,883333908996047580,-3023430280093746546,1253866782730544252,-2652541341293732240,-3271892520967689019,-3752005443895063020,4447917552968482513,-3824236721243846818,5600139313482945383,-999779136651389228,-8469897042294769427,7796143214715526711,406420894930862997,-2962130523947052332,-1278282830806339692,-8447450042751963291,634287000685320862,-4988625188634368073,7264114668740343559,604237143730786090,1470443674382315935,7627286917302141493,6193255306513896806,-88995703250039083,5251413380424095294,-896519829376623449,-1255840563362049523,-6375440828517507443,2331875313404929916,8954805250915502220,7208472503953793396,-4921350084320109520,8682056056407108854,-588986527289762379,9058761110104874970,5619968217006612529,3556136729690226244,2636161296644079035,-8961930654928536483,-5855381532408164884,8378124878485911957,-2362426267959965117,2730324786590578227,-7828512552827125787,6135910401929572633,7539770217393522009,2966065950377957666,-2096713473244396849,-7604673598994665387,-7219768014399086113,2704497122794833704,-2967228398298959366,-6762901644464291495,-1553630643759993924,1564603397139288648,6116811891197961186,3562368697804772802,-3199395829836276360,-1165308188865718640,-2427793488252231210,-8760734042314058841,-7857272506160709120,3203259669013418168,-946026787142432929,4945843407304527756,-3777254025118911417,-8496811611764847693,6997957085954944184,6393220067418700989,1296680119038768392,5852192073241482937,-4072182146803896176,-6966297004098237683,-5487642568473235337,-1519244559474694756,3811374754853013692,-2605325301426890003,-2885808776371324742,6661350203815069651,1327657210385814471,-3825923588202089762,-7915987217397706762,6735184013381996252,1519213888176055875,8382345159179417209,1911513965813618260,],
+];
+
+// The tables above were generated by the code below (which is no longer needed).
+
+//fn zeros() -> [[i64; 192]; 7] {
+//    [
+//        [
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//        ],
+//        [
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//        ],
+//        [
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//        ],
+//        [
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//        ],
+//        [
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//        ],
+//        [
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//        ],
+//        [
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+//        ],
+//    ]
+//}
+//
+//fn genPowTable() {
+//    let mut powTable0 = zeros();
+//    let mut powTable1 = zeros();
+//    let mut powTable2 = zeros();
+//
+//    let mut z = GF2_192::new();
+//    for i in 0..64 {
+//        let z = GF2_192::from([1 << i, 0, 0]);
+//        let res = GF2_192::mul(&z, &z);
+//        powTable0[0][i] = res.word[0];
+//        powTable1[0][i] = res.word[1];
+//        powTable2[0][i] = res.word[2];
+//    }
+//
+//    for i in 64..128 {
+//        let z = GF2_192::from([0, 1 << ((i as i64) - 64), 0]);
+//        let res = GF2_192::mul(&z, &z);
+//        powTable0[0][i] = res.word[0];
+//        powTable1[0][i] = res.word[1];
+//        powTable2[0][i] = res.word[2];
+//    }
+//
+//    for i in 128..192 {
+//        let z = GF2_192::from([0, 0, 1 << ((i as i64) - 128)]);
+//        let res = GF2_192::mul(&z, &z);
+//        powTable0[0][i] = res.word[0];
+//        powTable1[0][i] = res.word[1];
+//        powTable2[0][i] = res.word[2];
+//    }
+//
+//    for k in 1..powTable0.len() {
+//        for i in 0..64 {
+//            let mut z = GF2_192::from([1 << i, 0, 0]);
+//            z = power2To2ToK_internal(z, k - 1, &powTable0, &powTable1, &powTable2);
+//            z = power2To2ToK_internal(z, k - 1, &powTable0, &powTable1, &powTable2);
+//            powTable0[k][i] = z.word[0];
+//            powTable1[k][i] = z.word[1];
+//            powTable2[k][i] = z.word[2];
+//        }
+//
+//        for i in 64..128 {
+//            let mut z = GF2_192::from([0, 1 << (i - 64), 0]);
+//            z = power2To2ToK_internal(z, k - 1, &powTable0, &powTable1, &powTable2);
+//            z = power2To2ToK_internal(z, k - 1, &powTable0, &powTable1, &powTable2);
+//            powTable0[k][i] = z.word[0];
+//            powTable1[k][i] = z.word[1];
+//            powTable2[k][i] = z.word[2];
+//        }
+//        for i in 128..192 {
+//            let mut z = GF2_192::from([0, 0, 1 << (i - 128)]);
+//            z = power2To2ToK_internal(z, k - 1, &powTable0, &powTable1, &powTable2);
+//            z = power2To2ToK_internal(z, k - 1, &powTable0, &powTable1, &powTable2);
+//            powTable0[k][i] = z.word[0];
+//            powTable1[k][i] = z.word[1];
+//            powTable2[k][i] = z.word[2];
+//        }
+//    }
+//    let mut s = String::from("static POW_TABLE_0: [[i64; 192]; 7] = [\n");
+//    for t in powTable0 {
+//        s.push_str("[");
+//        for v in t {
+//            s.push_str(&v.to_string());
+//            s.push_str(",");
+//        }
+//        s.push_str("],\n");
+//    }
+//    s.push_str("];");
+//    println!("{}", s);
+//
+//    let mut s = String::from("static POW_TABLE_1: [[i64; 192]; 7] = [\n");
+//    for t in powTable1 {
+//        s.push_str("[");
+//        for v in t {
+//            s.push_str(&v.to_string());
+//            s.push_str(",");
+//        }
+//        s.push_str("],\n");
+//    }
+//    s.push_str("];");
+//    println!("{}", s);
+//
+//    let mut s = String::from("static POW_TABLE_2: [[i64; 192]; 7] = [\n");
+//    for t in powTable2 {
+//        s.push_str("[");
+//        for v in t {
+//            s.push_str(&v.to_string());
+//            s.push_str(",");
+//        }
+//        s.push_str("],\n");
+//    }
+//    s.push_str("];");
+//    println!("{}", s);
+//}
+//
+//fn power2To2ToK_internal(
+//    z: GF2_192,
+//    k: usize,
+//    powTable0: &[[i64; 192]; 7],
+//    powTable1: &[[i64; 192]; 7],
+//    powTable2: &[[i64; 192]; 7],
+//) -> GF2_192 {
+//    if k >= 7 {
+//        // By Fermat's little theorem, z^{2^{2^k}} = z^{2^{2^k} mod (2^{192}-1)}
+//        // If k>=7, then 2^{2^k} mod (2^{192}-1) = 2^64 when k is even and 2^128 when k is odd (proof below),
+//        // so that's what we compute.
+//        // Note that we have no precomputed table for k=7 (i.e., 2^128), because we don't expect
+//        // this to be needed -- only up to k=6 is used in inversion.
+//        // Here's the proof: let m = 64. 2^{2^k} mod (2^{192}-1) = 2^{mn} mod (2^{3m}-1) for n = 2^{k-6}.
+//        // Let d = n div 3 and r = n mod 3.
+//        // Then 2^{mn} = (2^{3m}-1) (2^{m(n-3}}+2^{m(n-6)}+...+2^{m-nd})+2^{nr}
+//        // So the remainder is 2^{nr}. r is 2 when k is odd and 1 when k is even.
+//
+//        let res = power2To2ToK_internal(z, 6, powTable0, powTable1, powTable2);
+//        if k % 2 == 1 {
+//            power2To2ToK_internal(res, 6, powTable0, powTable1, powTable2)
+//        } else {
+//            res
+//        }
+//    } else {
+//        // powTable0[k][i] contains the result of raising x^i to the power 2^k for i = 0...63
+//        // powTable0[k][i-64] contains the result of raising x^i to the power 2^k for i = 64...127
+//        // powTable0[k][i-128] contains the result of raising x^i to the power 2^k for i = 128...191
+//        // Because raising to the power 2^k is linear over any field of characteristic 2,
+//        // we just need to XOR the values in these tables at indices i where z is 1.
+//        // This selection is done via multiplication by 0 or 1, to avoid having an input-dependent path
+//        // through the code, thus reducing the chance of side-channel attacks.
+//        //
+//        // Note that more efficient tables can be precomputed -- for example, the result of raising
+//        // every one of 16 possible 4-bit nibbles at every one of 32 possible nibble positions.
+//        // But indexing into these tables will be input-dependent, which may make side-channel attacks easier.
+//
+//        let mut t0 = 0;
+//        let mut t1 = 0;
+//        let mut t2 = 0;
+//        let mut maxIndex: usize = 0;
+//        let mut i = 0;
+//        for mut w in z.word {
+//            maxIndex += 64;
+//            while i < maxIndex {
+//                let multiplier = w & 1;
+//                // No "if w&1 == 0" here, to avoid a data-dependent path through the code,
+//                // thus reducing the chance of side channel attacks
+//                t0 ^= powTable0[k][i] * multiplier;
+//                t1 ^= powTable1[k][i] * multiplier;
+//                t2 ^= powTable2[k][i] * multiplier;
+//                w = lrs_i64(w, 1);
+//                i += 1;
+//            }
+//        }
+//        GF2_192 { word: [t0, t1, t2] }
+//    }
+//}
+//
+
+/// The following tests closely match those in `ScoreXFoundation/sigmastate-interpreter`.
+#[cfg(test)]
+#[allow(clippy::unwrap_used)]
+mod tests {
+    use super::*;
+    use rand::{thread_rng, Rng};
+
+    #[derive(PartialEq, Eq, Clone)]
+    struct GF2Slow {
+        x: Vec<i64>,
+    }
+
+    impl GF2Slow {
+        fn equals(e: &GF2Slow, that: &[i64]) -> bool {
+            let mut i = 0;
+            while i < std::cmp::min(e.x.len(), that.len()) {
+                if e.x[i] != that[i] {
+                    return false;
+                }
+                i += 1;
+            }
+
+            while i < e.x.len() {
+                if e.x[i] != 0 {
+                    return false;
+                }
+                i += 1;
+            }
+
+            while i < that.len() {
+                if that[i] != 0 {
+                    return false;
+                }
+                i += 1;
+            }
+            true
+        }
+
+        #[allow(clippy::needless_range_loop)]
+        fn mul_bits(a: &[i64], b: &[i64]) -> GF2Slow {
+            let mut c: Vec<_> = std::iter::repeat(0).take(a.len() + b.len()).collect();
+
+            for i in 0..a.len() {
+                for i1 in 0..64 {
+                    for j in 0..b.len() {
+                        for j1 in 0..64 {
+                            if (a[i] & (1 << i1)) != 0 && (b[j] & (1 << j1)) != 0 {
+                                let c_position = i * 64 + i1 + j * 64 + j1;
+                                c[c_position / 64] ^= 1 << (c_position % 64);
+                            }
+                        }
+                    }
+                }
+            }
+            GF2Slow { x: c }
+        }
+
+        fn mod_reduce(poly: &GF2Slow, modulus: Modulus) -> GF2Slow {
+            let mut res = poly.clone();
+            for i in ((modulus.degree as usize)..=(res.x.len() * 64 - 1)).rev() {
+                if (res.x[i >> 6] & (1 << (i & 63))) != 0 {
+                    for j in 0..modulus.offset.len() {
+                        let k = (i as i32) - modulus.offset[j];
+                        res.x[(k as usize) >> 6] ^= 1 << (k & 63);
+                    }
+                }
+            }
+            res
+        }
+    }
+
+    struct Modulus {
+        offset: Vec<i32>,
+        degree: i32,
+    }
+
+    impl Modulus {
+        fn new(sparse_modulus: &[i32]) -> Modulus {
+            let degree = sparse_modulus[0];
+            let mut offset: Vec<_> = std::iter::repeat(0).take(sparse_modulus.len()).collect();
+            for i in 1..sparse_modulus.len() {
+                offset[i] = degree - sparse_modulus[i];
+            }
+            Modulus { offset, degree }
+        }
+    }
+
+    static ZERO: Gf2_192 = Gf2_192 { word: [0, 0, 0] };
+    static ONE: Gf2_192 = Gf2_192 { word: [1, 0, 0] };
+    static PENTANOMIAL: [i32; 5] = [192, 7, 2, 1, 0];
+
+    fn generate_test_values() -> Vec<Gf2_192> {
+        let mut test_values: Vec<[i64; 3]> = std::iter::repeat([0, 0, 0]).take(250).collect();
+        let mut rng = thread_rng();
+
+        // Test single 1s in every bit position but last
+        // (1s in last bit position -- i.e., just the value of 1 -- will be tested separately)
+        let mut j = 0;
+        for i in 1..64 {
+            test_values[j][0] = 1 << i;
+            test_values[j][1] = 0;
+            test_values[j][2] = 0;
+            j += 1;
+        }
+        for i in 0..64 {
+            test_values[j][0] = 0;
+            test_values[j][1] = 1 << i;
+            test_values[j][2] = 0;
+            j += 1;
+        }
+        for i in 0..64 {
+            test_values[j][0] = 0;
+            test_values[j][1] = 0;
+            test_values[j][2] = 1 << i;
+            j += 1;
+        }
+
+        // Test first word zero, last two words random,
+        for _ in 0..5 {
+            test_values[j][0] = 0;
+            test_values[j][1] = rng.gen();
+            test_values[j][2] = rng.gen();
+            j += 1;
+        }
+
+        // and first word random, last two words 0
+        for _ in 0..5 {
+            test_values[j][0] = rng.gen();
+            test_values[j][1] = 0;
+            test_values[j][2] = 0;
+            j += 1;
+        }
+
+        // and first word random, second word 1, last word 0
+        for _ in 0..5 {
+            test_values[j][0] = rng.gen();
+            test_values[j][1] = 1;
+            test_values[j][2] = 0;
+            j += 1;
+        }
+
+        // and last word random, first two words 0
+        for _ in 0..5 {
+            test_values[j][0] = 0;
+            test_values[j][1] = 0;
+            test_values[j][2] = rng.gen();
+            j += 1;
+        }
+
+        while j < test_values.len() {
+            test_values[j][0] = rng.gen();
+            test_values[j][1] = rng.gen();
+            test_values[j][2] = rng.gen();
+            j += 1;
+        }
+
+        test_values.into_iter().map(Gf2_192::from).collect()
+    }
+
+    #[test]
+    fn test_equality() {
+        let mut t = Gf2_192::new();
+        assert!(t.is_zero());
+
+        t = Gf2_192::from(0);
+        assert!(t.is_zero());
+
+        t = Gf2_192::from(1);
+        assert!(t.is_one());
+
+        t = Gf2_192::from(-1);
+        assert_eq!(t.word[0], 0xFFFFFFFF);
+        assert_eq!(t.word[1], 0);
+        assert_eq!(t.word[1], 0);
+
+        let s: [i64; 3] = [123345, 123567891234567, 487237823242367];
+        t = Gf2_192::from(s);
+        let t1 = t;
+        assert_eq!(t, t1);
+
+        let r: [i64; 3] = t.into();
+
+        // Test byte arrays ([i8])
+        let mut b: [i8; 24] = Default::default();
+
+        for i in 0..8 {
+            b[i] = lrs_i64(r[0], (i * 8) as i64) as i8;
+            b[i + 8] = lrs_i64(r[1], (i * 8) as i64) as i8;
+            b[i + 16] = lrs_i64(r[2], (i * 8) as i64) as i8;
+        }
+
+        t = Gf2_192::from(b);
+        let i64_repr: [i64; 3] = t.into();
+        let i8_repr: [i8; 24] = t.into();
+        assert_eq!(r, i64_repr);
+        assert_eq!(b, i8_repr);
+
+        // Extra test of equality for [u8; 24] representation
+        let b_u8_repr: Vec<_> = b.into_iter().map(|x| x as u8).collect();
+        let u8_repr: [u8; 24] = t.into();
+        assert_eq!(b_u8_repr, u8_repr);
+
+        // Test on i8 array with offset
+        let mut b1: [i8; 30] = Default::default();
+        b1[6..].clone_from_slice(&b[..24]);
+        t = Gf2_192::try_from(&b1[6..]).unwrap();
+        let i8_repr: [i8; 24] = t.into();
+        let i64_repr: [i64; 3] = t.into();
+        assert_eq!(b, i8_repr);
+        assert_eq!(r, i64_repr);
+
+        // Testing on 'all ones'.
+        let s: [i64; 3] = [i64::MAX, i64::MAX, i64::MAX];
+        t = Gf2_192::from(s);
+        let i64_repr: [i64; 3] = t.into();
+        assert_eq!(s, i64_repr);
+
+        // Testing 'all ones' from [i8; 24]
+        for i in 0..8 {
+            b[i] = lrs_i64(i64_repr[0], (i * 8) as i64) as i8;
+            b[i + 8] = lrs_i64(i64_repr[1], (i * 8) as i64) as i8;
+            b[i + 16] = lrs_i64(i64_repr[2], (i * 8) as i64) as i8;
+        }
+        t = Gf2_192::from(b);
+        assert_eq!(t.word, i64_repr);
+    }
+
+    #[test]
+    fn test_pow_2_to_2_to_k() {
+        let max_k = 15;
+        for k in 0..max_k {
+            assert_eq!(Gf2_192::power_2_to_2_to_k(ZERO, k), ZERO);
+            assert_eq!(Gf2_192::power_2_to_2_to_k(ONE, k), ONE);
+        }
+
+        assert!(Gf2_192::sqr(ZERO).is_zero());
+        assert!(Gf2_192::sqr(ONE).is_one());
+
+        let mut res1 = Gf2_192::new();
+        #[allow(unused_assignments)]
+        let mut res2 = Gf2_192::new();
+        for z in generate_test_values() {
+            for k in 0..max_k {
+                let res = Gf2_192::power_2_to_2_to_k(z, k);
+                if k == 0 {
+                    // Ground truth for squaring: self-multiply
+                    res1 = z * z; // sqr should equal power_2_to_2_to_k with k = 0
+                    assert_eq!(res, res1);
+                    res2 = Gf2_192::sqr(z);
+                    assert_eq!(res, res2);
+                } else {
+                    // res1 is the ground truth, computed using smaller values of k than is currently being tested
+                    res1 = Gf2_192::power_2_to_2_to_k(res1, k - 1);
+                    assert_eq!(res, res1);
+                }
+            }
+        }
+    }
+
+    #[test]
+    fn test_special_multiplication() {
+        // Run everything times 0 and 0 times everything
+        // and everything times 1 and 1 times everything
+        // where 0 and 1 are GF2_192
+        for z in generate_test_values() {
+            let mut res = z * ZERO;
+            assert!(res.is_zero());
+            res = ZERO * z;
+            assert!(res.is_zero());
+            res = ONE * z;
+            assert_eq!(res, z);
+            res = z * ONE;
+            assert_eq!(res, z);
+        }
+
+        // Run everything times 0
+        // and everything times 1
+        // where 0 and 1 are bytes
+        for z in generate_test_values() {
+            let mut res = Gf2_192::mul_by_i8(z, 0);
+            assert!(res.is_zero());
+            res = Gf2_192::mul_by_i8(z, 1);
+            assert_eq!(res, z);
+        }
+
+        // Run everything times every byte
+        let mut temp = vec![0];
+        for z in generate_test_values() {
+            for i in 2..256 {
+                let m = Modulus::new(&PENTANOMIAL);
+                temp[0] = i;
+                let res = Gf2_192::mul_by_i8(z, i as i8);
+                let res1 = GF2Slow::mul_bits(&z.word, &temp);
+                let res2 = GF2Slow::mod_reduce(&res1, m);
+                assert!(GF2Slow::equals(&res2, &res.word));
+            }
+        }
+    }
+
+    #[test]
+    fn test_special_add() {
+        // Run everything plus 0 and 0 plus everything
+        // where 0 is GF2_192
+        for z in generate_test_values() {
+            let mut res = z + ZERO;
+            assert_eq!(res, z);
+            res = ZERO + z;
+            assert_eq!(res, z);
+        }
+    }
+
+    #[test]
+    fn test_general_add() {
+        let mut res1 = GF2Slow { x: vec![0, 0, 0] };
+
+        // Try everything plus everything in the test array
+        let test_values = generate_test_values();
+        for w in test_values.clone() {
+            for z in test_values.clone() {
+                let res = w + z;
+                res1.x[0] = w.word[0] ^ z.word[0];
+                res1.x[1] = w.word[1] ^ z.word[1];
+                res1.x[2] = w.word[2] ^ z.word[2];
+                assert_eq!(res.word.to_vec(), res1.x);
+            }
+        }
+
+        // Try everything plus self in the test array and make sure you get zeros
+        for z in test_values {
+            let res = z + z;
+            assert!(res.is_zero());
+        }
+    }
+
+    #[test]
+    fn test_general_mult() {
+        let test_values = generate_test_values();
+        // Now run everything times everything in the test array
+        for y in test_values.clone() {
+            for z in test_values.clone() {
+                let m = Modulus::new(&PENTANOMIAL);
+                let res = y * z;
+                let res1 = GF2Slow::mul_bits(&y.word, &z.word);
+                let res2 = GF2Slow::mod_reduce(&res1, m);
+                assert!(
+                    GF2Slow::equals(&res2, &res.word),
+                    "lhs: {:?}, rhs: {:?}, leftarg: {:?}, rightarg: {:?}",
+                    res2.x,
+                    res.word,
+                    y,
+                    z
+                );
+            }
+        }
+    }
+
+    #[test]
+    fn test_inversion() {
+        // Test inversion of 1
+        let mut res = Gf2_192::invert(ONE);
+        assert!(res.is_one());
+
+        // Test inversion of everything
+        for z in generate_test_values() {
+            if z.is_zero() {
+                continue;
+            }
+
+            res = Gf2_192::invert(z);
+            let res1 = z * res;
+            assert!(res1.is_one());
+
+            let m = Modulus::new(&PENTANOMIAL);
+            let res2 = GF2Slow::mul_bits(&res.word, &z.word);
+            let res3 = GF2Slow::mod_reduce(&res2, m);
+            assert!(GF2Slow::equals(&res3, &ONE.word));
+        }
+    }
+}
diff --git a/gf2_192/src/gf2_192poly.rs b/gf2_192/src/gf2_192poly.rs
new file mode 100644
index 000000000..426f2c3f2
--- /dev/null
+++ b/gf2_192/src/gf2_192poly.rs
@@ -0,0 +1,256 @@
+//!  By Leonid Reyzin
+//!  This is free and unencumbered software released into the public domain.
+//!
+//!  Anyone is free to copy, modify, publish, use, compile, sell, or
+//!  distribute this software, either in source code form or as a compiled
+//!  binary, for any purpose, commercial or non-commercial, and by any
+//!  means.
+//!
+//!  In jurisdictions that recognize copyright laws, the author or authors
+//!  of this software dedicate any and all copyright interest in the
+//!  software to the public domain. We make this dedication for the benefit
+//!  of the public at large and to the detriment of our heirs and
+//!  successors. We intend this dedication to be an overt act of
+//!  relinquishment in perpetuity of all present and future rights to this
+//!  software under copyright law.
+//!
+//!  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+//!  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+//!  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+//!  IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
+//!  OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
+//!  ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+//!  OTHER DEALINGS IN THE SOFTWARE.
+//!
+//!  For more information, please refer to <http://unlicense.org>
+
+use thiserror::Error;
+
+use crate::{gf2_192::Gf2_192, Gf2_192Error};
+
+/// Byte representation of the coefficients of `Gf2_192Poly`. Each coefficient is a `[u8; 24]`
+/// representation of a `Gf2_192` instance. Note that the degree zero coefficient is provided
+/// separately in the `coeff0` field.
+pub struct CoefficientsByteRepr<'a> {
+    /// Coefficient of constant term of degree zero.
+    pub coeff0: [u8; 24],
+    /// Ordered coefficients of the non-zero-degree terms, starting with degree 1.
+    pub more_coeffs: &'a [u8],
+}
+
+#[derive(PartialEq, Eq, Clone, Debug)]
+/// A polynomial with coefficients in GF(2^192), whose domain ranges from `[i8::MIN, i8::MAX]`.
+pub struct Gf2_192Poly {
+    /// Coefficients of the polynomial. Must be non-empty.
+    coefficients: Vec<Gf2_192>,
+    /// Upper bound on the degree of the polynomial.
+    degree: usize,
+}
+
+/// `Gf2_192Poly` error
+#[derive(Error, PartialEq, Eq, Debug, Clone)]
+pub enum Gf2_192PolyError {
+    /// `Gf2_192Poly` interpolation error
+    #[error("`Gf2_192Poly::interpolation`: `points.len() != values.len()`")]
+    InterpolatePointsAndValuesLengthDiffer,
+}
+
+impl Gf2_192Poly {
+    /// Create the unique lowest-degree interpolating polynomial that passes through
+    /// `(0, value_at_zero)` and `(points[i], values[i])` for all `i = 0, ..(points.len() - 1)`. i.e.
+    ///  if the returned polynomial is denoted by `f` then
+    ///   - `f(0) == value_at_zero`
+    ///   - `f(points[i]) == values[i]` for all `i = 0, ..(points.len() - 1)`
+    ///
+    /// Assumptions:
+    ///  - Elements of `points` must be distinct `u8` values and must not contain `0`.
+    ///  - `points.len() == values.len()`. Note that `points` and `values` can be empty, resulting
+    ///    in a constant polynomial with value `value_at_zero`.
+    pub fn interpolate(
+        points: &[u8],
+        values: &[Gf2_192],
+        value_at_zero: Gf2_192,
+    ) -> Result<Gf2_192Poly, Gf2_192PolyError> {
+        if points.len() != values.len() {
+            return Err(Gf2_192PolyError::InterpolatePointsAndValuesLengthDiffer);
+        }
+
+        let result_degree = values.len();
+
+        let mut result = Gf2_192Poly::make_constant(result_degree, 0);
+        let mut vanishing_poly = Gf2_192Poly::make_constant(result_degree, 1);
+
+        for i in 0..points.len() {
+            let mut t = result.evaluate(points[i]);
+            let mut s = vanishing_poly.evaluate(points[i]);
+
+            // need to find r such that currentValue+r*valueOfVanishingPoly = values[i]
+            t = t + values[i];
+            s = Gf2_192::invert(s);
+            t = t * s;
+
+            result.add_monic_times_constant(vanishing_poly.clone(), t);
+
+            // Note: internally the domain of the polynomial is not the set of `u8` values but
+            // rather the set of `i8` values. This is because the original implementation from
+            // Reyzin was in Java, a language which does not have unsigned integers.
+            vanishing_poly.multiply_by_linear_binomial(points[i] as i8);
+        }
+
+        // Last point is at 0
+        let mut t = result.coefficients[0]; // evaluating at 0 is easy
+        let mut s = vanishing_poly.coefficients[0]; // evaluating at 0 is easy
+
+        // need to find r such that currentValue+r*valueOfVanishingPoly = valueAt0]
+        t = t + value_at_zero;
+        s = Gf2_192::invert(s);
+        t = t * s;
+        result.add_monic_times_constant(vanishing_poly, t);
+
+        Ok(result)
+    }
+
+    /// Evaluates polynomial at the given point `x`.
+    pub fn evaluate(&self, x: u8) -> Gf2_192 {
+        // Note: internally the domain of the polynomial is not the set of `u8` values but rather
+        // the set of `i8` values. This is because the original implementation from Reyzin was in
+        // Java, a language which does not have unsigned integers.
+        let mut res = self.coefficients[self.degree];
+        if self.degree > 0 {
+            for d in (0..=(self.degree - 1)).rev() {
+                res = Gf2_192::mul_by_i8(res, x as i8);
+                res = res + self.coefficients[d];
+            }
+        }
+        res
+    }
+
+    /// Returns Vec<u8> consisting of the concatenation of all the coefficients of the polynomial.
+    ///  - Degree-zero coefficient is located at index 0
+    ///  - Each coefficient takes 24 bytes for a total of `(self.degree+1)*24` bytes
+    pub fn to_bytes(&self) -> Vec<u8> {
+        let mut res: Vec<_> = std::iter::repeat(0).take((self.degree + 1) * 24).collect();
+        for i in 0..self.degree {
+            #[allow(clippy::unwrap_used)]
+            self.coefficients[i].to_i8_slice(&mut res, i * 24).unwrap();
+        }
+        res.into_iter().map(|x| x as u8).collect()
+    }
+
+    /// Adds r*p to `self`. Assumes:
+    ///  - p is monic
+    ///  - self.coefficients.len() > p.degree
+    ///  - p.degree == self.degree + 1 or (self == 0 and p == 1)
+    fn add_monic_times_constant(&mut self, p: Gf2_192Poly, r: Gf2_192) {
+        let mut _t = Gf2_192::new();
+        for i in 0..p.degree {
+            _t = p.coefficients[i] * r;
+            self.coefficients[i] = self.coefficients[i] + _t;
+        }
+        self.degree = p.degree;
+        self.coefficients[self.degree] = r;
+    }
+
+    /// Multiply `self` by `x + r`. Assumes that `self` is monic (i.e.
+    /// `self.coefficients[self.degree] == 1`)
+    fn multiply_by_linear_binomial(&mut self, r: i8) {
+        self.degree += 1;
+        self.coefficients[self.degree] = Gf2_192::from(1);
+        for i in (1..self.degree).rev() {
+            self.coefficients[i] = Gf2_192::mul_by_i8(self.coefficients[i], r);
+            self.coefficients[i] = self.coefficients[i] + self.coefficients[i - 1];
+        }
+        self.coefficients[0] = Gf2_192::mul_by_i8(self.coefficients[0], r);
+    }
+
+    /// Constructs a constant polynomial (degree 0) which takes value of `constant_term`.
+    /// `max_degree` specifies the maximum degree of the polynomial (to allocate space).
+    fn make_constant(max_degree: usize, constant_term: i32) -> Gf2_192Poly {
+        let mut coefficients: Vec<_> = std::iter::repeat_with(Gf2_192::new)
+            .take(max_degree + 1)
+            .collect();
+        coefficients[0] = Gf2_192::from(constant_term);
+        let degree = 0;
+        Gf2_192Poly {
+            degree,
+            coefficients,
+        }
+    }
+}
+
+impl<'a> TryFrom<CoefficientsByteRepr<'a>> for Gf2_192Poly {
+    type Error = Gf2_192Error;
+
+    /// Constructs the polynomial given the byte array representation of the coefficients. Note that
+    /// the coefficient of degree zero is provided separately (see [`CoefficientsByteRepr`]).
+    fn try_from(c: CoefficientsByteRepr<'a>) -> Result<Self, Self::Error> {
+        let degree = c.more_coeffs.len() / 24;
+        let mut coefficients = Vec::with_capacity(degree + 1);
+        coefficients.push(Gf2_192::from(c.coeff0));
+
+        for i in 1..=degree {
+            coefficients.push(Gf2_192::try_from(&c.more_coeffs[(i - 1) * 24..])?);
+        }
+        Ok(Gf2_192Poly {
+            degree,
+            coefficients,
+        })
+    }
+}
+
+/// The following tests closely match those in `ScoreXFoundation/sigmastate-interpreter`.
+#[cfg(test)]
+#[allow(clippy::unwrap_used)]
+mod tests {
+    use super::*;
+    use rand::{thread_rng, Rng};
+
+    #[test]
+    fn test_interpolation() {
+        // Try with arrays of length 0
+
+        // Constant polynomial with value 0
+        let mut p = Gf2_192Poly::interpolate(&[], &[], Gf2_192::new()).unwrap();
+        assert!(p.evaluate(0).is_zero());
+        assert!(p.evaluate(5).is_zero());
+
+        // Constant polynomial with value 17
+        let val_17 = Gf2_192::from(17);
+        p = Gf2_192Poly::interpolate(&[], &[], val_17).unwrap();
+        assert_eq!(p.evaluate(0), val_17);
+        assert_eq!(p.evaluate(5), val_17);
+
+        let mut rng = thread_rng();
+
+        for len in 1..100 {
+            let mut points: Vec<_> = std::iter::repeat(0).take(len).collect();
+            // Generate a byte that's not an element of `points` nor 0
+            let mut j = 0;
+            while j < points.len() {
+                let b: u8 = rng.gen();
+                if b != 0 && !points.contains(&b) {
+                    points[j] = b;
+                    j += 1;
+                }
+            }
+            // Generate random elements for `values`
+            let mut values: Vec<_> = Vec::with_capacity(len);
+            for _ in 0..len {
+                let b: [i8; 24] = rng.gen();
+                values.push(Gf2_192::from(b));
+            }
+
+            let b: [i8; 24] = rng.gen();
+            let value_at_zero = Gf2_192::from(b);
+            let res = Gf2_192Poly::interpolate(&points, &values, value_at_zero).unwrap();
+
+            // Check that interpolating function hits `values[i]` for every `points[i]`.
+            for i in 0..points.len() {
+                assert_eq!(res.evaluate(points[i]), values[i]);
+            }
+
+            // Check the interpolating function at zero
+            assert_eq!(res.evaluate(0), value_at_zero);
+        }
+    }
+}
diff --git a/gf2_192/src/lib.rs b/gf2_192/src/lib.rs
new file mode 100644
index 000000000..8c759bd79
--- /dev/null
+++ b/gf2_192/src/lib.rs
@@ -0,0 +1,59 @@
+//! Implementation of finite field arithmetic and polynomial interpolation/evaluation in Galois
+//! field GF(2^192).
+
+// Coding conventions
+#![forbid(unsafe_code)]
+#![deny(non_upper_case_globals)]
+#![deny(non_camel_case_types)]
+#![deny(non_snake_case)]
+#![deny(unused_mut)]
+#![deny(dead_code)]
+#![deny(unused_imports)]
+#![deny(missing_docs)]
+// Clippy exclusions
+#![allow(clippy::unit_arg)]
+#![deny(rustdoc::broken_intra_doc_links)]
+#![deny(clippy::unwrap_used)]
+#![deny(clippy::expect_used)]
+#![deny(clippy::todo)]
+#![deny(clippy::unimplemented)]
+#![deny(clippy::panic)]
+
+use derive_more::From;
+use gf2_192poly::Gf2_192PolyError;
+use thiserror::Error;
+
+pub mod gf2_192;
+pub mod gf2_192poly;
+
+/// Logical right shift of i64 values which is equivalent to the `>>>` operator in java/scala. Need
+/// this because rust does 'arithmetical shift right' on signed integers.
+/// See:
+///  - <https://en.wikipedia.org/wiki/Logical_shift>
+///  - <https://en.wikipedia.org/wiki/Arithmetic_shift>
+pub fn lrs_i64(b: i64, s: i64) -> i64 {
+    ((b as u64) >> s) as i64
+}
+
+/// Logical right shift of i8 values which is equivalent to the `>>>` operator in java/scala. Need
+/// this because rust does 'arithmetical shift right' on signed integers.
+/// See:
+///  - <https://en.wikipedia.org/wiki/Logical_shift>
+///  - <https://en.wikipedia.org/wiki/Arithmetic_shift>
+pub fn lrs_i8(b: i8, s: i8) -> i8 {
+    ((b as u8) >> s) as i8
+}
+
+/// General error type for the `gf2_192` crate
+#[derive(Error, PartialEq, Eq, Debug, Clone, From)]
+pub enum Gf2_192Error {
+    /// Failed to create `Gf2_192` from `&[i8]`
+    #[error("Failed to create `Gf2_192` from `&[i8]`")]
+    Gf2_192TryFromByteArrayError,
+    /// Failed to create `Gf2_192` from `&[i8]`
+    #[error("Failed to write `Gf2_192` to `&[i8]`")]
+    Gf2_192ToByteArrayError,
+    /// `Gf2_192Poly` error
+    #[error("`Gf2_192Poly` Error: {0}")]
+    Gf2_192PolyError(Gf2_192PolyError),
+}


Test patch: