//! 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 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 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));
}
}
}