use std::ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign};
use falcon_profiler::profiling;
use itertools::Itertools;
use lazy_static::lazy_static;
use num::{One, Zero};
use num_complex::{Complex, Complex64};
use crate::{
cyclotomic_fourier::CyclotomicFourier,
falcon_field::Felt,
fixed_point::{FixedPoint64, FixedPoint128},
polynomial::Polynomial,
u32_field::U32Field,
};
pub trait FastFft: Sized + Clone {
type Field: Add + Mul + AddAssign + MulAssign + Neg + Sub + SubAssign + One + Zero;
fn fft_inplace(&mut self);
fn fft(&self) -> Self {
let mut a = self.clone();
a.fft_inplace();
a
}
fn merge_fft(a: &Self, b: &Self) -> Self;
fn split_fft(&self) -> (Self, Self);
fn ifft_inplace(&mut self);
fn ifft(&self) -> Self {
let mut a = self.clone();
a.ifft_inplace();
a
}
}
#[allow(clippy::approx_constant)]
const COMPLEX_BITREVERSED_POWERS_1024: [Complex64; 1024] = [
Complex64::new(1.0, 0.0),
Complex64::new(0.00000000000000006123233995736766, 1.0),
Complex64::new(0.7071067811865476, 0.7071067811865475),
Complex64::new(-0.7071067811865475, 0.7071067811865476),
Complex64::new(0.9238795325112867, 0.3826834323650898),
Complex64::new(-0.3826834323650897, 0.9238795325112867),
Complex64::new(0.38268343236508984, 0.9238795325112867),
Complex64::new(-0.9238795325112867, 0.3826834323650899),
Complex64::new(0.9807852804032304, 0.19509032201612825),
Complex64::new(-0.1950903220161282, 0.9807852804032304),
Complex64::new(0.5555702330196023, 0.8314696123025452),
Complex64::new(-0.8314696123025453, 0.5555702330196022),
Complex64::new(0.8314696123025452, 0.5555702330196022),
Complex64::new(-0.555570233019602, 0.8314696123025455),
Complex64::new(0.19509032201612833, 0.9807852804032304),
Complex64::new(-0.9807852804032304, 0.1950903220161286),
Complex64::new(0.9951847266721969, 0.0980171403295606),
Complex64::new(-0.09801714032956065, 0.9951847266721969),
Complex64::new(0.6343932841636455, 0.773010453362737),
Complex64::new(-0.773010453362737, 0.6343932841636455),
Complex64::new(0.881921264348355, 0.47139673682599764),
Complex64::new(-0.4713967368259977, 0.881921264348355),
Complex64::new(0.29028467725446233, 0.9569403357322089),
Complex64::new(-0.9569403357322088, 0.2902846772544624),
Complex64::new(0.9569403357322088, 0.29028467725446233),
Complex64::new(-0.29028467725446216, 0.9569403357322089),
Complex64::new(0.4713967368259978, 0.8819212643483549),
Complex64::new(-0.8819212643483549, 0.47139673682599786),
Complex64::new(0.773010453362737, 0.6343932841636455),
Complex64::new(-0.6343932841636454, 0.7730104533627371),
Complex64::new(0.09801714032956077, 0.9951847266721968),
Complex64::new(-0.9951847266721968, 0.09801714032956083),
Complex64::new(0.9987954562051724, 0.049067674327418015),
Complex64::new(-0.04906767432741801, 0.9987954562051724),
Complex64::new(0.6715589548470183, 0.7409511253549591),
Complex64::new(-0.7409511253549589, 0.6715589548470186),
Complex64::new(0.9039892931234433, 0.4275550934302821),
Complex64::new(-0.42755509343028186, 0.9039892931234434),
Complex64::new(0.33688985339222005, 0.9415440651830208),
Complex64::new(-0.9415440651830207, 0.33688985339222033),
Complex64::new(0.970031253194544, 0.24298017990326387),
Complex64::new(-0.24298017990326387, 0.970031253194544),
Complex64::new(0.5141027441932217, 0.8577286100002721),
Complex64::new(-0.857728610000272, 0.5141027441932218),
Complex64::new(0.8032075314806449, 0.5956993044924334),
Complex64::new(-0.5956993044924334, 0.8032075314806449),
Complex64::new(0.14673047445536175, 0.989176509964781),
Complex64::new(-0.989176509964781, 0.1467304744553618),
Complex64::new(0.989176509964781, 0.14673047445536175),
Complex64::new(-0.14673047445536164, 0.989176509964781),
Complex64::new(0.5956993044924335, 0.8032075314806448),
Complex64::new(-0.8032075314806448, 0.5956993044924335),
Complex64::new(0.8577286100002721, 0.5141027441932217),
Complex64::new(-0.5141027441932217, 0.8577286100002721),
Complex64::new(0.24298017990326398, 0.970031253194544),
Complex64::new(-0.970031253194544, 0.24298017990326407),
Complex64::new(0.9415440651830208, 0.33688985339222005),
Complex64::new(-0.33688985339221994, 0.9415440651830208),
Complex64::new(0.4275550934302822, 0.9039892931234433),
Complex64::new(-0.9039892931234433, 0.42755509343028203),
Complex64::new(0.7409511253549591, 0.6715589548470183),
Complex64::new(-0.6715589548470184, 0.740951125354959),
Complex64::new(0.049067674327418126, 0.9987954562051724),
Complex64::new(-0.9987954562051724, 0.049067674327417966),
Complex64::new(0.9996988186962042, 0.024541228522912288),
Complex64::new(-0.024541228522912142, 0.9996988186962042),
Complex64::new(0.6895405447370669, 0.7242470829514669),
Complex64::new(-0.7242470829514668, 0.689540544737067),
Complex64::new(0.9142097557035307, 0.40524131400498986),
Complex64::new(-0.40524131400498975, 0.9142097557035307),
Complex64::new(0.3598950365349883, 0.9329927988347388),
Complex64::new(-0.9329927988347388, 0.35989503653498833),
Complex64::new(0.9757021300385286, 0.2191012401568698),
Complex64::new(-0.21910124015686966, 0.9757021300385286),
Complex64::new(0.5349976198870973, 0.844853565249707),
Complex64::new(-0.8448535652497071, 0.5349976198870972),
Complex64::new(0.8175848131515837, 0.5758081914178453),
Complex64::new(-0.5758081914178453, 0.8175848131515837),
Complex64::new(0.17096188876030136, 0.9852776423889412),
Complex64::new(-0.9852776423889412, 0.17096188876030122),
Complex64::new(0.99247953459871, 0.1224106751992162),
Complex64::new(-0.12241067519921615, 0.99247953459871),
Complex64::new(0.6152315905806268, 0.7883464276266062),
Complex64::new(-0.7883464276266062, 0.6152315905806269),
Complex64::new(0.8700869911087115, 0.49289819222978404),
Complex64::new(-0.492898192229784, 0.8700869911087115),
Complex64::new(0.2667127574748984, 0.9637760657954398),
Complex64::new(-0.9637760657954398, 0.2667127574748985),
Complex64::new(0.9495281805930367, 0.3136817403988915),
Complex64::new(-0.3136817403988914, 0.9495281805930367),
Complex64::new(0.4496113296546066, 0.8932243011955153),
Complex64::new(-0.8932243011955152, 0.4496113296546069),
Complex64::new(0.7572088465064846, 0.6531728429537768),
Complex64::new(-0.6531728429537765, 0.7572088465064847),
Complex64::new(0.07356456359966745, 0.9972904566786902),
Complex64::new(-0.9972904566786902, 0.07356456359966773),
Complex64::new(0.9972904566786902, 0.07356456359966743),
Complex64::new(-0.07356456359966733, 0.9972904566786902),
Complex64::new(0.6531728429537768, 0.7572088465064845),
Complex64::new(-0.7572088465064846, 0.6531728429537766),
Complex64::new(0.8932243011955153, 0.44961132965460654),
Complex64::new(-0.4496113296546067, 0.8932243011955152),
Complex64::new(0.3136817403988916, 0.9495281805930367),
Complex64::new(-0.9495281805930367, 0.3136817403988914),
Complex64::new(0.9637760657954398, 0.26671275747489837),
Complex64::new(-0.2667127574748983, 0.9637760657954398),
Complex64::new(0.4928981922297841, 0.8700869911087113),
Complex64::new(-0.8700869911087113, 0.49289819222978415),
Complex64::new(0.7883464276266063, 0.6152315905806268),
Complex64::new(-0.6152315905806267, 0.7883464276266063),
Complex64::new(0.12241067519921628, 0.99247953459871),
Complex64::new(-0.99247953459871, 0.12241067519921635),
Complex64::new(0.9852776423889412, 0.17096188876030122),
Complex64::new(-0.17096188876030124, 0.9852776423889412),
Complex64::new(0.5758081914178453, 0.8175848131515837),
Complex64::new(-0.8175848131515836, 0.5758081914178454),
Complex64::new(0.8448535652497071, 0.5349976198870972),
Complex64::new(-0.534997619887097, 0.8448535652497072),
Complex64::new(0.21910124015686977, 0.9757021300385286),
Complex64::new(-0.9757021300385285, 0.21910124015687005),
Complex64::new(0.932992798834739, 0.3598950365349881),
Complex64::new(-0.35989503653498817, 0.9329927988347388),
Complex64::new(0.40524131400498986, 0.9142097557035307),
Complex64::new(-0.9142097557035307, 0.4052413140049899),
Complex64::new(0.724247082951467, 0.6895405447370668),
Complex64::new(-0.6895405447370669, 0.7242470829514669),
Complex64::new(0.024541228522912264, 0.9996988186962042),
Complex64::new(-0.9996988186962042, 0.024541228522912326),
Complex64::new(0.9999247018391445, 0.012271538285719925),
Complex64::new(-0.012271538285719823, 0.9999247018391445),
Complex64::new(0.6983762494089729, 0.7157308252838186),
Complex64::new(-0.7157308252838186, 0.6983762494089729),
Complex64::new(0.9191138516900578, 0.3939920400610481),
Complex64::new(-0.393992040061048, 0.9191138516900578),
Complex64::new(0.3713171939518376, 0.9285060804732155),
Complex64::new(-0.9285060804732155, 0.3713171939518377),
Complex64::new(0.9783173707196277, 0.20711137619221856),
Complex64::new(-0.20711137619221845, 0.9783173707196277),
Complex64::new(0.5453249884220465, 0.838224705554838),
Complex64::new(-0.8382247055548381, 0.5453249884220464),
Complex64::new(0.8245893027850253, 0.5657318107836131),
Complex64::new(-0.5657318107836132, 0.8245893027850252),
Complex64::new(0.18303988795514106, 0.9831054874312163),
Complex64::new(-0.9831054874312163, 0.1830398879551409),
Complex64::new(0.9939069700023561, 0.11022220729388306),
Complex64::new(-0.11022220729388306, 0.9939069700023561),
Complex64::new(0.6248594881423865, 0.7807372285720944),
Complex64::new(-0.7807372285720945, 0.6248594881423863),
Complex64::new(0.8760700941954066, 0.4821837720791227),
Complex64::new(-0.4821837720791227, 0.8760700941954066),
Complex64::new(0.27851968938505306, 0.9604305194155658),
Complex64::new(-0.9604305194155658, 0.27851968938505317),
Complex64::new(0.9533060403541939, 0.3020059493192281),
Complex64::new(-0.3020059493192281, 0.9533060403541939),
Complex64::new(0.46053871095824, 0.8876396204028539),
Complex64::new(-0.8876396204028538, 0.4605387109582402),
Complex64::new(0.765167265622459, 0.6438315428897914),
Complex64::new(-0.6438315428897913, 0.7651672656224591),
Complex64::new(0.08579731234443988, 0.996312612182778),
Complex64::new(-0.996312612182778, 0.08579731234444016),
Complex64::new(0.9981181129001492, 0.06132073630220858),
Complex64::new(-0.06132073630220853, 0.9981181129001492),
Complex64::new(0.6624157775901718, 0.7491363945234593),
Complex64::new(-0.7491363945234591, 0.662415777590172),
Complex64::new(0.8986744656939538, 0.43861623853852766),
Complex64::new(-0.4386162385385274, 0.8986744656939539),
Complex64::new(0.325310292162263, 0.9456073253805213),
Complex64::new(-0.9456073253805212, 0.32531029216226326),
Complex64::new(0.9669764710448521, 0.25486565960451457),
Complex64::new(-0.2548656596045145, 0.9669764710448521),
Complex64::new(0.5035383837257176, 0.8639728561215867),
Complex64::new(-0.8639728561215867, 0.5035383837257177),
Complex64::new(0.7958369046088836, 0.6055110414043255),
Complex64::new(-0.6055110414043254, 0.7958369046088836),
Complex64::new(0.13458070850712622, 0.99090263542778),
Complex64::new(-0.99090263542778, 0.13458070850712628),
Complex64::new(0.9873014181578584, 0.15885814333386145),
Complex64::new(-0.15885814333386128, 0.9873014181578584),
Complex64::new(0.5857978574564389, 0.8104571982525948),
Complex64::new(-0.8104571982525947, 0.585797857456439),
Complex64::new(0.8513551931052652, 0.524589682678469),
Complex64::new(-0.5245896826784687, 0.8513551931052652),
Complex64::new(0.23105810828067128, 0.9729399522055601),
Complex64::new(-0.9729399522055601, 0.23105810828067133),
Complex64::new(0.937339011912575, 0.34841868024943456),
Complex64::new(-0.3484186802494344, 0.937339011912575),
Complex64::new(0.4164295600976373, 0.9091679830905223),
Complex64::new(-0.9091679830905224, 0.41642956009763715),
Complex64::new(0.7326542716724128, 0.680600997795453),
Complex64::new(-0.680600997795453, 0.7326542716724128),
Complex64::new(0.03680722294135899, 0.9993223845883495),
Complex64::new(-0.9993223845883495, 0.03680722294135883),
Complex64::new(0.9993223845883495, 0.03680722294135883),
Complex64::new(-0.036807222941358866, 0.9993223845883495),
Complex64::new(0.6806009977954531, 0.7326542716724128),
Complex64::new(-0.7326542716724127, 0.6806009977954532),
Complex64::new(0.9091679830905224, 0.41642956009763715),
Complex64::new(-0.416429560097637, 0.9091679830905225),
Complex64::new(0.3484186802494345, 0.937339011912575),
Complex64::new(-0.9373390119125748, 0.3484186802494348),
Complex64::new(0.9729399522055602, 0.2310581082806711),
Complex64::new(-0.23105810828067114, 0.9729399522055602),
Complex64::new(0.5245896826784688, 0.8513551931052652),
Complex64::new(-0.8513551931052652, 0.524589682678469),
Complex64::new(0.8104571982525948, 0.5857978574564389),
Complex64::new(-0.5857978574564389, 0.8104571982525948),
Complex64::new(0.1588581433338614, 0.9873014181578584),
Complex64::new(-0.9873014181578584, 0.15885814333386147),
Complex64::new(0.99090263542778, 0.13458070850712617),
Complex64::new(-0.1345807085071261, 0.99090263542778),
Complex64::new(0.6055110414043255, 0.7958369046088835),
Complex64::new(-0.7958369046088835, 0.6055110414043257),
Complex64::new(0.8639728561215868, 0.5035383837257176),
Complex64::new(-0.5035383837257175, 0.8639728561215868),
Complex64::new(0.2548656596045146, 0.9669764710448521),
Complex64::new(-0.9669764710448521, 0.2548656596045147),
Complex64::new(0.9456073253805213, 0.3253102921622629),
Complex64::new(-0.32531029216226287, 0.9456073253805214),
Complex64::new(0.4386162385385277, 0.8986744656939538),
Complex64::new(-0.8986744656939539, 0.43861623853852755),
Complex64::new(0.7491363945234594, 0.6624157775901718),
Complex64::new(-0.6624157775901719, 0.7491363945234593),
Complex64::new(0.06132073630220865, 0.9981181129001492),
Complex64::new(-0.9981181129001492, 0.06132073630220849),
Complex64::new(0.996312612182778, 0.0857973123444399),
Complex64::new(-0.08579731234443976, 0.996312612182778),
Complex64::new(0.6438315428897915, 0.765167265622459),
Complex64::new(-0.765167265622459, 0.6438315428897914),
Complex64::new(0.8876396204028539, 0.46053871095824),
Complex64::new(-0.46053871095824006, 0.8876396204028539),
Complex64::new(0.3020059493192282, 0.9533060403541938),
Complex64::new(-0.9533060403541939, 0.30200594931922803),
Complex64::new(0.9604305194155658, 0.27851968938505306),
Complex64::new(-0.27851968938505295, 0.9604305194155659),
Complex64::new(0.48218377207912283, 0.8760700941954066),
Complex64::new(-0.8760700941954065, 0.4821837720791229),
Complex64::new(0.7807372285720945, 0.6248594881423863),
Complex64::new(-0.6248594881423862, 0.7807372285720946),
Complex64::new(0.11022220729388318, 0.9939069700023561),
Complex64::new(-0.9939069700023561, 0.11022220729388324),
Complex64::new(0.9831054874312163, 0.18303988795514095),
Complex64::new(-0.18303988795514092, 0.9831054874312163),
Complex64::new(0.5657318107836132, 0.8245893027850253),
Complex64::new(-0.8245893027850251, 0.5657318107836135),
Complex64::new(0.8382247055548381, 0.5453249884220465),
Complex64::new(-0.5453249884220462, 0.8382247055548382),
Complex64::new(0.20711137619221856, 0.9783173707196277),
Complex64::new(-0.9783173707196275, 0.20711137619221884),
Complex64::new(0.9285060804732156, 0.37131719395183754),
Complex64::new(-0.3713171939518375, 0.9285060804732156),
Complex64::new(0.3939920400610481, 0.9191138516900578),
Complex64::new(-0.9191138516900578, 0.39399204006104815),
Complex64::new(0.7157308252838186, 0.6983762494089729),
Complex64::new(-0.6983762494089728, 0.7157308252838187),
Complex64::new(0.012271538285719944, 0.9999247018391445),
Complex64::new(-0.9999247018391445, 0.012271538285720007),
Complex64::new(0.9999811752826011, 0.006135884649154475),
Complex64::new(-0.006135884649154393, 0.9999811752826011),
Complex64::new(0.7027547444572253, 0.7114321957452164),
Complex64::new(-0.7114321957452165, 0.7027547444572252),
Complex64::new(0.921514039342042, 0.38834504669882625),
Complex64::new(-0.3883450466988262, 0.921514039342042),
Complex64::new(0.3770074102164183, 0.9262102421383113),
Complex64::new(-0.9262102421383114, 0.37700741021641815),
Complex64::new(0.9795697656854405, 0.2011046348420919),
Complex64::new(-0.20110463484209182, 0.9795697656854405),
Complex64::new(0.5504579729366048, 0.83486287498638),
Complex64::new(-0.83486287498638, 0.5504579729366049),
Complex64::new(0.8280450452577558, 0.560661576197336),
Complex64::new(-0.5606615761973359, 0.8280450452577558),
Complex64::new(0.18906866414980628, 0.9819638691095552),
Complex64::new(-0.9819638691095552, 0.18906866414980636),
Complex64::new(0.9945645707342554, 0.10412163387205459),
Complex64::new(-0.1041216338720546, 0.9945645707342554),
Complex64::new(0.6296382389149271, 0.7768884656732324),
Complex64::new(-0.7768884656732323, 0.6296382389149272),
Complex64::new(0.8790122264286335, 0.4767992300633221),
Complex64::new(-0.4767992300633219, 0.8790122264286335),
Complex64::new(0.2844075372112718, 0.9587034748958716),
Complex64::new(-0.9587034748958715, 0.2844075372112721),
Complex64::new(0.9551411683057708, 0.2961508882436238),
Complex64::new(-0.29615088824362384, 0.9551411683057707),
Complex64::new(0.4659764957679661, 0.8847970984309378),
Complex64::new(-0.8847970984309378, 0.4659764957679662),
Complex64::new(0.7691033376455797, 0.6391244448637757),
Complex64::new(-0.6391244448637757, 0.7691033376455796),
Complex64::new(0.0919089564971327, 0.9957674144676598),
Complex64::new(-0.9957674144676598, 0.09190895649713275),
Complex64::new(0.9984755805732948, 0.055195244349689934),
Complex64::new(-0.05519524434968991, 0.9984755805732948),
Complex64::new(0.6669999223036375, 0.745057785441466),
Complex64::new(-0.745057785441466, 0.6669999223036376),
Complex64::new(0.901348847046022, 0.43309381885315196),
Complex64::new(-0.4330938188531519, 0.901348847046022),
Complex64::new(0.33110630575987643, 0.9435934581619604),
Complex64::new(-0.9435934581619604, 0.3311063057598765),
Complex64::new(0.9685220942744174, 0.24892760574572015),
Complex64::new(-0.24892760574572012, 0.9685220942744174),
Complex64::new(0.508830142543107, 0.8608669386377673),
Complex64::new(-0.8608669386377671, 0.5088301425431073),
Complex64::new(0.799537269107905, 0.600616479383869),
Complex64::new(-0.6006164793838688, 0.7995372691079052),
Complex64::new(0.14065823933284924, 0.9900582102622971),
Complex64::new(-0.990058210262297, 0.14065823933284954),
Complex64::new(0.9882575677307495, 0.15279718525844344),
Complex64::new(-0.1527971852584433, 0.9882575677307495),
Complex64::new(0.5907597018588743, 0.8068475535437992),
Complex64::new(-0.8068475535437993, 0.5907597018588742),
Complex64::new(0.8545579883654005, 0.5193559901655896),
Complex64::new(-0.5193559901655896, 0.8545579883654005),
Complex64::new(0.23702360599436734, 0.9715038909862518),
Complex64::new(-0.9715038909862518, 0.23702360599436717),
Complex64::new(0.9394592236021899, 0.3426607173119944),
Complex64::new(-0.34266071731199427, 0.9394592236021899),
Complex64::new(0.4220002707997998, 0.9065957045149153),
Complex64::new(-0.9065957045149153, 0.42200027079979985),
Complex64::new(0.7368165688773699, 0.6760927035753159),
Complex64::new(-0.6760927035753158, 0.73681656887737),
Complex64::new(0.04293825693494096, 0.9990777277526454),
Complex64::new(-0.9990777277526454, 0.04293825693494102),
Complex64::new(0.9995294175010931, 0.030674803176636626),
Complex64::new(-0.03067480317663646, 0.9995294175010931),
Complex64::new(0.6850836677727004, 0.7284643904482252),
Complex64::new(-0.7284643904482252, 0.6850836677727004),
Complex64::new(0.9117060320054299, 0.4108431710579039),
Complex64::new(-0.4108431710579038, 0.9117060320054299),
Complex64::new(0.3541635254204905, 0.9351835099389475),
Complex64::new(-0.9351835099389476, 0.3541635254204904),
Complex64::new(0.9743393827855759, 0.22508391135979283),
Complex64::new(-0.22508391135979267, 0.9743393827855759),
Complex64::new(0.5298036246862948, 0.8481203448032971),
Complex64::new(-0.8481203448032971, 0.5298036246862948),
Complex64::new(0.8140363297059484, 0.5808139580957645),
Complex64::new(-0.5808139580957644, 0.8140363297059485),
Complex64::new(0.1649131204899701, 0.9863080972445987),
Complex64::new(-0.9863080972445986, 0.16491312048997014),
Complex64::new(0.9917097536690995, 0.12849811079379317),
Complex64::new(-0.1284981107937931, 0.9917097536690995),
Complex64::new(0.6103828062763095, 0.7921065773002124),
Complex64::new(-0.7921065773002122, 0.6103828062763097),
Complex64::new(0.8670462455156926, 0.49822766697278187),
Complex64::new(-0.4982276669727816, 0.8670462455156928),
Complex64::new(0.26079411791527557, 0.9653944416976894),
Complex64::new(-0.9653944416976893, 0.26079411791527585),
Complex64::new(0.9475855910177411, 0.3195020308160157),
Complex64::new(-0.31950203081601564, 0.9475855910177412),
Complex64::new(0.44412214457042926, 0.8959662497561851),
Complex64::new(-0.8959662497561851, 0.4441221445704293),
Complex64::new(0.7531867990436125, 0.6578066932970786),
Complex64::new(-0.6578066932970786, 0.7531867990436125),
Complex64::new(0.0674439195636641, 0.9977230666441916),
Complex64::new(-0.9977230666441916, 0.06744391956366418),
Complex64::new(0.9968202992911657, 0.07968243797143013),
Complex64::new(-0.07968243797143001, 0.9968202992911658),
Complex64::new(0.6485144010221126, 0.7612023854842618),
Complex64::new(-0.7612023854842617, 0.6485144010221126),
Complex64::new(0.8904487232447579, 0.45508358712634384),
Complex64::new(-0.4550835871263437, 0.890448723244758),
Complex64::new(0.307849640041535, 0.9514350209690083),
Complex64::new(-0.9514350209690083, 0.30784964004153503),
Complex64::new(0.9621214042690416, 0.272621355449949),
Complex64::new(-0.27262135544994887, 0.9621214042690416),
Complex64::new(0.48755016014843605, 0.8730949784182901),
Complex64::new(-0.8730949784182901, 0.4875501601484359),
Complex64::new(0.7845565971555752, 0.6200572117632891),
Complex64::new(-0.6200572117632892, 0.7845565971555751),
Complex64::new(0.11631863091190488, 0.9932119492347945),
Complex64::new(-0.9932119492347945, 0.11631863091190471),
Complex64::new(0.984210092386929, 0.17700422041214875),
Complex64::new(-0.17700422041214875, 0.984210092386929),
Complex64::new(0.5707807458869674, 0.8211025149911046),
Complex64::new(-0.8211025149911046, 0.5707807458869673),
Complex64::new(0.8415549774368984, 0.5401714727298929),
Complex64::new(-0.5401714727298929, 0.8415549774368984),
Complex64::new(0.21311031991609136, 0.9770281426577544),
Complex64::new(-0.9770281426577544, 0.21311031991609142),
Complex64::new(0.9307669610789837, 0.36561299780477385),
Complex64::new(-0.36561299780477385, 0.9307669610789837),
Complex64::new(0.3996241998456468, 0.9166790599210427),
Complex64::new(-0.9166790599210426, 0.39962419984564707),
Complex64::new(0.7200025079613817, 0.693971460889654),
Complex64::new(-0.6939714608896538, 0.7200025079613818),
Complex64::new(0.01840672990580482, 0.9998305817958234),
Complex64::new(-0.9998305817958234, 0.0184067299058051),
Complex64::new(0.9998305817958234, 0.01840672990580482),
Complex64::new(-0.018406729905804695, 0.9998305817958234),
Complex64::new(0.693971460889654, 0.7200025079613817),
Complex64::new(-0.7200025079613817, 0.693971460889654),
Complex64::new(0.9166790599210427, 0.3996241998456468),
Complex64::new(-0.3996241998456467, 0.9166790599210427),
Complex64::new(0.36561299780477396, 0.9307669610789837),
Complex64::new(-0.9307669610789837, 0.3656129978047738),
Complex64::new(0.9770281426577544, 0.21311031991609136),
Complex64::new(-0.21311031991609125, 0.9770281426577544),
Complex64::new(0.540171472729893, 0.8415549774368983),
Complex64::new(-0.8415549774368983, 0.540171472729893),
Complex64::new(0.8211025149911046, 0.5707807458869673),
Complex64::new(-0.5707807458869671, 0.8211025149911048),
Complex64::new(0.17700422041214886, 0.984210092386929),
Complex64::new(-0.984210092386929, 0.17700422041214894),
Complex64::new(0.9932119492347945, 0.11631863091190475),
Complex64::new(-0.11631863091190475, 0.9932119492347945),
Complex64::new(0.6200572117632892, 0.7845565971555752),
Complex64::new(-0.784556597155575, 0.6200572117632894),
Complex64::new(0.8730949784182901, 0.487550160148436),
Complex64::new(-0.4875501601484357, 0.8730949784182902),
Complex64::new(0.272621355449949, 0.9621214042690416),
Complex64::new(-0.9621214042690415, 0.27262135544994925),
Complex64::new(0.9514350209690083, 0.30784964004153487),
Complex64::new(-0.30784964004153487, 0.9514350209690083),
Complex64::new(0.45508358712634384, 0.8904487232447579),
Complex64::new(-0.8904487232447579, 0.4550835871263439),
Complex64::new(0.7612023854842618, 0.6485144010221124),
Complex64::new(-0.6485144010221124, 0.7612023854842619),
Complex64::new(0.07968243797143013, 0.9968202992911657),
Complex64::new(-0.9968202992911657, 0.0796824379714302),
Complex64::new(0.9977230666441916, 0.06744391956366405),
Complex64::new(-0.06744391956366398, 0.9977230666441916),
Complex64::new(0.6578066932970786, 0.7531867990436124),
Complex64::new(-0.7531867990436124, 0.6578066932970787),
Complex64::new(0.8959662497561852, 0.4441221445704292),
Complex64::new(-0.44412214457042914, 0.8959662497561852),
Complex64::new(0.31950203081601575, 0.9475855910177411),
Complex64::new(-0.9475855910177411, 0.3195020308160158),
Complex64::new(0.9653944416976894, 0.2607941179152755),
Complex64::new(-0.26079411791527546, 0.9653944416976894),
Complex64::new(0.49822766697278187, 0.8670462455156926),
Complex64::new(-0.8670462455156928, 0.49822766697278176),
Complex64::new(0.7921065773002124, 0.6103828062763095),
Complex64::new(-0.6103828062763096, 0.7921065773002123),
Complex64::new(0.12849811079379322, 0.9917097536690995),
Complex64::new(-0.9917097536690995, 0.12849811079379309),
Complex64::new(0.9863080972445987, 0.16491312048996992),
Complex64::new(-0.16491312048996995, 0.9863080972445987),
Complex64::new(0.5808139580957645, 0.8140363297059483),
Complex64::new(-0.8140363297059484, 0.5808139580957645),
Complex64::new(0.8481203448032972, 0.5298036246862946),
Complex64::new(-0.5298036246862947, 0.8481203448032972),
Complex64::new(0.22508391135979278, 0.9743393827855759),
Complex64::new(-0.9743393827855759, 0.22508391135979283),
Complex64::new(0.9351835099389476, 0.35416352542049034),
Complex64::new(-0.3541635254204904, 0.9351835099389476),
Complex64::new(0.4108431710579039, 0.9117060320054299),
Complex64::new(-0.9117060320054298, 0.41084317105790413),
Complex64::new(0.7284643904482252, 0.6850836677727004),
Complex64::new(-0.6850836677727002, 0.7284643904482253),
Complex64::new(0.03067480317663658, 0.9995294175010931),
Complex64::new(-0.9995294175010931, 0.030674803176636865),
Complex64::new(0.9990777277526454, 0.04293825693494082),
Complex64::new(-0.042938256934940834, 0.9990777277526454),
Complex64::new(0.676092703575316, 0.7368165688773698),
Complex64::new(-0.7368165688773699, 0.6760927035753159),
Complex64::new(0.9065957045149153, 0.4220002707997997),
Complex64::new(-0.4220002707997997, 0.9065957045149153),
Complex64::new(0.3426607173119944, 0.9394592236021899),
Complex64::new(-0.9394592236021899, 0.34266071731199443),
Complex64::new(0.9715038909862518, 0.2370236059943672),
Complex64::new(-0.23702360599436723, 0.9715038909862518),
Complex64::new(0.5193559901655895, 0.8545579883654005),
Complex64::new(-0.8545579883654004, 0.5193559901655898),
Complex64::new(0.8068475535437993, 0.5907597018588742),
Complex64::new(-0.590759701858874, 0.8068475535437994),
Complex64::new(0.1527971852584434, 0.9882575677307495),
Complex64::new(-0.9882575677307495, 0.15279718525844369),
Complex64::new(0.9900582102622971, 0.1406582393328492),
Complex64::new(-0.14065823933284913, 0.9900582102622971),
Complex64::new(0.600616479383869, 0.799537269107905),
Complex64::new(-0.7995372691079051, 0.6006164793838689),
Complex64::new(0.8608669386377673, 0.508830142543107),
Complex64::new(-0.5088301425431071, 0.8608669386377672),
Complex64::new(0.24892760574572026, 0.9685220942744173),
Complex64::new(-0.9685220942744174, 0.2489276057457201),
Complex64::new(0.9435934581619604, 0.33110630575987643),
Complex64::new(-0.3311063057598763, 0.9435934581619604),
Complex64::new(0.433093818853152, 0.901348847046022),
Complex64::new(-0.9013488470460219, 0.43309381885315207),
Complex64::new(0.7450577854414661, 0.6669999223036375),
Complex64::new(-0.6669999223036374, 0.7450577854414661),
Complex64::new(0.05519524434969003, 0.9984755805732948),
Complex64::new(-0.9984755805732948, 0.055195244349690094),
Complex64::new(0.9957674144676598, 0.09190895649713272),
Complex64::new(-0.09190895649713257, 0.9957674144676598),
Complex64::new(0.6391244448637757, 0.7691033376455796),
Complex64::new(-0.7691033376455795, 0.6391244448637758),
Complex64::new(0.8847970984309378, 0.4659764957679662),
Complex64::new(-0.465976495767966, 0.8847970984309379),
Complex64::new(0.29615088824362396, 0.9551411683057707),
Complex64::new(-0.9551411683057707, 0.296150888243624),
Complex64::new(0.9587034748958716, 0.2844075372112719),
Complex64::new(-0.2844075372112717, 0.9587034748958716),
Complex64::new(0.47679923006332225, 0.8790122264286334),
Complex64::new(-0.8790122264286335, 0.4767992300633221),
Complex64::new(0.7768884656732324, 0.629638238914927),
Complex64::new(-0.6296382389149271, 0.7768884656732324),
Complex64::new(0.10412163387205473, 0.9945645707342554),
Complex64::new(-0.9945645707342554, 0.10412163387205457),
Complex64::new(0.9819638691095552, 0.1890686641498062),
Complex64::new(-0.18906866414980616, 0.9819638691095552),
Complex64::new(0.560661576197336, 0.8280450452577558),
Complex64::new(-0.8280450452577557, 0.5606615761973361),
Complex64::new(0.83486287498638, 0.5504579729366048),
Complex64::new(-0.5504579729366047, 0.8348628749863801),
Complex64::new(0.20110463484209196, 0.9795697656854405),
Complex64::new(-0.9795697656854405, 0.201104634842092),
Complex64::new(0.9262102421383114, 0.37700741021641826),
Complex64::new(-0.3770074102164182, 0.9262102421383114),
Complex64::new(0.3883450466988263, 0.9215140393420419),
Complex64::new(-0.9215140393420418, 0.3883450466988266),
Complex64::new(0.7114321957452164, 0.7027547444572253),
Complex64::new(-0.7027547444572251, 0.7114321957452167),
Complex64::new(0.006135884649154515, 0.9999811752826011),
Complex64::new(-0.9999811752826011, 0.006135884649154799),
Complex64::new(0.9999952938095762, 0.003067956762965976),
Complex64::new(-0.0030679567629660156, 0.9999952938095762),
Complex64::new(0.704934080375905, 0.7092728264388656),
Complex64::new(-0.7092728264388655, 0.7049340803759051),
Complex64::new(0.9227011283338786, 0.38551605384391885),
Complex64::new(-0.3855160538439189, 0.9227011283338785),
Complex64::new(0.3798472089240511, 0.9250492407826776),
Complex64::new(-0.9250492407826775, 0.3798472089240514),
Complex64::new(0.9801821359681174, 0.19809841071795356),
Complex64::new(-0.19809841071795362, 0.9801821359681174),
Complex64::new(0.5530167055800276, 0.8331701647019132),
Complex64::new(-0.8331701647019132, 0.5530167055800276),
Complex64::new(0.829761233794523, 0.5581185312205561),
Complex64::new(-0.5581185312205561, 0.829761233794523),
Complex64::new(0.19208039704989238, 0.9813791933137546),
Complex64::new(-0.9813791933137546, 0.19208039704989247),
Complex64::new(0.9948793307948056, 0.10106986275482782),
Complex64::new(-0.10106986275482775, 0.9948793307948056),
Complex64::new(0.6320187359398091, 0.7749531065948738),
Complex64::new(-0.7749531065948738, 0.6320187359398091),
Complex64::new(0.8804708890521608, 0.47410021465054997),
Complex64::new(-0.4741002146505499, 0.8804708890521609),
Complex64::new(0.28734745954472957, 0.9578264130275329),
Complex64::new(-0.9578264130275329, 0.2873474595447296),
Complex64::new(0.9560452513499964, 0.29321916269425863),
Complex64::new(-0.2932191626942586, 0.9560452513499965),
Complex64::new(0.46868882203582796, 0.8833633386657316),
Complex64::new(-0.8833633386657317, 0.46868882203582785),
Complex64::new(0.7710605242618138, 0.6367618612362842),
Complex64::new(-0.6367618612362843, 0.7710605242618137),
Complex64::new(0.09496349532963906, 0.9954807554919269),
Complex64::new(-0.9954807554919269, 0.09496349532963891),
Complex64::new(0.9986402181802653, 0.052131704680283324),
Complex64::new(-0.05213170468028319, 0.9986402181802653),
Complex64::new(0.669282588346636, 0.7430079521351217),
Complex64::new(-0.7430079521351217, 0.669282588346636),
Complex64::new(0.9026733182372588, 0.4303264813400826),
Complex64::new(-0.4303264813400827, 0.9026733182372588),
Complex64::new(0.3339996514420095, 0.9425731976014469),
Complex64::new(-0.9425731976014469, 0.3339996514420094),
Complex64::new(0.9692812353565485, 0.2459550503357946),
Complex64::new(-0.24595505033579448, 0.9692812353565485),
Complex64::new(0.5114688504379705, 0.8593018183570084),
Complex64::new(-0.8593018183570084, 0.5114688504379705),
Complex64::new(0.8013761717231402, 0.5981607069963423),
Complex64::new(-0.5981607069963422, 0.8013761717231404),
Complex64::new(0.14369503315029458, 0.9896220174632008),
Complex64::new(-0.9896220174632008, 0.14369503315029464),
Complex64::new(0.9887216919603238, 0.1497645346773215),
Complex64::new(-0.1497645346773215, 0.9887216919603238),
Complex64::new(0.5932322950397998, 0.8050313311429637),
Complex64::new(-0.8050313311429634, 0.5932322950398),
Complex64::new(0.8561473283751945, 0.5167317990176499),
Complex64::new(-0.5167317990176497, 0.8561473283751946),
Complex64::new(0.2400030224487415, 0.9707721407289504),
Complex64::new(-0.9707721407289502, 0.24000302244874178),
Complex64::new(0.9405060705932683, 0.33977688440682685),
Complex64::new(-0.33977688440682685, 0.9405060705932683),
Complex64::new(0.4247796812091088, 0.9052967593181188),
Complex64::new(-0.9052967593181187, 0.42477968120910886),
Complex64::new(0.7388873244606151, 0.673829000378756),
Complex64::new(-0.673829000378756, 0.7388873244606152),
Complex64::new(0.046003182130914644, 0.9989412931868569),
Complex64::new(-0.9989412931868569, 0.046003182130914706),
Complex64::new(0.9996188224951786, 0.02760814577896574),
Complex64::new(-0.027608145778965698, 0.9996188224951786),
Complex64::new(0.6873153408917592, 0.726359155084346),
Complex64::new(-0.7263591550843458, 0.6873153408917593),
Complex64::new(0.9129621904283982, 0.4080441628649787),
Complex64::new(-0.40804416286497863, 0.9129621904283982),
Complex64::new(0.35703096123343003, 0.9340925504042589),
Complex64::new(-0.9340925504042588, 0.3570309612334303),
Complex64::new(0.9750253450669941, 0.2220936209732035),
Complex64::new(-0.22209362097320348, 0.9750253450669941),
Complex64::new(0.532403127877198, 0.846490938774052),
Complex64::new(-0.846490938774052, 0.532403127877198),
Complex64::new(0.8158144108067338, 0.5783137964116556),
Complex64::new(-0.5783137964116555, 0.8158144108067338),
Complex64::new(0.16793829497473123, 0.9857975091675674),
Complex64::new(-0.9857975091675674, 0.16793829497473128),
Complex64::new(0.9920993131421918, 0.12545498341154623),
Complex64::new(-0.12545498341154607, 0.9920993131421918),
Complex64::new(0.6128100824294097, 0.79023022143731),
Complex64::new(-0.7902302214373099, 0.6128100824294098),
Complex64::new(0.8685707059713409, 0.49556526182577254),
Complex64::new(-0.4955652618257724, 0.868570705971341),
Complex64::new(0.2637546789748315, 0.9645897932898126),
Complex64::new(-0.9645897932898126, 0.26375467897483157),
Complex64::new(0.9485613499157303, 0.31659337555616585),
Complex64::new(-0.31659337555616573, 0.9485613499157304),
Complex64::new(0.4468688401623743, 0.8945994856313826),
Complex64::new(-0.8945994856313827, 0.44686884016237416),
Complex64::new(0.7552013768965365, 0.6554928529996153),
Complex64::new(-0.6554928529996155, 0.7552013768965365),
Complex64::new(0.07050457338961401, 0.9975114561403035),
Complex64::new(-0.9975114561403035, 0.07050457338961386),
Complex64::new(0.997060070339483, 0.07662386139203149),
Complex64::new(-0.0766238613920315, 0.997060070339483),
Complex64::new(0.650846684996381, 0.759209188978388),
Complex64::new(-0.7592091889783881, 0.650846684996381),
Complex64::new(0.8918407093923427, 0.4523495872337709),
Complex64::new(-0.4523495872337709, 0.8918407093923427),
Complex64::new(0.3107671527496115, 0.9504860739494817),
Complex64::new(-0.9504860739494817, 0.31076715274961153),
Complex64::new(0.9629532668736839, 0.2696683255729151),
Complex64::new(-0.2696683255729151, 0.9629532668736839),
Complex64::new(0.4902264832882911, 0.8715950866559511),
Complex64::new(-0.8715950866559509, 0.4902264832882914),
Complex64::new(0.7864552135990858, 0.6176473079378039),
Complex64::new(-0.6176473079378038, 0.7864552135990859),
Complex64::new(0.11936521481099135, 0.9928504144598651),
Complex64::new(-0.9928504144598651, 0.11936521481099163),
Complex64::new(0.9847485018019042, 0.17398387338746382),
Complex64::new(-0.1739838733874637, 0.9847485018019042),
Complex64::new(0.5732971666980423, 0.8193475200767969),
Complex64::new(-0.819347520076797, 0.5732971666980421),
Complex64::new(0.8432082396418454, 0.5375870762956454),
Complex64::new(-0.5375870762956456, 0.8432082396418454),
Complex64::new(0.2161067970762196, 0.9763697313300211),
Complex64::new(-0.9763697313300211, 0.21610679707621944),
Complex64::new(0.9318842655816681, 0.3627557243673972),
Complex64::new(-0.3627557243673971, 0.9318842655816681),
Complex64::new(0.40243465085941854, 0.9154487160882678),
Complex64::new(-0.9154487160882677, 0.4024346508594186),
Complex64::new(0.7221281939292153, 0.6917592583641577),
Complex64::new(-0.6917592583641576, 0.7221281939292155),
Complex64::new(0.021474080275469605, 0.9997694053512153),
Complex64::new(-0.9997694053512153, 0.021474080275469667),
Complex64::new(0.9998823474542126, 0.0153392062849881),
Complex64::new(-0.015339206284988098, 0.9998823474542126),
Complex64::new(0.696177131491463, 0.7178700450557317),
Complex64::new(-0.7178700450557316, 0.6961771314914631),
Complex64::new(0.9179007756213905, 0.3968099874167103),
Complex64::new(-0.3968099874167103, 0.9179007756213905),
Complex64::new(0.3684668299533723, 0.9296408958431813),
Complex64::new(-0.9296408958431812, 0.3684668299533726),
Complex64::new(0.9776773578245099, 0.2101118368804696),
Complex64::new(-0.2101118368804696, 0.9776773578245099),
Complex64::new(0.542750784864516, 0.8398937941959994),
Complex64::new(-0.8398937941959995, 0.5427507848645159),
Complex64::new(0.8228497813758264, 0.5682589526701315),
Complex64::new(-0.5682589526701315, 0.8228497813758263),
Complex64::new(0.18002290140569951, 0.9836624192117303),
Complex64::new(-0.9836624192117303, 0.18002290140569957),
Complex64::new(0.9935641355205953, 0.11327095217756435),
Complex64::new(-0.11327095217756424, 0.9935641355205953),
Complex64::new(0.6224612793741501, 0.7826505961665757),
Complex64::new(-0.7826505961665756, 0.6224612793741501),
Complex64::new(0.8745866522781761, 0.48486924800079106),
Complex64::new(-0.484869248000791, 0.8745866522781762),
Complex64::new(0.27557181931095825, 0.9612804858113206),
Complex64::new(-0.9612804858113206, 0.2755718193109583),
Complex64::new(0.9523750127197659, 0.3049292297354024),
Complex64::new(-0.30492922973540226, 0.9523750127197659),
Complex64::new(0.4578133035988773, 0.8890483558546646),
Complex64::new(-0.8890483558546646, 0.4578133035988772),
Complex64::new(0.7631884172633813, 0.6461760129833163),
Complex64::new(-0.6461760129833164, 0.7631884172633813),
Complex64::new(0.0827402645493758, 0.9965711457905548),
Complex64::new(-0.9965711457905548, 0.08274026454937564),
Complex64::new(0.997925286198596, 0.06438263092985747),
Complex64::new(-0.06438263092985728, 0.997925286198596),
Complex64::new(0.6601143420674205, 0.7511651319096864),
Complex64::new(-0.7511651319096865, 0.6601143420674205),
Complex64::new(0.8973245807054183, 0.44137126873171667),
Complex64::new(-0.4413712687317167, 0.8973245807054183),
Complex64::new(0.32240767880107, 0.9466009130832835),
Complex64::new(-0.9466009130832835, 0.32240767880106985),
Complex64::new(0.9661900034454125, 0.257831102162159),
Complex64::new(-0.2578311021621588, 0.9661900034454126),
Complex64::new(0.5008853826112409, 0.865513624090569),
Complex64::new(-0.865513624090569, 0.5008853826112409),
Complex64::new(0.7939754775543372, 0.6079497849677736),
Complex64::new(-0.6079497849677735, 0.7939754775543373),
Complex64::new(0.13154002870288328, 0.9913108598461154),
Complex64::new(-0.9913108598461154, 0.13154002870288334),
Complex64::new(0.9868094018141855, 0.16188639378011183),
Complex64::new(-0.16188639378011177, 0.9868094018141855),
Complex64::new(0.5833086529376983, 0.8122505865852039),
Complex64::new(-0.8122505865852038, 0.5833086529376985),
Complex64::new(0.8497417680008525, 0.5271991347819013),
Complex64::new(-0.5271991347819011, 0.8497417680008527),
Complex64::new(0.2280720831708858, 0.9736442496508119),
Complex64::new(-0.9736442496508119, 0.22807208317088606),
Complex64::new(0.9362656671702783, 0.3512927560855671),
Complex64::new(-0.35129275608556704, 0.9362656671702783),
Complex64::new(0.41363831223843456, 0.9104412922580671),
Complex64::new(-0.9104412922580671, 0.4136383122384346),
Complex64::new(0.7305627692278276, 0.6828455463852481),
Complex64::new(-0.682845546385248, 0.7305627692278276),
Complex64::new(0.03374117185137764, 0.9994306045554617),
Complex64::new(-0.9994306045554617, 0.033741171851377705),
Complex64::new(0.9992047586183639, 0.03987292758773981),
Complex64::new(-0.03987292758773973, 0.9992047586183639),
Complex64::new(0.6783500431298616, 0.7347388780959634),
Complex64::new(-0.7347388780959635, 0.6783500431298614),
Complex64::new(0.9078861164876663, 0.4192168883632239),
Complex64::new(-0.41921688836322407, 0.9078861164876662),
Complex64::new(0.34554132496398915, 0.9384035340631081),
Complex64::new(-0.9384035340631082, 0.345541324963989),
Complex64::new(0.9722264970789363, 0.23404195858354343),
Complex64::new(-0.23404195858354332, 0.9722264970789364),
Complex64::new(0.5219752929371544, 0.8529606049303636),
Complex64::new(-0.8529606049303636, 0.5219752929371545),
Complex64::new(0.808656181588175, 0.5882815482226452),
Complex64::new(-0.5882815482226452, 0.8086561815881751),
Complex64::new(0.15582839765426532, 0.9877841416445722),
Complex64::new(-0.9877841416445722, 0.15582839765426537),
Complex64::new(0.9904850842564571, 0.13762012158648604),
Complex64::new(-0.13762012158648607, 0.990485084256457),
Complex64::new(0.6030665985403483, 0.797690840943391),
Complex64::new(-0.7976908409433909, 0.6030665985403484),
Complex64::new(0.8624239561110406, 0.5061866453451552),
Complex64::new(-0.5061866453451551, 0.8624239561110406),
Complex64::new(0.2518978181542169, 0.9677538370934755),
Complex64::new(-0.9677538370934754, 0.2518978181542172),
Complex64::new(0.9446048372614803, 0.3282098435790925),
Complex64::new(-0.32820984357909255, 0.9446048372614803),
Complex64::new(0.4358570799222555, 0.9000158920161603),
Complex64::new(-0.9000158920161602, 0.43585707992225553),
Complex64::new(0.7471006059801801, 0.6647109782033448),
Complex64::new(-0.6647109782033449, 0.7471006059801801),
Complex64::new(0.05825826450043573, 0.9983015449338929),
Complex64::new(-0.9983015449338929, 0.058258264500435794),
Complex64::new(0.996044700901252, 0.0888535525825246),
Complex64::new(-0.08885355258252456, 0.996044700901252),
Complex64::new(0.6414810128085832, 0.7671389119358204),
Complex64::new(-0.7671389119358203, 0.6414810128085832),
Complex64::new(0.8862225301488806, 0.46325978355186015),
Complex64::new(-0.46325978355186015, 0.8862225301488806),
Complex64::new(0.2990798263080405, 0.9542280951091057),
Complex64::new(-0.9542280951091056, 0.29907982630804053),
Complex64::new(0.9595715130819845, 0.28146493792575794),
Complex64::new(-0.28146493792575794, 0.9595715130819845),
Complex64::new(0.479493757660153, 0.8775452902072612),
Complex64::new(-0.8775452902072611, 0.4794937576601533),
Complex64::new(0.778816512381476, 0.6272518154951441),
Complex64::new(-0.6272518154951439, 0.7788165123814761),
Complex64::new(0.10717242495680887, 0.9942404494531879),
Complex64::new(-0.9942404494531879, 0.10717242495680916),
Complex64::new(0.9825393022874412, 0.18605515166344663),
Complex64::new(-0.1860551516634465, 0.9825393022874412),
Complex64::new(0.5631993440138341, 0.8263210628456634),
Complex64::new(-0.8263210628456635, 0.5631993440138341),
Complex64::new(0.836547727223512, 0.5478940591731002),
Complex64::new(-0.5478940591731002, 0.836547727223512),
Complex64::new(0.204108966092817, 0.9789481753190622),
Complex64::new(-0.9789481753190622, 0.20410896609281684),
Complex64::new(0.9273625256504011, 0.37416406297145793),
Complex64::new(-0.3741640629714579, 0.9273625256504011),
Complex64::new(0.391170384302254, 0.9203182767091105),
Complex64::new(-0.9203182767091105, 0.39117038430225404),
Complex64::new(0.7135848687807936, 0.7005687939432483),
Complex64::new(-0.7005687939432482, 0.7135848687807937),
Complex64::new(0.00920375478205996, 0.9999576445519639),
Complex64::new(-0.9999576445519639, 0.00920375478206002),
Complex64::new(0.9999576445519639, 0.00920375478205982),
Complex64::new(-0.009203754782059837, 0.9999576445519639),
Complex64::new(0.7005687939432484, 0.7135848687807935),
Complex64::new(-0.7135848687807936, 0.7005687939432483),
Complex64::new(0.9203182767091106, 0.39117038430225387),
Complex64::new(-0.39117038430225387, 0.9203182767091106),
Complex64::new(0.374164062971458, 0.9273625256504011),
Complex64::new(-0.9273625256504011, 0.37416406297145804),
Complex64::new(0.9789481753190622, 0.20410896609281687),
Complex64::new(-0.2041089660928169, 0.9789481753190622),
Complex64::new(0.5478940591731002, 0.8365477272235119),
Complex64::new(-0.8365477272235119, 0.5478940591731004),
Complex64::new(0.8263210628456635, 0.5631993440138341),
Complex64::new(-0.563199344013834, 0.8263210628456636),
Complex64::new(0.18605515166344663, 0.9825393022874412),
Complex64::new(-0.9825393022874412, 0.1860551516634469),
Complex64::new(0.9942404494531879, 0.10717242495680884),
Complex64::new(-0.10717242495680876, 0.9942404494531879),
Complex64::new(0.6272518154951442, 0.7788165123814759),
Complex64::new(-0.778816512381476, 0.6272518154951441),
Complex64::new(0.8775452902072614, 0.479493757660153),
Complex64::new(-0.4794937576601531, 0.8775452902072612),
Complex64::new(0.28146493792575805, 0.9595715130819845),
Complex64::new(-0.9595715130819845, 0.2814649379257579),
Complex64::new(0.9542280951091057, 0.2990798263080405),
Complex64::new(-0.29907982630804036, 0.9542280951091057),
Complex64::new(0.46325978355186026, 0.8862225301488806),
Complex64::new(-0.8862225301488805, 0.4632597835518603),
Complex64::new(0.7671389119358204, 0.6414810128085832),
Complex64::new(-0.641481012808583, 0.7671389119358205),
Complex64::new(0.08885355258252468, 0.996044700901252),
Complex64::new(-0.996044700901252, 0.08885355258252475),
Complex64::new(0.9983015449338929, 0.05825826450043575),
Complex64::new(-0.05825826450043561, 0.9983015449338929),
Complex64::new(0.6647109782033449, 0.7471006059801801),
Complex64::new(-0.74710060598018, 0.664710978203345),
Complex64::new(0.9000158920161603, 0.4358570799222555),
Complex64::new(-0.43585707992225536, 0.9000158920161603),
Complex64::new(0.32820984357909266, 0.9446048372614803),
Complex64::new(-0.9446048372614801, 0.3282098435790927),
Complex64::new(0.9677538370934755, 0.25189781815421697),
Complex64::new(-0.2518978181542168, 0.9677538370934755),
Complex64::new(0.5061866453451555, 0.8624239561110405),
Complex64::new(-0.8624239561110405, 0.5061866453451552),
Complex64::new(0.7976908409433912, 0.6030665985403482),
Complex64::new(-0.6030665985403483, 0.797690840943391),
Complex64::new(0.13762012158648618, 0.990485084256457),
Complex64::new(-0.9904850842564571, 0.13762012158648604),
Complex64::new(0.9877841416445722, 0.15582839765426523),
Complex64::new(-0.1558283976542652, 0.9877841416445722),
Complex64::new(0.5882815482226453, 0.808656181588175),
Complex64::new(-0.808656181588175, 0.5882815482226453),
Complex64::new(0.8529606049303636, 0.5219752929371544),
Complex64::new(-0.5219752929371543, 0.8529606049303637),
Complex64::new(0.23404195858354346, 0.9722264970789363),
Complex64::new(-0.9722264970789363, 0.2340419585835435),
Complex64::new(0.9384035340631081, 0.3455413249639891),
Complex64::new(-0.34554132496398904, 0.9384035340631082),
Complex64::new(0.41921688836322396, 0.9078861164876662),
Complex64::new(-0.907886116487666, 0.41921688836322424),
Complex64::new(0.7347388780959635, 0.6783500431298615),
Complex64::new(-0.6783500431298612, 0.7347388780959636),
Complex64::new(0.039872927587739845, 0.9992047586183639),
Complex64::new(-0.9992047586183639, 0.03987292758774013),
Complex64::new(0.9994306045554617, 0.03374117185137758),
Complex64::new(-0.03374117185137752, 0.9994306045554617),
Complex64::new(0.6828455463852481, 0.7305627692278276),
Complex64::new(-0.7305627692278275, 0.6828455463852482),
Complex64::new(0.9104412922580672, 0.4136383122384345),
Complex64::new(-0.41363831223843445, 0.9104412922580672),
Complex64::new(0.35129275608556715, 0.9362656671702783),
Complex64::new(-0.9362656671702783, 0.3512927560855672),
Complex64::new(0.973644249650812, 0.22807208317088573),
Complex64::new(-0.22807208317088568, 0.973644249650812),
Complex64::new(0.5271991347819014, 0.8497417680008524),
Complex64::new(-0.8497417680008525, 0.5271991347819013),
Complex64::new(0.8122505865852039, 0.5833086529376983),
Complex64::new(-0.5833086529376984, 0.8122505865852039),
Complex64::new(0.16188639378011188, 0.9868094018141854),
Complex64::new(-0.9868094018141855, 0.16188639378011174),
Complex64::new(0.9913108598461154, 0.13154002870288312),
Complex64::new(-0.13154002870288314, 0.9913108598461154),
Complex64::new(0.6079497849677737, 0.7939754775543372),
Complex64::new(-0.7939754775543372, 0.6079497849677736),
Complex64::new(0.8655136240905691, 0.5008853826112407),
Complex64::new(-0.5008853826112408, 0.8655136240905691),
Complex64::new(0.25783110216215893, 0.9661900034454126),
Complex64::new(-0.9661900034454125, 0.257831102162159),
Complex64::new(0.9466009130832835, 0.32240767880106985),
Complex64::new(-0.32240767880106985, 0.9466009130832835),
Complex64::new(0.4413712687317166, 0.8973245807054183),
Complex64::new(-0.8973245807054182, 0.4413712687317169),
Complex64::new(0.7511651319096865, 0.6601143420674205),
Complex64::new(-0.6601143420674204, 0.7511651319096866),
Complex64::new(0.06438263092985741, 0.997925286198596),
Complex64::new(-0.997925286198596, 0.0643826309298577),
Complex64::new(0.9965711457905548, 0.08274026454937569),
Complex64::new(-0.08274026454937568, 0.9965711457905548),
Complex64::new(0.6461760129833164, 0.7631884172633813),
Complex64::new(-0.763188417263381, 0.6461760129833166),
Complex64::new(0.8890483558546646, 0.4578133035988772),
Complex64::new(-0.457813303598877, 0.8890483558546647),
Complex64::new(0.30492922973540243, 0.9523750127197659),
Complex64::new(-0.9523750127197658, 0.30492922973540265),
Complex64::new(0.9612804858113206, 0.27557181931095814),
Complex64::new(-0.27557181931095814, 0.9612804858113206),
Complex64::new(0.4848692480007911, 0.8745866522781761),
Complex64::new(-0.8745866522781761, 0.4848692480007911),
Complex64::new(0.7826505961665757, 0.62246127937415),
Complex64::new(-0.62246127937415, 0.7826505961665757),
Complex64::new(0.11327095217756436, 0.9935641355205953),
Complex64::new(-0.9935641355205953, 0.11327095217756442),
Complex64::new(0.9836624192117303, 0.18002290140569951),
Complex64::new(-0.1800229014056994, 0.9836624192117303),
Complex64::new(0.5682589526701315, 0.8228497813758263),
Complex64::new(-0.8228497813758262, 0.5682589526701317),
Complex64::new(0.8398937941959995, 0.5427507848645159),
Complex64::new(-0.5427507848645158, 0.8398937941959996),
Complex64::new(0.21011183688046972, 0.9776773578245099),
Complex64::new(-0.9776773578245099, 0.2101118368804698),
Complex64::new(0.9296408958431813, 0.3684668299533723),
Complex64::new(-0.3684668299533722, 0.9296408958431813),
Complex64::new(0.3968099874167104, 0.9179007756213904),
Complex64::new(-0.9179007756213905, 0.39680998741671025),
Complex64::new(0.7178700450557317, 0.696177131491463),
Complex64::new(-0.696177131491463, 0.7178700450557317),
Complex64::new(0.01533920628498822, 0.9998823474542126),
Complex64::new(-0.9998823474542126, 0.01533920628498806),
Complex64::new(0.9997694053512153, 0.021474080275469508),
Complex64::new(-0.021474080275469484, 0.9997694053512153),
Complex64::new(0.6917592583641577, 0.7221281939292153),
Complex64::new(-0.7221281939292152, 0.6917592583641579),
Complex64::new(0.9154487160882678, 0.40243465085941843),
Complex64::new(-0.40243465085941843, 0.9154487160882678),
Complex64::new(0.3627557243673972, 0.9318842655816681),
Complex64::new(-0.931884265581668, 0.3627557243673973),
Complex64::new(0.9763697313300211, 0.21610679707621952),
Complex64::new(-0.2161067970762195, 0.9763697313300211),
Complex64::new(0.5375870762956455, 0.8432082396418454),
Complex64::new(-0.8432082396418453, 0.5375870762956457),
Complex64::new(0.8193475200767969, 0.5732971666980422),
Complex64::new(-0.573297166698042, 0.8193475200767971),
Complex64::new(0.17398387338746385, 0.9847485018019042),
Complex64::new(-0.9847485018019042, 0.17398387338746413),
Complex64::new(0.9928504144598651, 0.11936521481099135),
Complex64::new(-0.11936521481099123, 0.9928504144598651),
Complex64::new(0.617647307937804, 0.7864552135990858),
Complex64::new(-0.7864552135990858, 0.6176473079378039),
Complex64::new(0.871595086655951, 0.49022648328829116),
Complex64::new(-0.4902264832882912, 0.871595086655951),
Complex64::new(0.2696683255729152, 0.9629532668736839),
Complex64::new(-0.9629532668736839, 0.2696683255729151),
Complex64::new(0.9504860739494817, 0.3107671527496115),
Complex64::new(-0.31076715274961136, 0.9504860739494818),
Complex64::new(0.452349587233771, 0.8918407093923427),
Complex64::new(-0.8918407093923426, 0.45234958723377106),
Complex64::new(0.7592091889783881, 0.6508466849963809),
Complex64::new(-0.6508466849963808, 0.7592091889783882),
Complex64::new(0.07662386139203162, 0.997060070339483),
Complex64::new(-0.997060070339483, 0.07662386139203169),
Complex64::new(0.9975114561403035, 0.07050457338961386),
Complex64::new(-0.0705045733896139, 0.9975114561403035),
Complex64::new(0.6554928529996155, 0.7552013768965365),
Complex64::new(-0.7552013768965364, 0.6554928529996156),
Complex64::new(0.8945994856313827, 0.44686884016237416),
Complex64::new(-0.446868840162374, 0.8945994856313828),
Complex64::new(0.31659337555616585, 0.9485613499157303),
Complex64::new(-0.9485613499157303, 0.31659337555616607),
Complex64::new(0.9645897932898128, 0.26375467897483135),
Complex64::new(-0.2637546789748314, 0.9645897932898128),
Complex64::new(0.4955652618257725, 0.8685707059713409),
Complex64::new(-0.8685707059713409, 0.49556526182577254),
Complex64::new(0.79023022143731, 0.6128100824294097),
Complex64::new(-0.6128100824294097, 0.79023022143731),
Complex64::new(0.1254549834115462, 0.9920993131421918),
Complex64::new(-0.9920993131421918, 0.12545498341154626),
Complex64::new(0.9857975091675675, 0.16793829497473117),
Complex64::new(-0.1679382949747311, 0.9857975091675675),
Complex64::new(0.5783137964116556, 0.8158144108067338),
Complex64::new(-0.8158144108067337, 0.5783137964116557),
Complex64::new(0.8464909387740521, 0.5324031278771979),
Complex64::new(-0.5324031278771979, 0.8464909387740521),
Complex64::new(0.2220936209732036, 0.9750253450669941),
Complex64::new(-0.9750253450669941, 0.22209362097320365),
Complex64::new(0.934092550404259, 0.35703096123343),
Complex64::new(-0.3570309612334299, 0.934092550404259),
Complex64::new(0.40804416286497874, 0.9129621904283981),
Complex64::new(-0.9129621904283982, 0.4080441628649786),
Complex64::new(0.726359155084346, 0.687315340891759),
Complex64::new(-0.6873153408917592, 0.7263591550843459),
Complex64::new(0.02760814577896582, 0.9996188224951786),
Complex64::new(-0.9996188224951786, 0.02760814577896566),
Complex64::new(0.9989412931868569, 0.04600318213091462),
Complex64::new(-0.04600318213091452, 0.9989412931868569),
Complex64::new(0.6738290003787561, 0.7388873244606151),
Complex64::new(-0.738887324460615, 0.6738290003787561),
Complex64::new(0.9052967593181188, 0.4247796812091088),
Complex64::new(-0.4247796812091087, 0.9052967593181188),
Complex64::new(0.33977688440682696, 0.9405060705932683),
Complex64::new(-0.9405060705932683, 0.339776884406827),
Complex64::new(0.9707721407289504, 0.2400030224487415),
Complex64::new(-0.2400030224487414, 0.9707721407289504),
Complex64::new(0.51673179901765, 0.8561473283751945),
Complex64::new(-0.8561473283751945, 0.5167317990176498),
Complex64::new(0.8050313311429637, 0.5932322950397998),
Complex64::new(-0.5932322950397999, 0.8050313311429635),
Complex64::new(0.14976453467732162, 0.9887216919603238),
Complex64::new(-0.9887216919603238, 0.14976453467732145),
Complex64::new(0.9896220174632009, 0.14369503315029447),
Complex64::new(-0.14369503315029444, 0.9896220174632009),
Complex64::new(0.5981607069963424, 0.8013761717231401),
Complex64::new(-0.8013761717231402, 0.5981607069963424),
Complex64::new(0.8593018183570085, 0.5114688504379703),
Complex64::new(-0.5114688504379704, 0.8593018183570084),
Complex64::new(0.2459550503357946, 0.9692812353565485),
Complex64::new(-0.9692812353565484, 0.24595505033579465),
Complex64::new(0.9425731976014469, 0.3339996514420094),
Complex64::new(-0.3339996514420094, 0.9425731976014469),
Complex64::new(0.4303264813400826, 0.9026733182372588),
Complex64::new(-0.9026733182372587, 0.4303264813400829),
Complex64::new(0.7430079521351217, 0.669282588346636),
Complex64::new(-0.6692825883466359, 0.7430079521351218),
Complex64::new(0.05213170468028332, 0.9986402181802653),
Complex64::new(-0.9986402181802652, 0.052131704680283594),
Complex64::new(0.9954807554919269, 0.09496349532963899),
Complex64::new(-0.09496349532963895, 0.9954807554919269),
Complex64::new(0.6367618612362842, 0.7710605242618137),
Complex64::new(-0.7710605242618136, 0.6367618612362844),
Complex64::new(0.8833633386657316, 0.4686888220358279),
Complex64::new(-0.4686888220358277, 0.8833633386657317),
Complex64::new(0.2932191626942587, 0.9560452513499964),
Complex64::new(-0.9560452513499963, 0.29321916269425896),
Complex64::new(0.9578264130275329, 0.2873474595447295),
Complex64::new(-0.28734745954472946, 0.9578264130275329),
Complex64::new(0.47410021465055, 0.8804708890521608),
Complex64::new(-0.8804708890521608, 0.4741002146505501),
Complex64::new(0.7749531065948739, 0.6320187359398091),
Complex64::new(-0.632018735939809, 0.7749531065948739),
Complex64::new(0.10106986275482788, 0.9948793307948056),
Complex64::new(-0.9948793307948056, 0.10106986275482793),
Complex64::new(0.9813791933137546, 0.19208039704989244),
Complex64::new(-0.19208039704989227, 0.9813791933137546),
Complex64::new(0.5581185312205561, 0.829761233794523),
Complex64::new(-0.8297612337945229, 0.5581185312205563),
Complex64::new(0.8331701647019132, 0.5530167055800275),
Complex64::new(-0.5530167055800274, 0.8331701647019133),
Complex64::new(0.19809841071795373, 0.9801821359681173),
Complex64::new(-0.9801821359681173, 0.1980984107179538),
Complex64::new(0.9250492407826776, 0.37984720892405116),
Complex64::new(-0.379847208924051, 0.9250492407826777),
Complex64::new(0.385516053843919, 0.9227011283338785),
Complex64::new(-0.9227011283338786, 0.38551605384391885),
Complex64::new(0.7092728264388657, 0.7049340803759049),
Complex64::new(-0.7049340803759049, 0.7092728264388656),
Complex64::new(0.003067956762966138, 0.9999952938095762),
Complex64::new(-0.9999952938095762, 0.003067956762965977),
];
impl FastFft for Polynomial<Complex64> {
type Field = Complex64;
fn fft_inplace(&mut self) {
Complex64::fft(&mut self.coefficients, &COMPLEX_BITREVERSED_POWERS_1024);
}
fn ifft_inplace(&mut self) {
let n = self.coefficients.len();
let psi_inv_rev = &COMPLEX_BITREVERSED_POWERS_1024
.iter()
.take(n)
.map(|c| Complex64::new(c.re, -c.im))
.collect_vec();
let ninv = Complex64::new(1.0 / (n as f64), 0.0);
Complex64::ifft(&mut self.coefficients, psi_inv_rev, ninv);
}
fn merge_fft(a: &Self, b: &Self) -> Self {
Self {
coefficients: Self::Field::merge_fft(
&a.coefficients,
&b.coefficients,
&COMPLEX_BITREVERSED_POWERS_1024,
),
}
}
fn split_fft(&self) -> (Self, Self) {
let n = self.coefficients.len();
let psi_inv_rev = &COMPLEX_BITREVERSED_POWERS_1024
.iter()
.take(n)
.map(|c| Complex64::new(c.re, -c.im))
.collect_vec();
let (a, b) = Self::Field::split_fft(&self.coefficients, psi_inv_rev);
(Self { coefficients: a }, Self { coefficients: b })
}
}
type ComplexFP = Complex<FixedPoint64>;
lazy_static! {
static ref FP_BITREVERSED_POWERS_1024: Vec<ComplexFP> =
ComplexFP::bitreversed_powers(1024);
}
impl FastFft for Polynomial<ComplexFP> {
type Field = ComplexFP;
fn fft_inplace(&mut self) {
ComplexFP::fft(&mut self.coefficients, &FP_BITREVERSED_POWERS_1024);
}
fn ifft_inplace(&mut self) {
let n = self.coefficients.len();
let psi_inv_rev = FP_BITREVERSED_POWERS_1024
.iter()
.take(n)
.map(|c| Complex::new(c.re, -c.im))
.collect_vec();
let ninv = Complex::new(
FixedPoint64::ONE / FixedPoint64::from(n as i32),
FixedPoint64::ZERO,
);
ComplexFP::ifft(&mut self.coefficients, &psi_inv_rev, ninv);
}
fn merge_fft(a: &Self, b: &Self) -> Self {
Self {
coefficients: ComplexFP::merge_fft(
&a.coefficients,
&b.coefficients,
&FP_BITREVERSED_POWERS_1024,
),
}
}
fn split_fft(&self) -> (Self, Self) {
let n = self.coefficients.len();
let psi_inv_rev = FP_BITREVERSED_POWERS_1024
.iter()
.take(n)
.map(|c| Complex::new(c.re, -c.im))
.collect_vec();
let (a, b) = ComplexFP::split_fft(&self.coefficients, &psi_inv_rev);
(Self { coefficients: a }, Self { coefficients: b })
}
}
type ComplexFixed128 = Complex<FixedPoint128>;
lazy_static! {
static ref FIXED128_BITREVERSED_POWERS_1024: Vec<ComplexFixed128> =
ComplexFixed128::bitreversed_powers(1024);
}
impl FastFft for Polynomial<ComplexFixed128> {
type Field = ComplexFixed128;
fn fft_inplace(&mut self) {
ComplexFixed128::fft(&mut self.coefficients, &FIXED128_BITREVERSED_POWERS_1024);
}
fn ifft_inplace(&mut self) {
let n = self.coefficients.len();
let psi_inv_rev = FIXED128_BITREVERSED_POWERS_1024
.iter()
.take(n)
.map(|c| Complex::new(c.re, -c.im))
.collect_vec();
let ninv = Complex::new(
FixedPoint128::ONE / FixedPoint128::from(n as i64),
FixedPoint128::ZERO,
);
ComplexFixed128::ifft(&mut self.coefficients, &psi_inv_rev, ninv);
}
fn merge_fft(a: &Self, b: &Self) -> Self {
Self {
coefficients: ComplexFixed128::merge_fft(
&a.coefficients,
&b.coefficients,
&FIXED128_BITREVERSED_POWERS_1024,
),
}
}
fn split_fft(&self) -> (Self, Self) {
let n = self.coefficients.len();
let psi_inv_rev = FIXED128_BITREVERSED_POWERS_1024
.iter()
.take(n)
.map(|c| Complex::new(c.re, -c.im))
.collect_vec();
let (a, b) = ComplexFixed128::split_fft(&self.coefficients, &psi_inv_rev);
(Self { coefficients: a }, Self { coefficients: b })
}
}
const FELT_BITREVERSED_POWERS_1024: [Felt; 1024] = [
Felt::new(1),
Felt::new(1479),
Felt::new(8246),
Felt::new(5146),
Felt::new(4134),
Felt::new(6553),
Felt::new(11567),
Felt::new(1305),
Felt::new(5860),
Felt::new(3195),
Felt::new(1212),
Felt::new(10643),
Felt::new(3621),
Felt::new(9744),
Felt::new(8785),
Felt::new(3542),
Felt::new(7311),
Felt::new(10938),
Felt::new(8961),
Felt::new(5777),
Felt::new(5023),
Felt::new(6461),
Felt::new(5728),
Felt::new(4591),
Felt::new(3006),
Felt::new(9545),
Felt::new(563),
Felt::new(9314),
Felt::new(2625),
Felt::new(11340),
Felt::new(4821),
Felt::new(2639),
Felt::new(12149),
Felt::new(1853),
Felt::new(726),
Felt::new(4611),
Felt::new(11112),
Felt::new(4255),
Felt::new(2768),
Felt::new(1635),
Felt::new(2963),
Felt::new(7393),
Felt::new(2366),
Felt::new(9238),
Felt::new(9198),
Felt::new(12208),
Felt::new(11289),
Felt::new(7969),
Felt::new(8736),
Felt::new(4805),
Felt::new(11227),
Felt::new(2294),
Felt::new(9542),
Felt::new(4846),
Felt::new(9154),
Felt::new(8577),
Felt::new(9275),
Felt::new(3201),
Felt::new(7203),
Felt::new(10963),
Felt::new(1170),
Felt::new(9970),
Felt::new(955),
Felt::new(11499),
Felt::new(8340),
Felt::new(8993),
Felt::new(2396),
Felt::new(4452),
Felt::new(6915),
Felt::new(2837),
Felt::new(130),
Felt::new(7935),
Felt::new(11336),
Felt::new(3748),
Felt::new(6522),
Felt::new(11462),
Felt::new(5067),
Felt::new(10092),
Felt::new(12171),
Felt::new(9813),
Felt::new(8011),
Felt::new(1673),
Felt::new(5331),
Felt::new(7300),
Felt::new(10908),
Felt::new(9764),
Felt::new(4177),
Felt::new(8705),
Felt::new(480),
Felt::new(9447),
Felt::new(1022),
Felt::new(12280),
Felt::new(5791),
Felt::new(11745),
Felt::new(9821),
Felt::new(11950),
Felt::new(12144),
Felt::new(6747),
Felt::new(8652),
Felt::new(3459),
Felt::new(2731),
Felt::new(8357),
Felt::new(6378),
Felt::new(7399),
Felt::new(10530),
Felt::new(3707),
Felt::new(8595),
Felt::new(5179),
Felt::new(3382),
Felt::new(355),
Felt::new(4231),
Felt::new(2548),
Felt::new(9048),
Felt::new(11560),
Felt::new(3289),
Felt::new(10276),
Felt::new(9005),
Felt::new(9408),
Felt::new(5092),
Felt::new(10200),
Felt::new(6534),
Felt::new(4632),
Felt::new(4388),
Felt::new(1260),
Felt::new(334),
Felt::new(2426),
Felt::new(1428),
Felt::new(10593),
Felt::new(3400),
Felt::new(2399),
Felt::new(5191),
Felt::new(9153),
Felt::new(9273),
Felt::new(243),
Felt::new(3000),
Felt::new(671),
Felt::new(3531),
Felt::new(11813),
Felt::new(3985),
Felt::new(7384),
Felt::new(10111),
Felt::new(10745),
Felt::new(6730),
Felt::new(11869),
Felt::new(9042),
Felt::new(2686),
Felt::new(2969),
Felt::new(3978),
Felt::new(8779),
Felt::new(6957),
Felt::new(9424),
Felt::new(2370),
Felt::new(8241),
Felt::new(10040),
Felt::new(9405),
Felt::new(11136),
Felt::new(3186),
Felt::new(5407),
Felt::new(10163),
Felt::new(1630),
Felt::new(3271),
Felt::new(8232),
Felt::new(10600),
Felt::new(8925),
Felt::new(4414),
Felt::new(2847),
Felt::new(10115),
Felt::new(4372),
Felt::new(9509),
Felt::new(5195),
Felt::new(7394),
Felt::new(10805),
Felt::new(9984),
Felt::new(7247),
Felt::new(4053),
Felt::new(9644),
Felt::new(12176),
Felt::new(4919),
Felt::new(2166),
Felt::new(8374),
Felt::new(12129),
Felt::new(9140),
Felt::new(7852),
Felt::new(3),
Felt::new(1426),
Felt::new(7635),
Felt::new(10512),
Felt::new(1663),
Felt::new(8653),
Felt::new(4938),
Felt::new(2704),
Felt::new(5291),
Felt::new(5277),
Felt::new(1168),
Felt::new(11082),
Felt::new(9041),
Felt::new(2143),
Felt::new(11224),
Felt::new(11885),
Felt::new(4645),
Felt::new(4096),
Felt::new(11796),
Felt::new(5444),
Felt::new(2381),
Felt::new(10911),
Felt::new(1912),
Felt::new(4337),
Felt::new(11854),
Felt::new(4976),
Felt::new(10682),
Felt::new(11414),
Felt::new(8509),
Felt::new(11287),
Felt::new(5011),
Felt::new(8005),
Felt::new(5088),
Felt::new(9852),
Felt::new(8643),
Felt::new(9302),
Felt::new(6267),
Felt::new(2422),
Felt::new(6039),
Felt::new(2187),
Felt::new(2566),
Felt::new(10849),
Felt::new(8526),
Felt::new(9223),
Felt::new(27),
Felt::new(7205),
Felt::new(1632),
Felt::new(7404),
Felt::new(1017),
Felt::new(4143),
Felt::new(7575),
Felt::new(12047),
Felt::new(10752),
Felt::new(8585),
Felt::new(2678),
Felt::new(7270),
Felt::new(11744),
Felt::new(3833),
Felt::new(3778),
Felt::new(11899),
Felt::new(773),
Felt::new(5101),
Felt::new(11222),
Felt::new(9888),
Felt::new(442),
Felt::new(9377),
Felt::new(6591),
Felt::new(354),
Felt::new(7428),
Felt::new(5012),
Felt::new(2481),
Felt::new(1045),
Felt::new(9430),
Felt::new(10302),
Felt::new(10587),
Felt::new(8724),
Felt::new(11635),
Felt::new(7083),
Felt::new(5529),
Felt::new(9090),
Felt::new(12233),
Felt::new(6152),
Felt::new(4948),
Felt::new(400),
Felt::new(1728),
Felt::new(6427),
Felt::new(6136),
Felt::new(6874),
Felt::new(3643),
Felt::new(10930),
Felt::new(5435),
Felt::new(1254),
Felt::new(11316),
Felt::new(10256),
Felt::new(3998),
Felt::new(10367),
Felt::new(8410),
Felt::new(11821),
Felt::new(8301),
Felt::new(11907),
Felt::new(316),
Felt::new(6950),
Felt::new(5446),
Felt::new(6093),
Felt::new(3710),
Felt::new(7822),
Felt::new(4789),
Felt::new(7540),
Felt::new(5537),
Felt::new(3789),
Felt::new(147),
Felt::new(5456),
Felt::new(7840),
Felt::new(11239),
Felt::new(7753),
Felt::new(5445),
Felt::new(3860),
Felt::new(9606),
Felt::new(1190),
Felt::new(8471),
Felt::new(6118),
Felt::new(5925),
Felt::new(1018),
Felt::new(8775),
Felt::new(1041),
Felt::new(1973),
Felt::new(5574),
Felt::new(11011),
Felt::new(2344),
Felt::new(4075),
Felt::new(5315),
Felt::new(4324),
Felt::new(4916),
Felt::new(10120),
Felt::new(11767),
Felt::new(7210),
Felt::new(9027),
Felt::new(6281),
Felt::new(11404),
Felt::new(7280),
Felt::new(1956),
Felt::new(11286),
Felt::new(3532),
Felt::new(12048),
Felt::new(12231),
Felt::new(1105),
Felt::new(12147),
Felt::new(5681),
Felt::new(8812),
Felt::new(8851),
Felt::new(2844),
Felt::new(975),
Felt::new(4212),
Felt::new(8687),
Felt::new(6068),
Felt::new(421),
Felt::new(8209),
Felt::new(3600),
Felt::new(3263),
Felt::new(7665),
Felt::new(6077),
Felt::new(4782),
Felt::new(6403),
Felt::new(9260),
Felt::new(5594),
Felt::new(8076),
Felt::new(11785),
Felt::new(605),
Felt::new(9987),
Felt::new(5468),
Felt::new(1010),
Felt::new(787),
Felt::new(8807),
Felt::new(5241),
Felt::new(9369),
Felt::new(9162),
Felt::new(8120),
Felt::new(5057),
Felt::new(7591),
Felt::new(3445),
Felt::new(7509),
Felt::new(2049),
Felt::new(7377),
Felt::new(10968),
Felt::new(192),
Felt::new(431),
Felt::new(10710),
Felt::new(2505),
Felt::new(5906),
Felt::new(12138),
Felt::new(10162),
Felt::new(8332),
Felt::new(9450),
Felt::new(6415),
Felt::new(677),
Felt::new(6234),
Felt::new(3336),
Felt::new(12237),
Felt::new(9115),
Felt::new(1323),
Felt::new(2766),
Felt::new(3150),
Felt::new(1319),
Felt::new(8243),
Felt::new(709),
Felt::new(8049),
Felt::new(8719),
Felt::new(11454),
Felt::new(6224),
Felt::new(922),
Felt::new(11848),
Felt::new(8210),
Felt::new(1058),
Felt::new(1958),
Felt::new(7967),
Felt::new(10211),
Felt::new(11177),
Felt::new(64),
Felt::new(8633),
Felt::new(11606),
Felt::new(9830),
Felt::new(6507),
Felt::new(1566),
Felt::new(2948),
Felt::new(9786),
Felt::new(6370),
Felt::new(7856),
Felt::new(3834),
Felt::new(5257),
Felt::new(10542),
Felt::new(9166),
Felt::new(9235),
Felt::new(5486),
Felt::new(1404),
Felt::new(11964),
Felt::new(1146),
Felt::new(11341),
Felt::new(3728),
Felt::new(8240),
Felt::new(6299),
Felt::new(1159),
Felt::new(6099),
Felt::new(295),
Felt::new(5766),
Felt::new(11637),
Felt::new(8527),
Felt::new(2919),
Felt::new(8273),
Felt::new(8212),
Felt::new(3329),
Felt::new(7991),
Felt::new(9597),
Felt::new(168),
Felt::new(10695),
Felt::new(1962),
Felt::new(5106),
Felt::new(6328),
Felt::new(5297),
Felt::new(6170),
Felt::new(3956),
Felt::new(1360),
Felt::new(11089),
Felt::new(7105),
Felt::new(9734),
Felt::new(6167),
Felt::new(9407),
Felt::new(1805),
Felt::new(1954),
Felt::new(2051),
Felt::new(6142),
Felt::new(2447),
Felt::new(3963),
Felt::new(11713),
Felt::new(8855),
Felt::new(8760),
Felt::new(9381),
Felt::new(218),
Felt::new(9928),
Felt::new(10446),
Felt::new(9259),
Felt::new(4115),
Felt::new(5333),
Felt::new(10258),
Felt::new(5876),
Felt::new(2281),
Felt::new(156),
Felt::new(9522),
Felt::new(8320),
Felt::new(3991),
Felt::new(453),
Felt::new(6381),
Felt::new(11871),
Felt::new(8517),
Felt::new(4774),
Felt::new(6860),
Felt::new(4737),
Felt::new(1293),
Felt::new(10232),
Felt::new(5369),
Felt::new(9087),
Felt::new(7796),
Felt::new(350),
Felt::new(1512),
Felt::new(10474),
Felt::new(6906),
Felt::new(1489),
Felt::new(2500),
Felt::new(1583),
Felt::new(6347),
Felt::new(11026),
Felt::new(12240),
Felt::new(6374),
Felt::new(1483),
Felt::new(3009),
Felt::new(1693),
Felt::new(723),
Felt::new(174),
Felt::new(2738),
Felt::new(6421),
Felt::new(2655),
Felt::new(6554),
Felt::new(10314),
Felt::new(3757),
Felt::new(9364),
Felt::new(11942),
Felt::new(7535),
Felt::new(10431),
Felt::new(426),
Felt::new(3315),
Felt::new(1945),
Felt::new(1029),
Felt::new(1325),
Felt::new(5724),
Felt::new(3624),
Felt::new(1892),
Felt::new(8945),
Felt::new(6691),
Felt::new(5797),
Felt::new(8330),
Felt::new(10141),
Felt::new(5959),
Felt::new(1248),
Felt::new(2442),
Felt::new(5115),
Felt::new(7350),
Felt::new(1522),
Felt::new(2151),
Felt::new(3343),
Felt::new(4119),
Felt::new(12269),
Felt::new(7287),
Felt::new(7126),
Felt::new(7681),
Felt::new(9395),
Felt::new(8635),
Felt::new(1314),
Felt::new(1744),
Felt::new(5690),
Felt::new(9834),
Felt::new(338),
Felt::new(8342),
Felt::new(10347),
Felt::new(3408),
Felt::new(11124),
Felt::new(9714),
Felt::new(8778),
Felt::new(5478),
Felt::new(1178),
Felt::new(9513),
Felt::new(11783),
Felt::new(1255),
Felt::new(5784),
Felt::new(1392),
Felt::new(9615),
Felt::new(2212),
Felt::new(8951),
Felt::new(3276),
Felt::new(8122),
Felt::new(6085),
Felt::new(11251),
Felt::new(923),
Felt::new(2800),
Felt::new(12096),
Felt::new(10058),
Felt::new(6092),
Felt::new(11912),
Felt::new(7711),
Felt::new(375),
Felt::new(1620),
Felt::new(2185),
Felt::new(11897),
Felt::new(1836),
Felt::new(11864),
Felt::new(12109),
Felt::new(4138),
Felt::new(2689),
Felt::new(7684),
Felt::new(5509),
Felt::new(204),
Felt::new(7070),
Felt::new(10880),
Felt::new(2054),
Felt::new(2483),
Felt::new(3042),
Felt::new(1344),
Felt::new(11826),
Felt::new(3407),
Felt::new(3981),
Felt::new(1468),
Felt::new(11232),
Felt::new(9689),
Felt::new(9168),
Felt::new(4705),
Felt::new(5246),
Felt::new(4475),
Felt::new(1236),
Felt::new(9272),
Felt::new(11925),
Felt::new(2360),
Felt::new(9261),
Felt::new(7073),
Felt::new(6771),
Felt::new(11063),
Felt::new(4739),
Felt::new(4251),
Felt::new(622),
Felt::new(10552),
Felt::new(4499),
Felt::new(5672),
Felt::new(2947),
Felt::new(8307),
Felt::new(5609),
Felt::new(636),
Felt::new(7376),
Felt::new(8761),
Felt::new(4235),
Felt::new(8464),
Felt::new(3375),
Felt::new(2291),
Felt::new(7954),
Felt::new(3393),
Felt::new(512),
Felt::new(7619),
Felt::new(6825),
Felt::new(4906),
Felt::new(2900),
Felt::new(239),
Felt::new(11295),
Felt::new(4554),
Felt::new(1804),
Felt::new(1403),
Felt::new(6094),
Felt::new(5189),
Felt::new(10602),
Felt::new(11883),
Felt::new(146),
Felt::new(7021),
Felt::new(1518),
Felt::new(8524),
Felt::new(7226),
Felt::new(8113),
Felt::new(8022),
Felt::new(5653),
Felt::new(10014),
Felt::new(2461),
Felt::new(10533),
Felt::new(8144),
Felt::new(8755),
Felt::new(8328),
Felt::new(3495),
Felt::new(7725),
Felt::new(2065),
Felt::new(6463),
Felt::new(1131),
Felt::new(1445),
Felt::new(11164),
Felt::new(7429),
Felt::new(5734),
Felt::new(1176),
Felt::new(6781),
Felt::new(1275),
Felt::new(3889),
Felt::new(579),
Felt::new(6693),
Felt::new(6302),
Felt::new(3114),
Felt::new(9520),
Felt::new(6323),
Felt::new(12077),
Felt::new(8682),
Felt::new(10962),
Felt::new(8347),
Felt::new(7057),
Felt::new(7508),
Felt::new(7365),
Felt::new(11275),
Felt::new(11841),
Felt::new(60),
Felt::new(2717),
Felt::new(3200),
Felt::new(1535),
Felt::new(2260),
Felt::new(12221),
Felt::new(5836),
Felt::new(4566),
Felt::new(1417),
Felt::new(6613),
Felt::new(10032),
Felt::new(4505),
Felt::new(8314),
Felt::new(7406),
Felt::new(9202),
Felt::new(5835),
Felt::new(8545),
Felt::new(4963),
Felt::new(9233),
Felt::new(2528),
Felt::new(6444),
Felt::new(6701),
Felt::new(11877),
Felt::new(5102),
Felt::new(2450),
Felt::new(10584),
Felt::new(11873),
Felt::new(11475),
Felt::new(2164),
Felt::new(5416),
Felt::new(716),
Felt::new(2110),
Felt::new(3448),
Felt::new(11946),
Felt::new(7751),
Felt::new(10381),
Felt::new(11081),
Felt::new(7562),
Felt::new(5211),
Felt::new(1866),
Felt::new(6877),
Felt::new(8080),
Felt::new(6296),
Felt::new(9011),
Felt::new(5061),
Felt::new(1218),
Felt::new(11851),
Felt::new(3515),
Felt::new(3589),
Felt::new(11572),
Felt::new(2982),
Felt::new(10916),
Felt::new(4103),
Felt::new(9860),
Felt::new(1721),
Felt::new(1536),
Felt::new(1092),
Felt::new(5209),
Felt::new(9084),
Felt::new(3359),
Felt::new(4265),
Felt::new(3678),
Felt::new(10361),
Felt::new(11825),
Felt::new(8840),
Felt::new(11153),
Felt::new(8581),
Felt::new(9051),
Felt::new(9363),
Felt::new(10463),
Felt::new(7800),
Felt::new(9118),
Felt::new(8051),
Felt::new(11677),
Felt::new(3368),
Felt::new(4227),
Felt::new(4222),
Felt::new(1526),
Felt::new(12164),
Felt::new(11749),
Felt::new(1389),
Felt::new(2068),
Felt::new(346),
Felt::new(7885),
Felt::new(3163),
Felt::new(8257),
Felt::new(4840),
Felt::new(6162),
Felt::new(6320),
Felt::new(7640),
Felt::new(9360),
Felt::new(6026),
Felt::new(466),
Felt::new(1030),
Felt::new(8468),
Felt::new(1681),
Felt::new(8443),
Felt::new(1573),
Felt::new(3793),
Felt::new(6063),
Felt::new(2602),
Felt::new(1901),
Felt::new(11787),
Felt::new(7171),
Felt::new(11169),
Felt::new(2535),
Felt::new(5808),
Felt::new(21),
Felt::new(2873),
Felt::new(9462),
Felt::new(9855),
Felt::new(791),
Felt::new(11415),
Felt::new(9988),
Felt::new(6639),
Felt::new(170),
Felt::new(12139),
Felt::new(11641),
Felt::new(4289),
Felt::new(2307),
Felt::new(8),
Felt::new(11832),
Felt::new(4523),
Felt::new(4301),
Felt::new(8494),
Felt::new(3268),
Felt::new(6513),
Felt::new(10440),
Felt::new(10013),
Felt::new(982),
Felt::new(9696),
Felt::new(11410),
Felt::new(4390),
Felt::new(4218),
Felt::new(8835),
Felt::new(3758),
Felt::new(9332),
Felt::new(1481),
Felt::new(10243),
Felt::new(9349),
Felt::new(3317),
Felt::new(2532),
Felt::new(8957),
Felt::new(12150),
Felt::new(11759),
Felt::new(2626),
Felt::new(4504),
Felt::new(778),
Felt::new(8711),
Felt::new(4697),
Felt::new(1701),
Felt::new(8823),
Felt::new(1279),
Felt::new(11424),
Felt::new(2672),
Felt::new(7119),
Felt::new(3116),
Felt::new(189),
Felt::new(10526),
Felt::new(10080),
Felt::new(10939),
Felt::new(6457),
Felt::new(1734),
Felt::new(8474),
Felt::new(10595),
Felt::new(1530),
Felt::new(3869),
Felt::new(7866),
Felt::new(11129),
Felt::new(4820),
Felt::new(7771),
Felt::new(3094),
Felt::new(9559),
Felt::new(5411),
Felt::new(1868),
Felt::new(10036),
Felt::new(10506),
Felt::new(5078),
Felt::new(7315),
Felt::new(4565),
Felt::new(2478),
Felt::new(2840),
Felt::new(9270),
Felt::new(8095),
Felt::new(5275),
Felt::new(10499),
Felt::new(6879),
Felt::new(11038),
Felt::new(6164),
Felt::new(10407),
Felt::new(1040),
Felt::new(2035),
Felt::new(4665),
Felt::new(5406),
Felt::new(3020),
Felt::new(5673),
Felt::new(3669),
Felt::new(7002),
Felt::new(11345),
Felt::new(4770),
Felt::new(2643),
Felt::new(1095),
Felt::new(5781),
Felt::new(9244),
Felt::new(1241),
Felt::new(4378),
Felt::new(8838),
Felt::new(8195),
Felt::new(3840),
Felt::new(1842),
Felt::new(8176),
Felt::new(12217),
Felt::new(9461),
Felt::new(7937),
Felt::new(4834),
Felt::new(9577),
Felt::new(6828),
Felt::new(9343),
Felt::new(7779),
Felt::new(2637),
Felt::new(11408),
Felt::new(11924),
Felt::new(10362),
Felt::new(1015),
Felt::new(11385),
Felt::new(2485),
Felt::new(5039),
Felt::new(5547),
Felt::new(11009),
Felt::new(11675),
Felt::new(1371),
Felt::new(24),
Felt::new(1590),
Felt::new(4411),
Felt::new(11066),
Felt::new(9955),
Felt::new(10734),
Felt::new(10487),
Felt::new(7186),
Felt::new(10398),
Felt::new(2338),
Felt::new(4693),
Felt::new(9996),
Felt::new(417),
Felt::new(6138),
Felt::new(8820),
Felt::new(7846),
Felt::new(3418),
Felt::new(2622),
Felt::new(6903),
Felt::new(4661),
Felt::new(11779),
Felt::new(450),
Felt::new(1944),
Felt::new(11711),
Felt::new(5368),
Felt::new(3670),
Felt::new(8481),
Felt::new(7302),
Felt::new(9916),
Felt::new(7154),
Felt::new(12226),
Felt::new(4684),
Felt::new(8929),
Felt::new(10891),
Felt::new(9199),
Felt::new(11463),
Felt::new(7246),
Felt::new(8787),
Felt::new(6500),
Felt::new(1658),
Felt::new(6671),
Felt::new(4483),
Felt::new(6586),
Felt::new(1506),
Felt::new(3065),
Felt::new(910),
Felt::new(6389),
Felt::new(7570),
Felt::new(751),
Felt::new(10583),
Felt::new(8360),
Felt::new(3229),
Felt::new(7559),
Felt::new(1282),
Felt::new(3572),
Felt::new(2832),
Felt::new(10268),
Felt::new(6086),
Felt::new(5646),
Felt::new(9169),
Felt::new(6184),
Felt::new(3941),
Felt::new(3753),
Felt::new(5370),
Felt::new(3536),
Felt::new(769),
Felt::new(6763),
Felt::new(50),
Felt::new(216),
Felt::new(8484),
Felt::new(767),
Felt::new(10076),
Felt::new(8136),
Felt::new(8566),
Felt::new(11444),
Felt::new(10353),
Felt::new(12282),
Felt::new(7235),
Felt::new(9135),
Felt::new(9004),
Felt::new(7929),
Felt::new(5349),
Felt::new(9344),
Felt::new(2633),
Felt::new(10883),
Felt::new(4855),
Felt::new(3769),
Felt::new(9057),
Felt::new(293),
Felt::new(8190),
Felt::new(8345),
Felt::new(6685),
Felt::new(6759),
Felt::new(1265),
Felt::new(3007),
Felt::new(10118),
Felt::new(8809),
Felt::new(2941),
Felt::new(11722),
Felt::new(5289),
Felt::new(6627),
Felt::new(4273),
Felt::new(3221),
Felt::new(2595),
Felt::new(3837),
Felt::new(5082),
Felt::new(7699),
Felt::new(682),
Felt::new(980),
Felt::new(7087),
Felt::new(11445),
Felt::new(5207),
Felt::new(8239),
];
const FELT_BITREVERSED_POWERS_INVERSE_1024: [Felt; 1024] = [
Felt::new(1),
Felt::new(10810),
Felt::new(7143),
Felt::new(4043),
Felt::new(10984),
Felt::new(722),
Felt::new(5736),
Felt::new(8155),
Felt::new(8747),
Felt::new(3504),
Felt::new(2545),
Felt::new(8668),
Felt::new(1646),
Felt::new(11077),
Felt::new(9094),
Felt::new(6429),
Felt::new(9650),
Felt::new(7468),
Felt::new(949),
Felt::new(9664),
Felt::new(2975),
Felt::new(11726),
Felt::new(2744),
Felt::new(9283),
Felt::new(7698),
Felt::new(6561),
Felt::new(5828),
Felt::new(7266),
Felt::new(6512),
Felt::new(3328),
Felt::new(1351),
Felt::new(4978),
Felt::new(790),
Felt::new(11334),
Felt::new(2319),
Felt::new(11119),
Felt::new(1326),
Felt::new(5086),
Felt::new(9088),
Felt::new(3014),
Felt::new(3712),
Felt::new(3135),
Felt::new(7443),
Felt::new(2747),
Felt::new(9995),
Felt::new(1062),
Felt::new(7484),
Felt::new(3553),
Felt::new(4320),
Felt::new(1000),
Felt::new(81),
Felt::new(3091),
Felt::new(3051),
Felt::new(9923),
Felt::new(4896),
Felt::new(9326),
Felt::new(10654),
Felt::new(9521),
Felt::new(8034),
Felt::new(1177),
Felt::new(7678),
Felt::new(11563),
Felt::new(10436),
Felt::new(140),
Felt::new(1696),
Felt::new(10861),
Felt::new(9863),
Felt::new(11955),
Felt::new(11029),
Felt::new(7901),
Felt::new(7657),
Felt::new(5755),
Felt::new(2089),
Felt::new(7197),
Felt::new(2881),
Felt::new(3284),
Felt::new(2013),
Felt::new(9000),
Felt::new(729),
Felt::new(3241),
Felt::new(9741),
Felt::new(8058),
Felt::new(11934),
Felt::new(8907),
Felt::new(7110),
Felt::new(3694),
Felt::new(8582),
Felt::new(1759),
Felt::new(4890),
Felt::new(5911),
Felt::new(3932),
Felt::new(9558),
Felt::new(8830),
Felt::new(3637),
Felt::new(5542),
Felt::new(145),
Felt::new(339),
Felt::new(2468),
Felt::new(544),
Felt::new(6498),
Felt::new(9),
Felt::new(11267),
Felt::new(2842),
Felt::new(11809),
Felt::new(3584),
Felt::new(8112),
Felt::new(2525),
Felt::new(1381),
Felt::new(4989),
Felt::new(6958),
Felt::new(10616),
Felt::new(4278),
Felt::new(2476),
Felt::new(118),
Felt::new(2197),
Felt::new(7222),
Felt::new(827),
Felt::new(5767),
Felt::new(8541),
Felt::new(953),
Felt::new(4354),
Felt::new(12159),
Felt::new(9452),
Felt::new(5374),
Felt::new(7837),
Felt::new(9893),
Felt::new(3296),
Felt::new(3949),
Felt::new(2859),
Felt::new(11244),
Felt::new(9808),
Felt::new(7277),
Felt::new(4861),
Felt::new(11935),
Felt::new(5698),
Felt::new(2912),
Felt::new(11847),
Felt::new(2401),
Felt::new(1067),
Felt::new(7188),
Felt::new(11516),
Felt::new(390),
Felt::new(8511),
Felt::new(8456),
Felt::new(545),
Felt::new(5019),
Felt::new(9611),
Felt::new(3704),
Felt::new(1537),
Felt::new(242),
Felt::new(4714),
Felt::new(8146),
Felt::new(11272),
Felt::new(4885),
Felt::new(10657),
Felt::new(5084),
Felt::new(12262),
Felt::new(3066),
Felt::new(3763),
Felt::new(1440),
Felt::new(9723),
Felt::new(10102),
Felt::new(6250),
Felt::new(9867),
Felt::new(6022),
Felt::new(2987),
Felt::new(3646),
Felt::new(2437),
Felt::new(7201),
Felt::new(4284),
Felt::new(7278),
Felt::new(1002),
Felt::new(3780),
Felt::new(875),
Felt::new(1607),
Felt::new(7313),
Felt::new(435),
Felt::new(7952),
Felt::new(10377),
Felt::new(1378),
Felt::new(9908),
Felt::new(6845),
Felt::new(493),
Felt::new(8193),
Felt::new(7644),
Felt::new(404),
Felt::new(1065),
Felt::new(10146),
Felt::new(3248),
Felt::new(1207),
Felt::new(11121),
Felt::new(7012),
Felt::new(6998),
Felt::new(9585),
Felt::new(7351),
Felt::new(3636),
Felt::new(10626),
Felt::new(1777),
Felt::new(4654),
Felt::new(10863),
Felt::new(12286),
Felt::new(4437),
Felt::new(3149),
Felt::new(160),
Felt::new(3915),
Felt::new(10123),
Felt::new(7370),
Felt::new(113),
Felt::new(2645),
Felt::new(8236),
Felt::new(5042),
Felt::new(2305),
Felt::new(1484),
Felt::new(4895),
Felt::new(7094),
Felt::new(2780),
Felt::new(7917),
Felt::new(2174),
Felt::new(9442),
Felt::new(7875),
Felt::new(3364),
Felt::new(1689),
Felt::new(4057),
Felt::new(9018),
Felt::new(10659),
Felt::new(2126),
Felt::new(6882),
Felt::new(9103),
Felt::new(1153),
Felt::new(2884),
Felt::new(2249),
Felt::new(4048),
Felt::new(9919),
Felt::new(2865),
Felt::new(5332),
Felt::new(3510),
Felt::new(8311),
Felt::new(9320),
Felt::new(9603),
Felt::new(3247),
Felt::new(420),
Felt::new(5559),
Felt::new(1544),
Felt::new(2178),
Felt::new(4905),
Felt::new(8304),
Felt::new(476),
Felt::new(8758),
Felt::new(11618),
Felt::new(9289),
Felt::new(12046),
Felt::new(3016),
Felt::new(3136),
Felt::new(7098),
Felt::new(9890),
Felt::new(8889),
Felt::new(8974),
Felt::new(11863),
Felt::new(1858),
Felt::new(4754),
Felt::new(347),
Felt::new(2925),
Felt::new(8532),
Felt::new(1975),
Felt::new(5735),
Felt::new(9634),
Felt::new(5868),
Felt::new(9551),
Felt::new(12115),
Felt::new(11566),
Felt::new(10596),
Felt::new(9280),
Felt::new(10806),
Felt::new(5915),
Felt::new(49),
Felt::new(1263),
Felt::new(5942),
Felt::new(10706),
Felt::new(9789),
Felt::new(10800),
Felt::new(5383),
Felt::new(1815),
Felt::new(10777),
Felt::new(11939),
Felt::new(4493),
Felt::new(3202),
Felt::new(6920),
Felt::new(2057),
Felt::new(10996),
Felt::new(7552),
Felt::new(5429),
Felt::new(7515),
Felt::new(3772),
Felt::new(418),
Felt::new(5908),
Felt::new(11836),
Felt::new(8298),
Felt::new(3969),
Felt::new(2767),
Felt::new(12133),
Felt::new(10008),
Felt::new(6413),
Felt::new(2031),
Felt::new(6956),
Felt::new(8174),
Felt::new(3030),
Felt::new(1843),
Felt::new(2361),
Felt::new(12071),
Felt::new(2908),
Felt::new(3529),
Felt::new(3434),
Felt::new(576),
Felt::new(8326),
Felt::new(9842),
Felt::new(6147),
Felt::new(10238),
Felt::new(10335),
Felt::new(10484),
Felt::new(2882),
Felt::new(6122),
Felt::new(2555),
Felt::new(5184),
Felt::new(1200),
Felt::new(10929),
Felt::new(8333),
Felt::new(6119),
Felt::new(6992),
Felt::new(5961),
Felt::new(7183),
Felt::new(10327),
Felt::new(1594),
Felt::new(12121),
Felt::new(2692),
Felt::new(4298),
Felt::new(8960),
Felt::new(4077),
Felt::new(4016),
Felt::new(9370),
Felt::new(3762),
Felt::new(652),
Felt::new(6523),
Felt::new(11994),
Felt::new(6190),
Felt::new(11130),
Felt::new(5990),
Felt::new(4049),
Felt::new(8561),
Felt::new(948),
Felt::new(11143),
Felt::new(325),
Felt::new(10885),
Felt::new(6803),
Felt::new(3054),
Felt::new(3123),
Felt::new(1747),
Felt::new(7032),
Felt::new(8455),
Felt::new(4433),
Felt::new(5919),
Felt::new(2503),
Felt::new(9341),
Felt::new(10723),
Felt::new(5782),
Felt::new(2459),
Felt::new(683),
Felt::new(3656),
Felt::new(12225),
Felt::new(1112),
Felt::new(2078),
Felt::new(4322),
Felt::new(10331),
Felt::new(11231),
Felt::new(4079),
Felt::new(441),
Felt::new(11367),
Felt::new(6065),
Felt::new(835),
Felt::new(3570),
Felt::new(4240),
Felt::new(11580),
Felt::new(4046),
Felt::new(10970),
Felt::new(9139),
Felt::new(9523),
Felt::new(10966),
Felt::new(3174),
Felt::new(52),
Felt::new(8953),
Felt::new(6055),
Felt::new(11612),
Felt::new(5874),
Felt::new(2839),
Felt::new(3957),
Felt::new(2127),
Felt::new(151),
Felt::new(6383),
Felt::new(9784),
Felt::new(1579),
Felt::new(11858),
Felt::new(12097),
Felt::new(1321),
Felt::new(4912),
Felt::new(10240),
Felt::new(4780),
Felt::new(8844),
Felt::new(4698),
Felt::new(7232),
Felt::new(4169),
Felt::new(3127),
Felt::new(2920),
Felt::new(7048),
Felt::new(3482),
Felt::new(11502),
Felt::new(11279),
Felt::new(6821),
Felt::new(2302),
Felt::new(11684),
Felt::new(504),
Felt::new(4213),
Felt::new(6695),
Felt::new(3029),
Felt::new(5886),
Felt::new(7507),
Felt::new(6212),
Felt::new(4624),
Felt::new(9026),
Felt::new(8689),
Felt::new(4080),
Felt::new(11868),
Felt::new(6221),
Felt::new(3602),
Felt::new(8077),
Felt::new(11314),
Felt::new(9445),
Felt::new(3438),
Felt::new(3477),
Felt::new(6608),
Felt::new(142),
Felt::new(11184),
Felt::new(58),
Felt::new(241),
Felt::new(8757),
Felt::new(1003),
Felt::new(10333),
Felt::new(5009),
Felt::new(885),
Felt::new(6008),
Felt::new(3262),
Felt::new(5079),
Felt::new(522),
Felt::new(2169),
Felt::new(7373),
Felt::new(7965),
Felt::new(6974),
Felt::new(8214),
Felt::new(9945),
Felt::new(1278),
Felt::new(6715),
Felt::new(10316),
Felt::new(11248),
Felt::new(3514),
Felt::new(11271),
Felt::new(6364),
Felt::new(6171),
Felt::new(3818),
Felt::new(11099),
Felt::new(2683),
Felt::new(8429),
Felt::new(6844),
Felt::new(4536),
Felt::new(1050),
Felt::new(4449),
Felt::new(6833),
Felt::new(12142),
Felt::new(8500),
Felt::new(6752),
Felt::new(4749),
Felt::new(7500),
Felt::new(4467),
Felt::new(8579),
Felt::new(6196),
Felt::new(6843),
Felt::new(5339),
Felt::new(11973),
Felt::new(382),
Felt::new(3988),
Felt::new(468),
Felt::new(3879),
Felt::new(1922),
Felt::new(8291),
Felt::new(2033),
Felt::new(973),
Felt::new(11035),
Felt::new(6854),
Felt::new(1359),
Felt::new(8646),
Felt::new(5415),
Felt::new(6153),
Felt::new(5862),
Felt::new(10561),
Felt::new(11889),
Felt::new(7341),
Felt::new(6137),
Felt::new(56),
Felt::new(3199),
Felt::new(6760),
Felt::new(5206),
Felt::new(654),
Felt::new(3565),
Felt::new(1702),
Felt::new(1987),
Felt::new(4050),
Felt::new(7082),
Felt::new(844),
Felt::new(5202),
Felt::new(11309),
Felt::new(11607),
Felt::new(4590),
Felt::new(7207),
Felt::new(8452),
Felt::new(9694),
Felt::new(9068),
Felt::new(8016),
Felt::new(5662),
Felt::new(7000),
Felt::new(567),
Felt::new(9348),
Felt::new(3480),
Felt::new(2171),
Felt::new(9282),
Felt::new(11024),
Felt::new(5530),
Felt::new(5604),
Felt::new(3944),
Felt::new(4099),
Felt::new(11996),
Felt::new(3232),
Felt::new(8520),
Felt::new(7434),
Felt::new(1406),
Felt::new(9656),
Felt::new(2945),
Felt::new(6940),
Felt::new(4360),
Felt::new(3285),
Felt::new(3154),
Felt::new(5054),
Felt::new(7),
Felt::new(1936),
Felt::new(845),
Felt::new(3723),
Felt::new(4153),
Felt::new(2213),
Felt::new(11522),
Felt::new(3805),
Felt::new(12073),
Felt::new(12239),
Felt::new(5526),
Felt::new(11520),
Felt::new(8753),
Felt::new(6919),
Felt::new(8536),
Felt::new(8348),
Felt::new(6105),
Felt::new(3120),
Felt::new(6643),
Felt::new(6203),
Felt::new(2021),
Felt::new(9457),
Felt::new(8717),
Felt::new(11007),
Felt::new(4730),
Felt::new(9060),
Felt::new(3929),
Felt::new(1706),
Felt::new(11538),
Felt::new(4719),
Felt::new(5900),
Felt::new(11379),
Felt::new(9224),
Felt::new(10783),
Felt::new(5703),
Felt::new(7806),
Felt::new(5618),
Felt::new(10631),
Felt::new(5789),
Felt::new(3502),
Felt::new(5043),
Felt::new(826),
Felt::new(3090),
Felt::new(1398),
Felt::new(3360),
Felt::new(7605),
Felt::new(63),
Felt::new(5135),
Felt::new(2373),
Felt::new(4987),
Felt::new(3808),
Felt::new(8619),
Felt::new(6921),
Felt::new(578),
Felt::new(10345),
Felt::new(11839),
Felt::new(510),
Felt::new(7628),
Felt::new(5386),
Felt::new(9667),
Felt::new(8871),
Felt::new(4443),
Felt::new(3469),
Felt::new(6151),
Felt::new(11872),
Felt::new(2293),
Felt::new(7596),
Felt::new(9951),
Felt::new(1891),
Felt::new(5103),
Felt::new(1802),
Felt::new(1555),
Felt::new(2334),
Felt::new(1223),
Felt::new(7878),
Felt::new(10699),
Felt::new(12265),
Felt::new(10918),
Felt::new(614),
Felt::new(1280),
Felt::new(6742),
Felt::new(7250),
Felt::new(9804),
Felt::new(904),
Felt::new(11274),
Felt::new(1927),
Felt::new(365),
Felt::new(881),
Felt::new(9652),
Felt::new(4510),
Felt::new(2946),
Felt::new(5461),
Felt::new(2712),
Felt::new(7455),
Felt::new(4352),
Felt::new(2828),
Felt::new(72),
Felt::new(4113),
Felt::new(10447),
Felt::new(8449),
Felt::new(4094),
Felt::new(3451),
Felt::new(7911),
Felt::new(11048),
Felt::new(3045),
Felt::new(6508),
Felt::new(11194),
Felt::new(9646),
Felt::new(7519),
Felt::new(944),
Felt::new(5287),
Felt::new(8620),
Felt::new(6616),
Felt::new(9269),
Felt::new(6883),
Felt::new(7624),
Felt::new(10254),
Felt::new(11249),
Felt::new(1882),
Felt::new(6125),
Felt::new(1251),
Felt::new(5410),
Felt::new(1790),
Felt::new(7014),
Felt::new(4194),
Felt::new(3019),
Felt::new(9449),
Felt::new(9811),
Felt::new(7724),
Felt::new(4974),
Felt::new(7211),
Felt::new(1783),
Felt::new(2253),
Felt::new(10421),
Felt::new(6878),
Felt::new(2730),
Felt::new(9195),
Felt::new(4518),
Felt::new(7469),
Felt::new(1160),
Felt::new(4423),
Felt::new(8420),
Felt::new(10759),
Felt::new(1694),
Felt::new(3815),
Felt::new(10555),
Felt::new(5832),
Felt::new(1350),
Felt::new(2209),
Felt::new(1763),
Felt::new(12100),
Felt::new(9173),
Felt::new(5170),
Felt::new(9617),
Felt::new(865),
Felt::new(11010),
Felt::new(3466),
Felt::new(10588),
Felt::new(7592),
Felt::new(3578),
Felt::new(11511),
Felt::new(7785),
Felt::new(9663),
Felt::new(530),
Felt::new(139),
Felt::new(3332),
Felt::new(9757),
Felt::new(8972),
Felt::new(2940),
Felt::new(2046),
Felt::new(10808),
Felt::new(2957),
Felt::new(8531),
Felt::new(3454),
Felt::new(8071),
Felt::new(7899),
Felt::new(879),
Felt::new(2593),
Felt::new(11307),
Felt::new(2276),
Felt::new(1849),
Felt::new(5776),
Felt::new(9021),
Felt::new(3795),
Felt::new(7988),
Felt::new(7766),
Felt::new(457),
Felt::new(12281),
Felt::new(9982),
Felt::new(8000),
Felt::new(648),
Felt::new(150),
Felt::new(12119),
Felt::new(5650),
Felt::new(2301),
Felt::new(874),
Felt::new(11498),
Felt::new(2434),
Felt::new(2827),
Felt::new(9416),
Felt::new(12268),
Felt::new(6481),
Felt::new(9754),
Felt::new(1120),
Felt::new(5118),
Felt::new(502),
Felt::new(10388),
Felt::new(9687),
Felt::new(6226),
Felt::new(8496),
Felt::new(10716),
Felt::new(3846),
Felt::new(10608),
Felt::new(3821),
Felt::new(11259),
Felt::new(11823),
Felt::new(6263),
Felt::new(2929),
Felt::new(4649),
Felt::new(5969),
Felt::new(6127),
Felt::new(7449),
Felt::new(4032),
Felt::new(9126),
Felt::new(4404),
Felt::new(11943),
Felt::new(10221),
Felt::new(10900),
Felt::new(540),
Felt::new(125),
Felt::new(10763),
Felt::new(8067),
Felt::new(8062),
Felt::new(8921),
Felt::new(612),
Felt::new(4238),
Felt::new(3171),
Felt::new(4489),
Felt::new(1826),
Felt::new(2926),
Felt::new(3238),
Felt::new(3708),
Felt::new(1136),
Felt::new(3449),
Felt::new(464),
Felt::new(1928),
Felt::new(8611),
Felt::new(8024),
Felt::new(8930),
Felt::new(3205),
Felt::new(7080),
Felt::new(11197),
Felt::new(10753),
Felt::new(10568),
Felt::new(2429),
Felt::new(8186),
Felt::new(1373),
Felt::new(9307),
Felt::new(717),
Felt::new(8700),
Felt::new(8774),
Felt::new(438),
Felt::new(11071),
Felt::new(7228),
Felt::new(3278),
Felt::new(5993),
Felt::new(4209),
Felt::new(5412),
Felt::new(10423),
Felt::new(7078),
Felt::new(4727),
Felt::new(1208),
Felt::new(1908),
Felt::new(4538),
Felt::new(343),
Felt::new(8841),
Felt::new(10179),
Felt::new(11573),
Felt::new(6873),
Felt::new(10125),
Felt::new(814),
Felt::new(416),
Felt::new(1705),
Felt::new(9839),
Felt::new(7187),
Felt::new(412),
Felt::new(5588),
Felt::new(5845),
Felt::new(9761),
Felt::new(3056),
Felt::new(7326),
Felt::new(3744),
Felt::new(6454),
Felt::new(3087),
Felt::new(4883),
Felt::new(3975),
Felt::new(7784),
Felt::new(2257),
Felt::new(5676),
Felt::new(10872),
Felt::new(7723),
Felt::new(6453),
Felt::new(68),
Felt::new(10029),
Felt::new(10754),
Felt::new(9089),
Felt::new(9572),
Felt::new(12229),
Felt::new(448),
Felt::new(1014),
Felt::new(4924),
Felt::new(4781),
Felt::new(5232),
Felt::new(3942),
Felt::new(1327),
Felt::new(3607),
Felt::new(212),
Felt::new(5966),
Felt::new(2769),
Felt::new(9175),
Felt::new(5987),
Felt::new(5596),
Felt::new(11710),
Felt::new(8400),
Felt::new(11014),
Felt::new(5508),
Felt::new(11113),
Felt::new(6555),
Felt::new(4860),
Felt::new(1125),
Felt::new(10844),
Felt::new(11158),
Felt::new(5826),
Felt::new(10224),
Felt::new(4564),
Felt::new(8794),
Felt::new(3961),
Felt::new(3534),
Felt::new(4145),
Felt::new(1756),
Felt::new(9828),
Felt::new(2275),
Felt::new(6636),
Felt::new(4267),
Felt::new(4176),
Felt::new(5063),
Felt::new(3765),
Felt::new(10771),
Felt::new(5268),
Felt::new(12143),
Felt::new(406),
Felt::new(1687),
Felt::new(7100),
Felt::new(6195),
Felt::new(10886),
Felt::new(10485),
Felt::new(7735),
Felt::new(994),
Felt::new(12050),
Felt::new(9389),
Felt::new(7383),
Felt::new(5464),
Felt::new(4670),
Felt::new(11777),
Felt::new(8896),
Felt::new(4335),
Felt::new(9998),
Felt::new(8914),
Felt::new(3825),
Felt::new(8054),
Felt::new(3528),
Felt::new(4913),
Felt::new(11653),
Felt::new(6680),
Felt::new(3982),
Felt::new(9342),
Felt::new(6617),
Felt::new(7790),
Felt::new(1737),
Felt::new(11667),
Felt::new(8038),
Felt::new(7550),
Felt::new(1226),
Felt::new(5518),
Felt::new(5216),
Felt::new(3028),
Felt::new(9929),
Felt::new(364),
Felt::new(3017),
Felt::new(11053),
Felt::new(7814),
Felt::new(7043),
Felt::new(7584),
Felt::new(3121),
Felt::new(2600),
Felt::new(1057),
Felt::new(10821),
Felt::new(8308),
Felt::new(8882),
Felt::new(463),
Felt::new(10945),
Felt::new(9247),
Felt::new(9806),
Felt::new(10235),
Felt::new(1409),
Felt::new(5219),
Felt::new(12085),
Felt::new(6780),
Felt::new(4605),
Felt::new(9600),
Felt::new(8151),
Felt::new(180),
Felt::new(425),
Felt::new(10453),
Felt::new(392),
Felt::new(10104),
Felt::new(10669),
Felt::new(11914),
Felt::new(4578),
Felt::new(377),
Felt::new(6197),
Felt::new(2231),
Felt::new(193),
Felt::new(9489),
Felt::new(11366),
Felt::new(1038),
Felt::new(6204),
Felt::new(4167),
Felt::new(9013),
Felt::new(3338),
Felt::new(10077),
Felt::new(2674),
Felt::new(10897),
Felt::new(6505),
Felt::new(11034),
Felt::new(506),
Felt::new(2776),
Felt::new(11111),
Felt::new(6811),
Felt::new(3511),
Felt::new(2575),
Felt::new(1165),
Felt::new(8881),
Felt::new(1942),
Felt::new(3947),
Felt::new(11951),
Felt::new(2455),
Felt::new(6599),
Felt::new(10545),
Felt::new(10975),
Felt::new(3654),
Felt::new(2894),
Felt::new(4608),
Felt::new(5163),
Felt::new(5002),
Felt::new(20),
Felt::new(8170),
Felt::new(8946),
Felt::new(10138),
Felt::new(10767),
Felt::new(4939),
Felt::new(7174),
Felt::new(9847),
Felt::new(11041),
Felt::new(6330),
Felt::new(2148),
Felt::new(3959),
Felt::new(6492),
Felt::new(5598),
Felt::new(3344),
Felt::new(10397),
Felt::new(8665),
Felt::new(6565),
Felt::new(10964),
Felt::new(11260),
Felt::new(10344),
];
const FELT_BITREVERSED_POWERS_INVERSE_HALVED_1024: [Felt; 1024] = {
let src = FELT_BITREVERSED_POWERS_INVERSE_1024;
let mut result = [Felt::new(0); 1024];
let mut i = 0;
while i < 1024 {
result[i] = src[i].half();
i += 1;
}
result
};
impl FastFft for Polynomial<Felt> {
type Field = Felt;
#[profiling]
fn fft_inplace(&mut self) {
Felt::fft(&mut self.coefficients, &FELT_BITREVERSED_POWERS_1024);
}
#[profiling]
fn ifft_inplace(&mut self) {
let n = self.coefficients.len();
let a = &mut self.coefficients;
let mut t = 1;
let mut m = n;
while m > 1 {
let h = m / 2;
let mut j1 = 0;
for i in 0..h {
let s = FELT_BITREVERSED_POWERS_INVERSE_HALVED_1024[h + i];
for j in j1..j1 + t {
let u = a[j];
let v = a[j + t];
a[j] = (u + v).half();
a[j + t] = (u - v) * s;
}
j1 += 2 * t;
}
t <<= 1;
m >>= 1;
}
}
fn merge_fft(a: &Self, b: &Self) -> Self {
Self {
coefficients: Self::Field::merge_fft(
&a.coefficients,
&b.coefficients,
&FELT_BITREVERSED_POWERS_1024,
),
}
}
fn split_fft(&self) -> (Self, Self) {
let (a, b) =
Self::Field::split_fft(&self.coefficients, &FELT_BITREVERSED_POWERS_INVERSE_1024);
(Self { coefficients: a }, Self { coefficients: b })
}
}
const U32_FIELD_PSI_REV_1024: [U32Field; 1024] = [
U32Field(1),
U32Field(655882981),
U32Field(172781245),
U32Field(506943095),
U32Field(702988283),
U32Field(711638157),
U32Field(939115227),
U32Field(63125917),
U32Field(82460528),
U32Field(198474581),
U32Field(103341490),
U32Field(380887327),
U32Field(220380164),
U32Field(15369996),
U32Field(558672688),
U32Field(790859465),
U32Field(212552520),
U32Field(458980381),
U32Field(24801431),
U32Field(709960537),
U32Field(953525248),
U32Field(809857670),
U32Field(772172083),
U32Field(396089055),
U32Field(768017581),
U32Field(126072806),
U32Field(439040762),
U32Field(769289104),
U32Field(320967569),
U32Field(133255804),
U32Field(1058515541),
U32Field(152591694),
U32Field(360020593),
U32Field(694057462),
U32Field(330795584),
U32Field(644851913),
U32Field(550294870),
U32Field(499758275),
U32Field(258190112),
U32Field(419224128),
U32Field(535899961),
U32Field(706172404),
U32Field(971581923),
U32Field(82356288),
U32Field(797615808),
U32Field(563278264),
U32Field(843219079),
U32Field(144956042),
U32Field(530184162),
U32Field(865596768),
U32Field(228361579),
U32Field(851059211),
U32Field(362808624),
U32Field(195444839),
U32Field(416604876),
U32Field(833792975),
U32Field(335976687),
U32Field(236111590),
U32Field(726829693),
U32Field(135700423),
U32Field(477351786),
U32Field(177348430),
U32Field(881900936),
U32Field(119848233),
U32Field(438899937),
U32Field(377290039),
U32Field(549200374),
U32Field(734094188),
U32Field(715272440),
U32Field(401760798),
U32Field(304249400),
U32Field(655826546),
U32Field(919048578),
U32Field(32781120),
U32Field(334021909),
U32Field(1049119005),
U32Field(137513120),
U32Field(1069806701),
U32Field(666286560),
U32Field(188902643),
U32Field(200140215),
U32Field(927311853),
U32Field(972247171),
U32Field(644866574),
U32Field(930942822),
U32Field(586734544),
U32Field(599886356),
U32Field(1038464617),
U32Field(513368514),
U32Field(38458857),
U32Field(1009396112),
U32Field(1062780171),
U32Field(693711004),
U32Field(169574073),
U32Field(992071453),
U32Field(212414429),
U32Field(274773989),
U32Field(109258324),
U32Field(770187295),
U32Field(73727950),
U32Field(588676622),
U32Field(874107943),
U32Field(16600436),
U32Field(507217693),
U32Field(38675143),
U32Field(915929283),
U32Field(288987389),
U32Field(504862402),
U32Field(963441985),
U32Field(467140026),
U32Field(991615706),
U32Field(550220127),
U32Field(565823917),
U32Field(690048853),
U32Field(416079950),
U32Field(396655002),
U32Field(611541541),
U32Field(733459874),
U32Field(40415307),
U32Field(80773043),
U32Field(827507536),
U32Field(673911563),
U32Field(382583264),
U32Field(939772504),
U32Field(17153319),
U32Field(965867782),
U32Field(5016007),
U32Field(815662212),
U32Field(1059644434),
U32Field(751239108),
U32Field(1015378800),
U32Field(92000091),
U32Field(971718694),
U32Field(139934167),
U32Field(989313395),
U32Field(127561648),
U32Field(458989350),
U32Field(376873055),
U32Field(957761883),
U32Field(472903182),
U32Field(827616361),
U32Field(408411326),
U32Field(793297646),
U32Field(609514052),
U32Field(23719457),
U32Field(765774195),
U32Field(530292503),
U32Field(983951175),
U32Field(928687251),
U32Field(454681855),
U32Field(363387924),
U32Field(1018436637),
U32Field(668475886),
U32Field(813061532),
U32Field(557820575),
U32Field(170824773),
U32Field(805563376),
U32Field(520241734),
U32Field(688243042),
U32Field(1059209916),
U32Field(13636968),
U32Field(501549925),
U32Field(643629576),
U32Field(626050478),
U32Field(599452011),
U32Field(322556315),
U32Field(739340815),
U32Field(257641748),
U32Field(37923481),
U32Field(992353568),
U32Field(974037888),
U32Field(208793500),
U32Field(816230521),
U32Field(119492189),
U32Field(453285762),
U32Field(391449543),
U32Field(603122798),
U32Field(136678033),
U32Field(955372016),
U32Field(77431733),
U32Field(920622900),
U32Field(765199117),
U32Field(593520622),
U32Field(275493746),
U32Field(270954905),
U32Field(833029354),
U32Field(608264848),
U32Field(1008000445),
U32Field(45110417),
U32Field(854186880),
U32Field(9775646),
U32Field(896084877),
U32Field(34502587),
U32Field(694932224),
U32Field(855025629),
U32Field(409590610),
U32Field(848583551),
U32Field(365623917),
U32Field(57552609),
U32Field(305421627),
U32Field(1038268548),
U32Field(315009513),
U32Field(39150536),
U32Field(1005812311),
U32Field(184423729),
U32Field(16605325),
U32Field(368377971),
U32Field(557127817),
U32Field(72072800),
U32Field(323381702),
U32Field(223004229),
U32Field(998590468),
U32Field(546326320),
U32Field(620899833),
U32Field(34874258),
U32Field(55843198),
U32Field(847246632),
U32Field(989109907),
U32Field(103089918),
U32Field(234627679),
U32Field(110240418),
U32Field(889458316),
U32Field(1061523477),
U32Field(653441264),
U32Field(54600292),
U32Field(711611347),
U32Field(503929823),
U32Field(1046945062),
U32Field(728690631),
U32Field(997021354),
U32Field(825235663),
U32Field(780959866),
U32Field(872266859),
U32Field(108332983),
U32Field(746294928),
U32Field(491124105),
U32Field(925108971),
U32Field(857574326),
U32Field(792015933),
U32Field(772650542),
U32Field(995404878),
U32Field(689874161),
U32Field(375007902),
U32Field(123519892),
U32Field(1000769271),
U32Field(635983961),
U32Field(178367361),
U32Field(906955003),
U32Field(154948705),
U32Field(964534195),
U32Field(1030391277),
U32Field(1036103293),
U32Field(647212051),
U32Field(694225796),
U32Field(106218416),
U32Field(825288912),
U32Field(352467225),
U32Field(555334922),
U32Field(481654805),
U32Field(320676609),
U32Field(188715326),
U32Field(246970923),
U32Field(94491261),
U32Field(536712678),
U32Field(518277793),
U32Field(1027213710),
U32Field(957930083),
U32Field(345229536),
U32Field(329046305),
U32Field(695783409),
U32Field(545820573),
U32Field(334020664),
U32Field(1014595532),
U32Field(227832468),
U32Field(551924742),
U32Field(907208506),
U32Field(314535629),
U32Field(745482793),
U32Field(784439433),
U32Field(894428200),
U32Field(722321555),
U32Field(879026727),
U32Field(174738127),
U32Field(971446612),
U32Field(774207574),
U32Field(714602080),
U32Field(204360171),
U32Field(525020510),
U32Field(377546836),
U32Field(346560853),
U32Field(772009067),
U32Field(41860334),
U32Field(773622224),
U32Field(394776880),
U32Field(676257004),
U32Field(849768601),
U32Field(144127463),
U32Field(1018954934),
U32Field(1000823740),
U32Field(1052982427),
U32Field(750501631),
U32Field(784984417),
U32Field(298370936),
U32Field(892568338),
U32Field(560210051),
U32Field(743283658),
U32Field(68544765),
U32Field(979172435),
U32Field(900654341),
U32Field(171271989),
U32Field(193306832),
U32Field(375308328),
U32Field(714993413),
U32Field(918486918),
U32Field(157720372),
U32Field(842934036),
U32Field(165168460),
U32Field(600915700),
U32Field(826582430),
U32Field(662081069),
U32Field(409159153),
U32Field(664368091),
U32Field(888430812),
U32Field(1018454687),
U32Field(856627084),
U32Field(814263218),
U32Field(1017494164),
U32Field(362435372),
U32Field(602563157),
U32Field(751574923),
U32Field(265776960),
U32Field(174785585),
U32Field(140677358),
U32Field(718413858),
U32Field(413194886),
U32Field(8249762),
U32Field(917251932),
U32Field(876057131),
U32Field(210402391),
U32Field(659054303),
U32Field(580050473),
U32Field(120344786),
U32Field(534423937),
U32Field(540813886),
U32Field(634978640),
U32Field(211862207),
U32Field(422056255),
U32Field(565847899),
U32Field(90730954),
U32Field(26784793),
U32Field(81885087),
U32Field(663216234),
U32Field(133199980),
U32Field(682754387),
U32Field(345567893),
U32Field(287305520),
U32Field(716700836),
U32Field(900909757),
U32Field(108117596),
U32Field(1067489565),
U32Field(617327896),
U32Field(398880872),
U32Field(132958869),
U32Field(439576910),
U32Field(968440673),
U32Field(216461613),
U32Field(1038060151),
U32Field(872986504),
U32Field(1031769378),
U32Field(700828330),
U32Field(627721625),
U32Field(918918587),
U32Field(756079427),
U32Field(1056996671),
U32Field(495270823),
U32Field(905158645),
U32Field(495423560),
U32Field(466547081),
U32Field(417424922),
U32Field(876087271),
U32Field(832171240),
U32Field(611573793),
U32Field(44405668),
U32Field(871036690),
U32Field(147000025),
U32Field(744738580),
U32Field(180854988),
U32Field(122037104),
U32Field(1030996967),
U32Field(620908008),
U32Field(465948813),
U32Field(555862478),
U32Field(374264821),
U32Field(786497905),
U32Field(82603839),
U32Field(83066765),
U32Field(23005486),
U32Field(686691752),
U32Field(120798839),
U32Field(425635083),
U32Field(58166237),
U32Field(729389696),
U32Field(220559044),
U32Field(619854331),
U32Field(790433989),
U32Field(299301491),
U32Field(81968761),
U32Field(369298885),
U32Field(868432543),
U32Field(630804773),
U32Field(551779604),
U32Field(1034000143),
U32Field(1013785059),
U32Field(713016574),
U32Field(734346865),
U32Field(637481117),
U32Field(218071323),
U32Field(955756457),
U32Field(485509742),
U32Field(828102785),
U32Field(797750513),
U32Field(644308003),
U32Field(646673416),
U32Field(374243556),
U32Field(340383340),
U32Field(299677484),
U32Field(488219621),
U32Field(636605444),
U32Field(189920839),
U32Field(759625931),
U32Field(87392867),
U32Field(948335576),
U32Field(1697882),
U32Field(41871682),
U32Field(730856247),
U32Field(742765199),
U32Field(711135241),
U32Field(367744495),
U32Field(235864135),
U32Field(370156360),
U32Field(373653513),
U32Field(501467635),
U32Field(569872963),
U32Field(35609661),
U32Field(901576747),
U32Field(993340233),
U32Field(548652051),
U32Field(696632754),
U32Field(178803506),
U32Field(8950692),
U32Field(100925920),
U32Field(838483448),
U32Field(396366611),
U32Field(285938446),
U32Field(585271279),
U32Field(622604743),
U32Field(532942154),
U32Field(612337323),
U32Field(665734558),
U32Field(957200134),
U32Field(497982667),
U32Field(1018783369),
U32Field(609764415),
U32Field(968481593),
U32Field(875751365),
U32Field(644126971),
U32Field(878763459),
U32Field(970964519),
U32Field(745870026),
U32Field(938235715),
U32Field(801738142),
U32Field(584128042),
U32Field(480139225),
U32Field(94999961),
U32Field(687853923),
U32Field(849628695),
U32Field(852428710),
U32Field(108824711),
U32Field(18180283),
U32Field(1072974340),
U32Field(43443288),
U32Field(710617186),
U32Field(958949873),
U32Field(338353566),
U32Field(1004239677),
U32Field(392167005),
U32Field(443363789),
U32Field(396532045),
U32Field(283121181),
U32Field(46375299),
U32Field(389226673),
U32Field(279370168),
U32Field(580920224),
U32Field(577584894),
U32Field(1011913130),
U32Field(226966154),
U32Field(989607965),
U32Field(852214502),
U32Field(366317617),
U32Field(123772320),
U32Field(86545690),
U32Field(398044405),
U32Field(771022952),
U32Field(859771182),
U32Field(725486320),
U32Field(429140485),
U32Field(782017076),
U32Field(585030659),
U32Field(735618781),
U32Field(133391962),
U32Field(836232510),
U32Field(822486687),
U32Field(198925374),
U32Field(589145951),
U32Field(980815818),
U32Field(281167168),
U32Field(866042273),
U32Field(58003779),
U32Field(474760192),
U32Field(605080880),
U32Field(1046798914),
U32Field(761092838),
U32Field(861234982),
U32Field(676491706),
U32Field(464170161),
U32Field(652288507),
U32Field(1004853885),
U32Field(45553939),
U32Field(865947611),
U32Field(547332356),
U32Field(79195218),
U32Field(576640186),
U32Field(615123647),
U32Field(375490628),
U32Field(314051173),
U32Field(690912530),
U32Field(778070135),
U32Field(127217046),
U32Field(392696935),
U32Field(78765892),
U32Field(129057778),
U32Field(658753469),
U32Field(224674858),
U32Field(1046300068),
U32Field(756435042),
U32Field(941105013),
U32Field(666103299),
U32Field(600839048),
U32Field(225883784),
U32Field(236489511),
U32Field(863036223),
U32Field(661472312),
U32Field(808009930),
U32Field(70586279),
U32Field(593854593),
U32Field(331489297),
U32Field(818000251),
U32Field(195025528),
U32Field(425978263),
U32Field(94683116),
U32Field(912055838),
U32Field(235687911),
U32Field(982661034),
U32Field(611007956),
U32Field(760157441),
U32Field(1015475665),
U32Field(939842975),
U32Field(601176702),
U32Field(968960754),
U32Field(138977008),
U32Field(946532252),
U32Field(612362953),
U32Field(927955631),
U32Field(839959996),
U32Field(1073136288),
U32Field(1014460519),
U32Field(971711555),
U32Field(433019601),
U32Field(173727064),
U32Field(685921366),
U32Field(34996512),
U32Field(711659984),
U32Field(928315127),
U32Field(334915676),
U32Field(559160893),
U32Field(853806727),
U32Field(707476167),
U32Field(200300715),
U32Field(713546632),
U32Field(269421264),
U32Field(1009083218),
U32Field(468170282),
U32Field(730808640),
U32Field(891294772),
U32Field(475400660),
U32Field(729576354),
U32Field(914623451),
U32Field(502189437),
U32Field(882889800),
U32Field(564850540),
U32Field(516553595),
U32Field(292426394),
U32Field(664498971),
U32Field(282830342),
U32Field(561622626),
U32Field(203784135),
U32Field(78307514),
U32Field(913599456),
U32Field(979785106),
U32Field(821566592),
U32Field(374961126),
U32Field(917471385),
U32Field(954852113),
U32Field(936642752),
U32Field(918152378),
U32Field(771780284),
U32Field(812313561),
U32Field(30260568),
U32Field(781507445),
U32Field(867163435),
U32Field(912845815),
U32Field(174419989),
U32Field(716906065),
U32Field(219857613),
U32Field(919138707),
U32Field(724792680),
U32Field(278951675),
U32Field(938311884),
U32Field(759525836),
U32Field(677073012),
U32Field(293361279),
U32Field(915385262),
U32Field(274230366),
U32Field(1047503280),
U32Field(626225448),
U32Field(656975006),
U32Field(889419256),
U32Field(873657902),
U32Field(362611769),
U32Field(988291882),
U32Field(751713020),
U32Field(488770111),
U32Field(856231377),
U32Field(434153881),
U32Field(1034466753),
U32Field(682451659),
U32Field(981984641),
U32Field(350675729),
U32Field(129675956),
U32Field(313850948),
U32Field(246264019),
U32Field(534477250),
U32Field(371383723),
U32Field(997533625),
U32Field(306262420),
U32Field(976828558),
U32Field(934783679),
U32Field(547160040),
U32Field(293444236),
U32Field(657672030),
U32Field(241064207),
U32Field(890529408),
U32Field(790400255),
U32Field(520072915),
U32Field(981716568),
U32Field(920805640),
U32Field(153179142),
U32Field(898539157),
U32Field(747645856),
U32Field(18374003),
U32Field(313486177),
U32Field(228395675),
U32Field(126018154),
U32Field(122613199),
U32Field(522357086),
U32Field(184309037),
U32Field(413530541),
U32Field(751957153),
U32Field(52977),
U32Field(29587757),
U32Field(723093675),
U32Field(151477579),
U32Field(523611955),
U32Field(918375557),
U32Field(793123130),
U32Field(723647656),
U32Field(479660172),
U32Field(387603141),
U32Field(163309551),
U32Field(144817211),
U32Field(766763624),
U32Field(549998130),
U32Field(953455628),
U32Field(704129888),
U32Field(1009223122),
U32Field(241755352),
U32Field(440564467),
U32Field(1002523558),
U32Field(444543739),
U32Field(169264132),
U32Field(782250420),
U32Field(474606781),
U32Field(576538841),
U32Field(208460602),
U32Field(511384199),
U32Field(707563221),
U32Field(429013063),
U32Field(1004694053),
U32Field(974768001),
U32Field(335401065),
U32Field(823518448),
U32Field(515736928),
U32Field(510096346),
U32Field(327120121),
U32Field(870395407),
U32Field(16017617),
U32Field(849704569),
U32Field(643079486),
U32Field(733832401),
U32Field(759308296),
U32Field(177135040),
U32Field(206945722),
U32Field(898709877),
U32Field(36679425),
U32Field(431855944),
U32Field(629787328),
U32Field(890859425),
U32Field(643561478),
U32Field(207639022),
U32Field(438032003),
U32Field(191237532),
U32Field(479032350),
U32Field(45729963),
U32Field(98763899),
U32Field(170203107),
U32Field(237259021),
U32Field(945986353),
U32Field(205406110),
U32Field(812661012),
U32Field(97473557),
U32Field(192421071),
U32Field(546767550),
U32Field(530399547),
U32Field(835336721),
U32Field(813747602),
U32Field(684655648),
U32Field(966769062),
U32Field(344132471),
U32Field(482869221),
U32Field(10890853),
U32Field(130016834),
U32Field(384993519),
U32Field(671879749),
U32Field(1031471004),
U32Field(125718859),
U32Field(278999351),
U32Field(538122523),
U32Field(901085683),
U32Field(580058293),
U32Field(875612518),
U32Field(574998150),
U32Field(419587370),
U32Field(937653220),
U32Field(1000550683),
U32Field(465550201),
U32Field(749243911),
U32Field(679592114),
U32Field(523314928),
U32Field(946347847),
U32Field(174539968),
U32Field(993041945),
U32Field(443945890),
U32Field(852872163),
U32Field(239039229),
U32Field(507377927),
U32Field(1053167243),
U32Field(238171328),
U32Field(878763115),
U32Field(242255626),
U32Field(263854906),
U32Field(477214315),
U32Field(568444215),
U32Field(986103214),
U32Field(8831527),
U32Field(361972462),
U32Field(1052271232),
U32Field(921127336),
U32Field(192780595),
U32Field(870030114),
U32Field(530735213),
U32Field(888306589),
U32Field(655246251),
U32Field(163950432),
U32Field(562947362),
U32Field(1017183231),
U32Field(670677963),
U32Field(593995733),
U32Field(92083568),
U32Field(385845236),
U32Field(608852728),
U32Field(20360704),
U32Field(134053918),
U32Field(743249902),
U32Field(263693373),
U32Field(743600892),
U32Field(44383815),
U32Field(64688341),
U32Field(142488116),
U32Field(258581522),
U32Field(956620),
U32Field(551564646),
U32Field(876469584),
U32Field(330171451),
U32Field(450311560),
U32Field(416594580),
U32Field(702237256),
U32Field(236908552),
U32Field(310331618),
U32Field(921072880),
U32Field(785982091),
U32Field(294296440),
U32Field(832827665),
U32Field(440004217),
U32Field(547460942),
U32Field(56028723),
U32Field(544074155),
U32Field(986371029),
U32Field(947796485),
U32Field(433303456),
U32Field(761223582),
U32Field(713355453),
U32Field(74804579),
U32Field(573364451),
U32Field(385085046),
U32Field(92965744),
U32Field(489319743),
U32Field(503554489),
U32Field(100871353),
U32Field(489209265),
U32Field(489621030),
U32Field(194514657),
U32Field(74853739),
U32Field(197881999),
U32Field(97666914),
U32Field(395031688),
U32Field(71836652),
U32Field(827103335),
U32Field(933853969),
U32Field(64423226),
U32Field(540793634),
U32Field(568830333),
U32Field(692584167),
U32Field(1044308009),
U32Field(143579132),
U32Field(243976804),
U32Field(234623974),
U32Field(527454540),
U32Field(360248893),
U32Field(981137518),
U32Field(857933916),
U32Field(96328429),
U32Field(895541886),
U32Field(935383571),
U32Field(559509163),
U32Field(613711939),
U32Field(475854788),
U32Field(853806132),
U32Field(36962544),
U32Field(987609878),
U32Field(46748977),
U32Field(755496949),
U32Field(1068378701),
U32Field(994156849),
U32Field(50713567),
U32Field(1040335022),
U32Field(1059334336),
U32Field(690099782),
U32Field(555568228),
U32Field(557725572),
U32Field(344912333),
U32Field(31897964),
U32Field(558536479),
U32Field(526662328),
U32Field(197418525),
U32Field(599144492),
U32Field(1037970435),
U32Field(872187352),
U32Field(762414574),
U32Field(116900429),
U32Field(257846609),
U32Field(950980880),
U32Field(308599002),
U32Field(414253097),
U32Field(819862909),
U32Field(882104913),
U32Field(768954435),
U32Field(633683935),
U32Field(455950313),
U32Field(243380385),
U32Field(671394191),
U32Field(1024657437),
U32Field(107238583),
U32Field(183062845),
U32Field(17157744),
U32Field(819847710),
U32Field(627257889),
U32Field(1069372078),
U32Field(423063183),
U32Field(516864148),
U32Field(933359352),
U32Field(757942620),
U32Field(227517930),
U32Field(487841254),
U32Field(63821751),
U32Field(23766461),
U32Field(261320663),
U32Field(741083140),
U32Field(503932402),
U32Field(480867921),
U32Field(706485307),
U32Field(377337081),
U32Field(357609323),
U32Field(390786068),
U32Field(62778999),
U32Field(897397510),
U32Field(808682266),
U32Field(1048863921),
U32Field(335015669),
U32Field(989033247),
U32Field(921033472),
U32Field(655123947),
U32Field(21859191),
U32Field(452860893),
U32Field(1007617266),
U32Field(72153755),
U32Field(189220707),
U32Field(387286584),
U32Field(561829543),
U32Field(55065512),
U32Field(811986844),
U32Field(28678057),
U32Field(495118485),
U32Field(909970351),
U32Field(842267830),
U32Field(308105492),
U32Field(637691999),
U32Field(646255290),
U32Field(816160715),
U32Field(49075518),
U32Field(992559944),
U32Field(244110210),
U32Field(884427116),
U32Field(948123994),
U32Field(1008793537),
U32Field(514984882),
U32Field(799811801),
U32Field(707472166),
U32Field(267545906),
U32Field(1053694254),
U32Field(556789582),
U32Field(481217010),
U32Field(282154061),
U32Field(546178658),
U32Field(1027889672),
U32Field(111773901),
U32Field(813164039),
U32Field(746034158),
U32Field(957566166),
U32Field(838107496),
U32Field(570126940),
U32Field(195396302),
U32Field(780638916),
U32Field(313991695),
U32Field(643648015),
U32Field(593216041),
U32Field(586473209),
U32Field(874126261),
U32Field(714753092),
U32Field(86938479),
U32Field(341444550),
U32Field(953772848),
U32Field(716394924),
U32Field(897063937),
U32Field(871863694),
U32Field(207054939),
U32Field(36260268),
U32Field(531132728),
U32Field(995722232),
U32Field(113241674),
U32Field(1008775846),
U32Field(850926751),
U32Field(31012104),
U32Field(848989789),
U32Field(389197236),
U32Field(132346222),
U32Field(258099515),
U32Field(396470938),
U32Field(535092195),
U32Field(150169350),
U32Field(716040993),
U32Field(877334132),
U32Field(810850546),
U32Field(1044036630),
U32Field(274128004),
U32Field(439533967),
U32Field(1002080264),
U32Field(352343012),
U32Field(308431618),
U32Field(446195072),
U32Field(638702287),
U32Field(283758557),
U32Field(502212978),
U32Field(542682390),
U32Field(919775067),
U32Field(513217749),
U32Field(4602788),
U32Field(524958625),
U32Field(530340270),
U32Field(175656968),
U32Field(59637479),
U32Field(143181411),
U32Field(492326136),
U32Field(694559216),
U32Field(946151163),
];
const U32_FIELD_PSI_REV_INV_1024: [U32Field; 1024] = [
U32Field(1),
U32Field(417871132),
U32Field(566811018),
U32Field(900972868),
U32Field(1010628196),
U32Field(134638886),
U32Field(362115956),
U32Field(370765830),
U32Field(282894648),
U32Field(515081425),
U32Field(1058384117),
U32Field(853373949),
U32Field(692866786),
U32Field(970412623),
U32Field(875279532),
U32Field(991293585),
U32Field(921162419),
U32Field(15238572),
U32Field(940498309),
U32Field(752786544),
U32Field(304465009),
U32Field(634713351),
U32Field(947681307),
U32Field(305736532),
U32Field(677665058),
U32Field(301582030),
U32Field(263896443),
U32Field(120228865),
U32Field(363793576),
U32Field(1048952682),
U32Field(614773732),
U32Field(861201593),
U32Field(953905880),
U32Field(191853177),
U32Field(896405683),
U32Field(596402327),
U32Field(938053690),
U32Field(346924420),
U32Field(837642523),
U32Field(737777426),
U32Field(239961138),
U32Field(657149237),
U32Field(878309274),
U32Field(710945489),
U32Field(222694902),
U32Field(845392534),
U32Field(208157345),
U32Field(543569951),
U32Field(928798071),
U32Field(230535034),
U32Field(510475849),
U32Field(276138305),
U32Field(991397825),
U32Field(102172190),
U32Field(367581709),
U32Field(537854152),
U32Field(654529985),
U32Field(815564001),
U32Field(573995838),
U32Field(523459243),
U32Field(428902200),
U32Field(742958529),
U32Field(379696651),
U32Field(713733520),
U32Field(258091901),
U32Field(1068738106),
U32Field(107886331),
U32Field(1056600794),
U32Field(133981609),
U32Field(691170849),
U32Field(399842550),
U32Field(246246577),
U32Field(992981070),
U32Field(1033338806),
U32Field(340294239),
U32Field(462212572),
U32Field(677099111),
U32Field(657674163),
U32Field(383705260),
U32Field(507930196),
U32Field(523533986),
U32Field(82138407),
U32Field(606614087),
U32Field(110312128),
U32Field(568891711),
U32Field(784766724),
U32Field(157824830),
U32Field(1035078970),
U32Field(566536420),
U32Field(1057153677),
U32Field(199646170),
U32Field(485077491),
U32Field(1000026163),
U32Field(303566818),
U32Field(964495789),
U32Field(798980124),
U32Field(861339684),
U32Field(81682660),
U32Field(904180040),
U32Field(380043109),
U32Field(10973942),
U32Field(64358001),
U32Field(1035295256),
U32Field(560385599),
U32Field(35289496),
U32Field(473867757),
U32Field(487019569),
U32Field(142811291),
U32Field(428887539),
U32Field(101506942),
U32Field(146442260),
U32Field(873613898),
U32Field(884851470),
U32Field(407467553),
U32Field(3947412),
U32Field(936240993),
U32Field(24635108),
U32Field(739732204),
U32Field(1040972993),
U32Field(154705535),
U32Field(417927567),
U32Field(769504713),
U32Field(671993315),
U32Field(358481673),
U32Field(339659925),
U32Field(524553739),
U32Field(696464074),
U32Field(634854176),
U32Field(248465201),
U32Field(967535697),
U32Field(379528317),
U32Field(426542062),
U32Field(37650820),
U32Field(43362836),
U32Field(109219918),
U32Field(918805408),
U32Field(166799110),
U32Field(895386752),
U32Field(437770152),
U32Field(72984842),
U32Field(950234221),
U32Field(698746211),
U32Field(383879952),
U32Field(78349235),
U32Field(301103571),
U32Field(281738180),
U32Field(216179787),
U32Field(148645142),
U32Field(582630008),
U32Field(327459185),
U32Field(965421130),
U32Field(201487254),
U32Field(292794247),
U32Field(248518450),
U32Field(76732759),
U32Field(345063482),
U32Field(26809051),
U32Field(569824290),
U32Field(362142766),
U32Field(1019153821),
U32Field(420312849),
U32Field(12230636),
U32Field(184295797),
U32Field(963513695),
U32Field(839126434),
U32Field(970664195),
U32Field(84644206),
U32Field(226507481),
U32Field(1017910915),
U32Field(1038879855),
U32Field(452854280),
U32Field(527427793),
U32Field(75163645),
U32Field(850749884),
U32Field(750372411),
U32Field(1001681313),
U32Field(516626296),
U32Field(705376142),
U32Field(1057148788),
U32Field(889330384),
U32Field(67941802),
U32Field(1034603577),
U32Field(758744600),
U32Field(35485565),
U32Field(768332486),
U32Field(1016201504),
U32Field(708130196),
U32Field(225170562),
U32Field(664163503),
U32Field(218728484),
U32Field(378821889),
U32Field(1039251526),
U32Field(177669236),
U32Field(1063978467),
U32Field(219567233),
U32Field(1028643696),
U32Field(65753668),
U32Field(465489265),
U32Field(240724759),
U32Field(802799208),
U32Field(798260367),
U32Field(480233491),
U32Field(308554996),
U32Field(153131213),
U32Field(996322380),
U32Field(118382097),
U32Field(937076080),
U32Field(470631315),
U32Field(682304570),
U32Field(620468351),
U32Field(954261924),
U32Field(257523592),
U32Field(864960613),
U32Field(99716225),
U32Field(81400545),
U32Field(1035830632),
U32Field(816112365),
U32Field(334413298),
U32Field(751197798),
U32Field(474302102),
U32Field(447703635),
U32Field(430124537),
U32Field(572204188),
U32Field(1060117145),
U32Field(14544197),
U32Field(385511071),
U32Field(553512379),
U32Field(268190737),
U32Field(902929340),
U32Field(515933538),
U32Field(260692581),
U32Field(405278227),
U32Field(55317476),
U32Field(710366189),
U32Field(619072258),
U32Field(145066862),
U32Field(89802938),
U32Field(543461610),
U32Field(307979918),
U32Field(1050034656),
U32Field(464240061),
U32Field(280456467),
U32Field(665342787),
U32Field(246137752),
U32Field(600850931),
U32Field(115992230),
U32Field(696881058),
U32Field(614764763),
U32Field(946192465),
U32Field(84440718),
U32Field(933819946),
U32Field(102035419),
U32Field(981754022),
U32Field(58375313),
U32Field(322515005),
U32Field(14109679),
U32Field(251267426),
U32Field(237521603),
U32Field(940362151),
U32Field(338135332),
U32Field(488723454),
U32Field(291737037),
U32Field(644613628),
U32Field(348267793),
U32Field(213982931),
U32Field(302731161),
U32Field(675709708),
U32Field(987208423),
U32Field(949981793),
U32Field(707436496),
U32Field(221539611),
U32Field(84146148),
U32Field(846787959),
U32Field(61840983),
U32Field(496169219),
U32Field(492833889),
U32Field(794383945),
U32Field(684527440),
U32Field(1027378814),
U32Field(790632932),
U32Field(677222068),
U32Field(630390324),
U32Field(681587108),
U32Field(69514436),
U32Field(735400547),
U32Field(114804240),
U32Field(363136927),
U32Field(1030310825),
U32Field(779773),
U32Field(1055573830),
U32Field(964929402),
U32Field(221325403),
U32Field(224125418),
U32Field(385900190),
U32Field(978754152),
U32Field(593614888),
U32Field(489626071),
U32Field(272015971),
U32Field(135518398),
U32Field(327884087),
U32Field(102789594),
U32Field(194990654),
U32Field(429627142),
U32Field(198002748),
U32Field(105272520),
U32Field(463989698),
U32Field(54970744),
U32Field(575771446),
U32Field(116553979),
U32Field(408019555),
U32Field(461416790),
U32Field(540811959),
U32Field(451149370),
U32Field(488482834),
U32Field(787815667),
U32Field(677387502),
U32Field(235270665),
U32Field(972828193),
U32Field(1064803421),
U32Field(894950607),
U32Field(377121359),
U32Field(525102062),
U32Field(80413880),
U32Field(172177366),
U32Field(1038144452),
U32Field(503881150),
U32Field(572286478),
U32Field(700100600),
U32Field(703597753),
U32Field(837889978),
U32Field(706009618),
U32Field(362618872),
U32Field(330988914),
U32Field(342897866),
U32Field(1031882431),
U32Field(1072056231),
U32Field(125418537),
U32Field(986361246),
U32Field(314128182),
U32Field(883833274),
U32Field(437148669),
U32Field(585534492),
U32Field(774076629),
U32Field(733370773),
U32Field(699510557),
U32Field(427080697),
U32Field(429446110),
U32Field(276003600),
U32Field(245651328),
U32Field(588244371),
U32Field(117997656),
U32Field(855682790),
U32Field(436272996),
U32Field(339407248),
U32Field(360737539),
U32Field(59969054),
U32Field(39753970),
U32Field(521974509),
U32Field(442949340),
U32Field(205321570),
U32Field(704455228),
U32Field(991785352),
U32Field(774452622),
U32Field(283320124),
U32Field(453899782),
U32Field(853195069),
U32Field(344364417),
U32Field(1015587876),
U32Field(648119030),
U32Field(952955274),
U32Field(387062361),
U32Field(1050748627),
U32Field(990687348),
U32Field(991150274),
U32Field(287256208),
U32Field(699489292),
U32Field(517891635),
U32Field(607805300),
U32Field(452846105),
U32Field(42757146),
U32Field(951717009),
U32Field(892899125),
U32Field(329015533),
U32Field(926754088),
U32Field(202717423),
U32Field(1029348445),
U32Field(462180320),
U32Field(241582873),
U32Field(197666842),
U32Field(656329191),
U32Field(607207032),
U32Field(578330553),
U32Field(168595468),
U32Field(578483290),
U32Field(16757442),
U32Field(317674686),
U32Field(154835526),
U32Field(446032488),
U32Field(372925783),
U32Field(41984735),
U32Field(200767609),
U32Field(35693962),
U32Field(857292500),
U32Field(105313440),
U32Field(634177203),
U32Field(940795244),
U32Field(674873241),
U32Field(456426217),
U32Field(6264548),
U32Field(965636517),
U32Field(172844356),
U32Field(357053277),
U32Field(786448593),
U32Field(728186220),
U32Field(390999726),
U32Field(940554133),
U32Field(410537879),
U32Field(991869026),
U32Field(1046969320),
U32Field(983023159),
U32Field(507906214),
U32Field(651697858),
U32Field(861891906),
U32Field(438775473),
U32Field(532940227),
U32Field(539330176),
U32Field(953409327),
U32Field(493703640),
U32Field(414699810),
U32Field(863351722),
U32Field(197696982),
U32Field(156502181),
U32Field(1065504351),
U32Field(660559227),
U32Field(355340255),
U32Field(933076755),
U32Field(898968528),
U32Field(807977153),
U32Field(322179190),
U32Field(471190956),
U32Field(711318741),
U32Field(56259949),
U32Field(259490895),
U32Field(217127029),
U32Field(55299426),
U32Field(185323301),
U32Field(409386022),
U32Field(664594960),
U32Field(411673044),
U32Field(247171683),
U32Field(472838413),
U32Field(908585653),
U32Field(230820077),
U32Field(916033741),
U32Field(155267195),
U32Field(358760700),
U32Field(698445785),
U32Field(880447281),
U32Field(902482124),
U32Field(173099772),
U32Field(94581678),
U32Field(1005209348),
U32Field(330470455),
U32Field(513544062),
U32Field(181185775),
U32Field(775383177),
U32Field(288769696),
U32Field(323252482),
U32Field(20771686),
U32Field(72930373),
U32Field(54799179),
U32Field(929626650),
U32Field(223985512),
U32Field(397497109),
U32Field(678977233),
U32Field(300131889),
U32Field(1031893779),
U32Field(301745046),
U32Field(727193260),
U32Field(696207277),
U32Field(548733603),
U32Field(869393942),
U32Field(359152033),
U32Field(299546539),
U32Field(102307501),
U32Field(899015986),
U32Field(194727386),
U32Field(351432558),
U32Field(179325913),
U32Field(289314680),
U32Field(328271320),
U32Field(759218484),
U32Field(166545607),
U32Field(521829371),
U32Field(845921645),
U32Field(59158581),
U32Field(739733449),
U32Field(527933540),
U32Field(377970704),
U32Field(744707808),
U32Field(728524577),
U32Field(115824030),
U32Field(46540403),
U32Field(555476320),
U32Field(537041435),
U32Field(979262852),
U32Field(826783190),
U32Field(885038787),
U32Field(753077504),
U32Field(592099308),
U32Field(518419191),
U32Field(721286888),
U32Field(127602950),
U32Field(379194897),
U32Field(581427977),
U32Field(930572702),
U32Field(1014116634),
U32Field(898097145),
U32Field(543413843),
U32Field(548795488),
U32Field(1069151325),
U32Field(560536364),
U32Field(153979046),
U32Field(531071723),
U32Field(571541135),
U32Field(789995556),
U32Field(435051826),
U32Field(627559041),
U32Field(765322495),
U32Field(721411101),
U32Field(71673849),
U32Field(634220146),
U32Field(799626109),
U32Field(29717483),
U32Field(262903567),
U32Field(196419981),
U32Field(357713120),
U32Field(923584763),
U32Field(538661918),
U32Field(677283175),
U32Field(815654598),
U32Field(941407891),
U32Field(684556877),
U32Field(224764324),
U32Field(1042742009),
U32Field(222827362),
U32Field(64978267),
U32Field(960512439),
U32Field(78031881),
U32Field(542621385),
U32Field(1037493845),
U32Field(866699174),
U32Field(201890419),
U32Field(176690176),
U32Field(357359189),
U32Field(119981265),
U32Field(732309563),
U32Field(986815634),
U32Field(359001021),
U32Field(199627852),
U32Field(487280904),
U32Field(480538072),
U32Field(430106098),
U32Field(759762418),
U32Field(293115197),
U32Field(878357811),
U32Field(503627173),
U32Field(235646617),
U32Field(116187947),
U32Field(327719955),
U32Field(260590074),
U32Field(961980212),
U32Field(45864441),
U32Field(527575455),
U32Field(791600052),
U32Field(592537103),
U32Field(516964531),
U32Field(20059859),
U32Field(806208207),
U32Field(366281947),
U32Field(273942312),
U32Field(558769231),
U32Field(64960576),
U32Field(125630119),
U32Field(189326997),
U32Field(829643903),
U32Field(81194169),
U32Field(1024678595),
U32Field(257593398),
U32Field(427498823),
U32Field(436062114),
U32Field(765648621),
U32Field(231486283),
U32Field(163783762),
U32Field(578635628),
U32Field(1045076056),
U32Field(261767269),
U32Field(1018688601),
U32Field(511924570),
U32Field(686467529),
U32Field(884533406),
U32Field(1001600358),
U32Field(66136847),
U32Field(620893220),
U32Field(1051894922),
U32Field(418630166),
U32Field(152720641),
U32Field(84720866),
U32Field(738738444),
U32Field(24890192),
U32Field(265071847),
U32Field(176356603),
U32Field(1010975114),
U32Field(682968045),
U32Field(716144790),
U32Field(696417032),
U32Field(367268806),
U32Field(592886192),
U32Field(569821711),
U32Field(332670973),
U32Field(812433450),
U32Field(1049987652),
U32Field(1009932362),
U32Field(585912859),
U32Field(846236183),
U32Field(315811493),
U32Field(140394761),
U32Field(556889965),
U32Field(650690930),
U32Field(4382035),
U32Field(446496224),
U32Field(253906403),
U32Field(1056596369),
U32Field(890691268),
U32Field(966515530),
U32Field(49096676),
U32Field(402359922),
U32Field(830373728),
U32Field(617803800),
U32Field(440070178),
U32Field(304799678),
U32Field(191649200),
U32Field(253891204),
U32Field(659501016),
U32Field(765155111),
U32Field(122773233),
U32Field(815907504),
U32Field(956853684),
U32Field(311339539),
U32Field(201566761),
U32Field(35783678),
U32Field(474609621),
U32Field(876335588),
U32Field(547091785),
U32Field(515217634),
U32Field(1041856149),
U32Field(728841780),
U32Field(516028541),
U32Field(518185885),
U32Field(383654331),
U32Field(14419777),
U32Field(33419091),
U32Field(1023040546),
U32Field(79597264),
U32Field(5375412),
U32Field(318257164),
U32Field(1027005136),
U32Field(86144235),
U32Field(1036791569),
U32Field(219947981),
U32Field(597899325),
U32Field(460042174),
U32Field(514244950),
U32Field(138370542),
U32Field(178212227),
U32Field(977425684),
U32Field(215820197),
U32Field(92616595),
U32Field(713505220),
U32Field(546299573),
U32Field(839130139),
U32Field(829777309),
U32Field(930174981),
U32Field(29446104),
U32Field(381169946),
U32Field(504923780),
U32Field(532960479),
U32Field(1009330887),
U32Field(139900144),
U32Field(246650778),
U32Field(1001917461),
U32Field(678722425),
U32Field(976087199),
U32Field(875872114),
U32Field(998900374),
U32Field(879239456),
U32Field(584133083),
U32Field(584544848),
U32Field(972882760),
U32Field(570199624),
U32Field(584434370),
U32Field(980788369),
U32Field(688669067),
U32Field(500389662),
U32Field(998949534),
U32Field(360398660),
U32Field(312530531),
U32Field(640450657),
U32Field(125957628),
U32Field(87383084),
U32Field(529679958),
U32Field(1017725390),
U32Field(526293171),
U32Field(633749896),
U32Field(240926448),
U32Field(779457673),
U32Field(287772022),
U32Field(152681233),
U32Field(763422495),
U32Field(836845561),
U32Field(371516857),
U32Field(657159533),
U32Field(623442553),
U32Field(743582662),
U32Field(197284529),
U32Field(522189467),
U32Field(1072797493),
U32Field(815172591),
U32Field(931265997),
U32Field(1009065772),
U32Field(1029370298),
U32Field(330153221),
U32Field(810060740),
U32Field(330504211),
U32Field(939700195),
U32Field(1053393409),
U32Field(464901385),
U32Field(687908877),
U32Field(981670545),
U32Field(479758380),
U32Field(403076150),
U32Field(56570882),
U32Field(510806751),
U32Field(909803681),
U32Field(418507862),
U32Field(185447524),
U32Field(543018900),
U32Field(203723999),
U32Field(880973518),
U32Field(152626777),
U32Field(21482881),
U32Field(711781651),
U32Field(1064922586),
U32Field(87650899),
U32Field(505309898),
U32Field(596539798),
U32Field(809899207),
U32Field(831498487),
U32Field(194990998),
U32Field(835582785),
U32Field(20586870),
U32Field(566376186),
U32Field(834714884),
U32Field(220881950),
U32Field(629808223),
U32Field(80712168),
U32Field(899214145),
U32Field(127406266),
U32Field(550439185),
U32Field(394161999),
U32Field(324510202),
U32Field(608203912),
U32Field(73203430),
U32Field(136100893),
U32Field(654166743),
U32Field(498755963),
U32Field(198141595),
U32Field(493695820),
U32Field(172668430),
U32Field(535631590),
U32Field(794754762),
U32Field(948035254),
U32Field(42283109),
U32Field(401874364),
U32Field(688760594),
U32Field(943737279),
U32Field(1062863260),
U32Field(590884892),
U32Field(729621642),
U32Field(106985051),
U32Field(389098465),
U32Field(260006511),
U32Field(238417392),
U32Field(543354566),
U32Field(526986563),
U32Field(881333042),
U32Field(976280556),
U32Field(261093101),
U32Field(868348003),
U32Field(127767760),
U32Field(836495092),
U32Field(903551006),
U32Field(974990214),
U32Field(1028024150),
U32Field(594721763),
U32Field(882516581),
U32Field(635722110),
U32Field(866115091),
U32Field(430192635),
U32Field(182894688),
U32Field(443966785),
U32Field(641898169),
U32Field(1037074688),
U32Field(175044236),
U32Field(866808391),
U32Field(896619073),
U32Field(314445817),
U32Field(339921712),
U32Field(430674627),
U32Field(224049544),
U32Field(1057736496),
U32Field(203358706),
U32Field(746633992),
U32Field(563657767),
U32Field(558017185),
U32Field(250235665),
U32Field(738353048),
U32Field(98986112),
U32Field(69060060),
U32Field(644741050),
U32Field(366190892),
U32Field(562369914),
U32Field(865293511),
U32Field(497215272),
U32Field(599147332),
U32Field(291503693),
U32Field(904489981),
U32Field(629210374),
U32Field(71230555),
U32Field(633189646),
U32Field(831998761),
U32Field(64530991),
U32Field(369624225),
U32Field(120298485),
U32Field(523755983),
U32Field(306990489),
U32Field(928936902),
U32Field(910444562),
U32Field(686150972),
U32Field(594093941),
U32Field(350106457),
U32Field(280630983),
U32Field(155378556),
U32Field(550142158),
U32Field(922276534),
U32Field(350660438),
U32Field(1044166356),
U32Field(1073701136),
U32Field(321796960),
U32Field(660223572),
U32Field(889445076),
U32Field(551397027),
U32Field(951140914),
U32Field(947735959),
U32Field(845358438),
U32Field(760267936),
U32Field(1055380110),
U32Field(326108257),
U32Field(175214956),
U32Field(920574971),
U32Field(152948473),
U32Field(92037545),
U32Field(553681198),
U32Field(283353858),
U32Field(183224705),
U32Field(832689906),
U32Field(416082083),
U32Field(780309877),
U32Field(526594073),
U32Field(138970434),
U32Field(96925555),
U32Field(767491693),
U32Field(76220488),
U32Field(702370390),
U32Field(539276863),
U32Field(827490094),
U32Field(759903165),
U32Field(944078157),
U32Field(723078384),
U32Field(91769472),
U32Field(391302454),
U32Field(39287360),
U32Field(639600232),
U32Field(217522736),
U32Field(584984002),
U32Field(322041093),
U32Field(85462231),
U32Field(711142344),
U32Field(200096211),
U32Field(184334857),
U32Field(416779107),
U32Field(447528665),
U32Field(26250833),
U32Field(799523747),
U32Field(158368851),
U32Field(780392834),
U32Field(396681101),
U32Field(314228277),
U32Field(135442229),
U32Field(794802438),
U32Field(348961433),
U32Field(154615406),
U32Field(853896500),
U32Field(356848048),
U32Field(899334124),
U32Field(160908298),
U32Field(206590678),
U32Field(292246668),
U32Field(1043493545),
U32Field(261440552),
U32Field(301973829),
U32Field(155601735),
U32Field(137111361),
U32Field(118902000),
U32Field(156282728),
U32Field(698792987),
U32Field(252187521),
U32Field(93969007),
U32Field(160154657),
U32Field(995446599),
U32Field(869969978),
U32Field(512131487),
U32Field(790923771),
U32Field(409255142),
U32Field(781327719),
U32Field(557200518),
U32Field(508903573),
U32Field(190864313),
U32Field(571564676),
U32Field(159130662),
U32Field(344177759),
U32Field(598353453),
U32Field(182459341),
U32Field(342945473),
U32Field(605583831),
U32Field(64670895),
U32Field(804332849),
U32Field(360207481),
U32Field(873453398),
U32Field(366277946),
U32Field(219947386),
U32Field(514593220),
U32Field(738838437),
U32Field(145438986),
U32Field(362094129),
U32Field(1038757601),
U32Field(387832747),
U32Field(900027049),
U32Field(640734512),
U32Field(102042558),
U32Field(59293594),
U32Field(617825),
U32Field(233794117),
U32Field(145798482),
U32Field(461391160),
U32Field(127221861),
U32Field(934777105),
U32Field(104793359),
U32Field(472577411),
U32Field(133911138),
U32Field(58278448),
U32Field(313596672),
U32Field(462746157),
U32Field(91093079),
U32Field(838066202),
U32Field(161698275),
U32Field(979070997),
U32Field(647775850),
U32Field(878728585),
U32Field(255753862),
U32Field(742264816),
U32Field(479899520),
U32Field(1003167834),
U32Field(265744183),
U32Field(412281801),
U32Field(210717890),
U32Field(837264602),
U32Field(847870329),
U32Field(472915065),
U32Field(407650814),
U32Field(132649100),
U32Field(317319071),
U32Field(27454045),
U32Field(849079255),
U32Field(415000644),
U32Field(944696335),
U32Field(994988221),
U32Field(681057178),
U32Field(946537067),
U32Field(295683978),
U32Field(382841583),
U32Field(759702940),
U32Field(698263485),
U32Field(458630466),
U32Field(497113927),
U32Field(994558895),
U32Field(526421757),
U32Field(207806502),
U32Field(1028200174),
U32Field(68900228),
U32Field(421465606),
U32Field(609583952),
U32Field(397262407),
U32Field(212519131),
U32Field(312661275),
U32Field(26955199),
U32Field(468673233),
U32Field(598993921),
U32Field(1015750334),
U32Field(207711840),
U32Field(792586945),
U32Field(92938295),
U32Field(484608162),
U32Field(874828739),
];
const U32_FIELD_NINV_2: U32Field = U32Field(536877057);
const U32_FIELD_NINV_4: U32Field = U32Field(805315585);
const U32_FIELD_NINV_8: U32Field = U32Field(939534849);
const U32_FIELD_NINV_16: U32Field = U32Field(1006644481);
const U32_FIELD_NINV_32: U32Field = U32Field(1040199297);
const U32_FIELD_NINV_64: U32Field = U32Field(1056976705);
const U32_FIELD_NINV_128: U32Field = U32Field(1065365409);
const U32_FIELD_NINV_256: U32Field = U32Field(1069559761);
const U32_FIELD_NINV_512: U32Field = U32Field(1071656937);
const U32_FIELD_NINV_1024: U32Field = U32Field(1072705525);
impl FastFft for Polynomial<U32Field> {
type Field = U32Field;
fn fft_inplace(&mut self) {
U32Field::fft(&mut self.coefficients, &U32_FIELD_PSI_REV_1024);
}
fn merge_fft(a: &Self, b: &Self) -> Self {
Self {
coefficients: U32Field::merge_fft(
&a.coefficients,
&b.coefficients,
&U32_FIELD_PSI_REV_1024,
),
}
}
fn split_fft(&self) -> (Self, Self) {
let (a, b) = U32Field::split_fft(&self.coefficients, &U32_FIELD_PSI_REV_INV_1024);
(Self { coefficients: a }, Self { coefficients: b })
}
fn ifft_inplace(&mut self) {
let n = self.coefficients.len();
let ninv = match n {
2 => U32_FIELD_NINV_2,
4 => U32_FIELD_NINV_4,
8 => U32_FIELD_NINV_8,
16 => U32_FIELD_NINV_16,
32 => U32_FIELD_NINV_32,
64 => U32_FIELD_NINV_64,
128 => U32_FIELD_NINV_128,
256 => U32_FIELD_NINV_256,
512 => U32_FIELD_NINV_512,
1024 => U32_FIELD_NINV_1024,
_ => unreachable!(),
};
U32Field::ifft(&mut self.coefficients, &U32_FIELD_PSI_REV_INV_1024, ninv);
}
}
#[cfg(test)]
mod test {
use itertools::Itertools;
use num::One;
use crate::{
cyclotomic_fourier::CyclotomicFourier,
fast_fft::{
U32_FIELD_NINV_1024, U32_FIELD_NINV_128, U32_FIELD_NINV_16, U32_FIELD_NINV_2,
U32_FIELD_NINV_256, U32_FIELD_NINV_32, U32_FIELD_NINV_4, U32_FIELD_NINV_512,
U32_FIELD_NINV_64, U32_FIELD_NINV_8,
},
inverse::Inverse,
u32_field::U32Field,
};
use super::{U32_FIELD_PSI_REV_1024, U32_FIELD_PSI_REV_INV_1024};
#[test]
fn u32_field_bitreversed_powers_is_correct() {
let print_nicely = |v: &[U32Field]| {
format!(
"[{}]",
v.iter()
.map(|e| format!("U32Field({})", e.value()))
.join(", ")
)
};
let assert_or_print_nicely = |lhs: &[U32Field], rhs: Vec<U32Field>| {
assert_eq!(lhs.to_vec(), rhs, "Should be: {}", print_nicely(&rhs));
};
for logn in 1..=10 {
assert_or_print_nicely(
&U32_FIELD_PSI_REV_1024[0..(1 << logn)],
U32Field::bitreversed_powers(1 << logn),
);
assert_or_print_nicely(
&U32_FIELD_PSI_REV_INV_1024[0..(1 << logn)],
U32Field::bitreversed_powers_inverse(1 << logn),
);
}
}
#[test]
fn u32_field_ninv_is_correct() {
let mut powers_of_two_inverse = vec![];
let two_inverse = U32Field::new(2).inverse_or_zero();
let mut acc = two_inverse;
for _ in 0..10 {
powers_of_two_inverse.push(acc);
acc *= two_inverse;
}
assert_eq!(
powers_of_two_inverse,
vec![
U32_FIELD_NINV_2,
U32_FIELD_NINV_4,
U32_FIELD_NINV_8,
U32_FIELD_NINV_16,
U32_FIELD_NINV_32,
U32_FIELD_NINV_64,
U32_FIELD_NINV_128,
U32_FIELD_NINV_256,
U32_FIELD_NINV_512,
U32_FIELD_NINV_1024,
]
);
assert_eq!(
U32Field(2) * U32_FIELD_NINV_2,
U32Field::one(),
"2 inv is wrong"
);
assert_eq!(
U32Field(4) * U32_FIELD_NINV_4,
U32Field::one(),
"4 inv is wrong"
);
assert_eq!(
U32Field(8) * U32_FIELD_NINV_8,
U32Field::one(),
"8 inv is wrong; should be: {}",
U32Field(8).inverse_or_zero()
);
assert_eq!(
U32Field(16) * U32_FIELD_NINV_16,
U32Field::one(),
"16 inv is wrong; should be: {}",
U32Field(16).inverse_or_zero()
);
assert_eq!(
U32Field(32) * U32_FIELD_NINV_32,
U32Field::one(),
"32 inv is wrong; should be: {}",
U32Field(32).inverse_or_zero()
);
assert_eq!(
U32Field(64) * U32_FIELD_NINV_64,
U32Field::one(),
"64 inv is wrong; should be: {}",
U32Field(64).inverse_or_zero()
);
assert_eq!(
U32Field(128) * U32_FIELD_NINV_128,
U32Field::one(),
"128 inv is wrong; should be: {}",
U32Field(128).inverse_or_zero()
);
assert_eq!(
U32Field(256) * U32_FIELD_NINV_256,
U32Field::one(),
"256 inv is wrong; should be: {}",
U32Field(256).inverse_or_zero()
);
assert_eq!(
U32Field(512) * U32_FIELD_NINV_512,
U32Field::one(),
"512 inv is wrong; should be: {}",
U32Field(512).inverse_or_zero()
);
assert_eq!(
U32Field(1024) * U32_FIELD_NINV_1024,
U32Field::one(),
"1024 inv is wrong; should be: {}",
U32Field(1024).inverse_or_zero()
);
}
}