use itertools::Itertools;
use num::{BigInt, FromPrimitive, One, Zero};
use num_complex::Complex64;
use rand::{rngs::StdRng, RngCore, SeedableRng};
use crate::{
fast_fft::FastFft,
field::{Felt, Q},
polynomial::Polynomial,
samplerz::sampler_z,
};
/// Reduce the vector (F,G) relative to (f,g). This method follows the python
/// implementation [1]. Note that this algorithm can end up in an infinite loop. (It's one
/// of the things the author would like to fix.) When this happens, control returns an
/// error (hence the return type) and generates another keypair with fresh randomness.
///
/// Algorithm 7 in the spec [2, p.35]
///
/// [1]: https://github.com/tprest/falcon.py
///
/// [2]: https://falcon-sign.info/falcon.pdf
fn babai_reduce(
f: &Polynomial<BigInt>,
g: &Polynomial<BigInt>,
capital_f: &mut Polynomial<BigInt>,
capital_g: &mut Polynomial<BigInt>,
) -> Result<(), String> {
let bitsize = |bi: &BigInt| (bi.bits() + 7) & (u64::MAX ^ 7);
let n = f.coefficients.len();
let size = [
f.map(bitsize).fold(0, |a, &b| u64::max(a, b)),
g.map(bitsize).fold(0, |a, &b| u64::max(a, b)),
53,
]
.into_iter()
.max()
.unwrap();
let shift = (size as i64) - 53;
let f_adjusted = f
.map(|bi| Complex64::new(i64::try_from(bi >> shift).unwrap() as f64, 0.0))
.fft();
let g_adjusted = g
.map(|bi| Complex64::new(i64::try_from(bi >> shift).unwrap() as f64, 0.0))
.fft();
let f_star_adjusted = f_adjusted.map(|c| c.conj());
let g_star_adjusted = g_adjusted.map(|c| c.conj());
let denominator_fft =
f_adjusted.hadamard_mul(&f_star_adjusted) + g_adjusted.hadamard_mul(&g_star_adjusted);
let mut counter = 0;
loop {
let capital_size = [
capital_f.map(bitsize).fold(0, |a, &b| u64::max(a, b)),
capital_g.map(bitsize).fold(0, |a, &b| u64::max(a, b)),
53,
]
.into_iter()
.max()
.unwrap();
if capital_size < size {
break;
}
let capital_shift = (capital_size as i64) - 53;
let capital_f_adjusted = capital_f
.map(|bi| Complex64::new(i64::try_from(bi >> capital_shift).unwrap() as f64, 0.0))
.fft();
let capital_g_adjusted = capital_g
.map(|bi| Complex64::new(i64::try_from(bi >> capital_shift).unwrap() as f64, 0.0))
.fft();
let numerator = capital_f_adjusted.hadamard_mul(&f_star_adjusted)
+ capital_g_adjusted.hadamard_mul(&g_star_adjusted);
let quotient = numerator.hadamard_div(&denominator_fft).ifft();
let k = quotient.map(|f| Into::<BigInt>::into(f.re.round() as i64));
if k.is_zero() {
break;
}
let kf = (k.clone().karatsuba(f))
.reduce_by_cyclotomic(n)
.map(|bi| bi << (capital_size - size));
let kg = (k.clone().karatsuba(g))
.reduce_by_cyclotomic(n)
.map(|bi| bi << (capital_size - size));
*capital_f -= kf;
*capital_g -= kg;
counter += 1;
if counter > 1000 {
// If we get here, that means that (with high likelihood) we are in an
// infinite loop. We know it happens from time to time -- seldomly, but it
// does. It would be nice to fix that! But in order to fix it we need to be
// able to reproduce it, and for that we need test vectors. So print them
// and hope that one day they circle back to the implementor.
return Err(format!("Encountered infinite loop in babai_reduce of falcon-rust.\n\\
Please help the developer(s) fix it! You can do this by sending them the inputs to the function that caused the behavior:\n\\
f: {:?}\n\\
g: {:?}\n\\
capital_f: {:?}\n\\
capital_g: {:?}\n", f.coefficients, g.coefficients, capital_f.coefficients, capital_g.coefficients));
}
}
Ok(())
}
/// Extended Euclidean algorithm for computing the greatest common divisor (g) and
/// Bézout coefficients (u, v) for the relation
///
/// $$ u a + v b = g . $$
///
/// Implementation adapted from Wikipedia [1].
///
/// [1]: https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Pseudocode
fn xgcd(a: &BigInt, b: &BigInt) -> (BigInt, BigInt, BigInt) {
let (mut old_r, mut r) = (a.clone(), b.clone());
let (mut old_s, mut s) = (BigInt::one(), BigInt::zero());
let (mut old_t, mut t) = (BigInt::zero(), BigInt::one());
while r != BigInt::zero() {
let quotient = old_r.clone() / r.clone();
(old_r, r) = (r.clone(), old_r.clone() - quotient.clone() * r);
(old_s, s) = (s.clone(), old_s.clone() - quotient.clone() * s);
(old_t, t) = (t.clone(), old_t.clone() - quotient * t);
}
(old_r, old_s, old_t)
}
/// Solve the NTRU equation. Given f, g in ZZ[X], find F, G in ZZ[X].
/// such that
///
/// f G - g F = q mod (X^n + 1)
///
/// Algorithm 6 of the specification [1, p.35].
///
/// [1]: https://falcon-sign.info/falcon.pdf
fn ntru_solve(
f: &Polynomial<BigInt>,
g: &Polynomial<BigInt>,
) -> Option<(Polynomial<BigInt>, Polynomial<BigInt>)> {
let n = f.coefficients.len();
if n == 1 {
let (gcd, u, v) = xgcd(&f.coefficients[0], &g.coefficients[0]);
if gcd != BigInt::one() {
return None;
}
return Some((
(Polynomial::new(vec![-v * BigInt::from_u32(Q).unwrap()])),
Polynomial::new(vec![u * BigInt::from_u32(Q).unwrap()]),
));
}
let f_prime = f.field_norm();
let g_prime = g.field_norm();
let Some((capital_f_prime, capital_g_prime)) = ntru_solve(&f_prime, &g_prime) else {
return None;
};
let capital_f_prime_xsq = capital_f_prime.lift_next_cyclotomic();
let capital_g_prime_xsq = capital_g_prime.lift_next_cyclotomic();
let f_minx = f.galois_adjoint();
let g_minx = g.galois_adjoint();
let mut capital_f = (capital_f_prime_xsq.karatsuba(&g_minx)).reduce_by_cyclotomic(n);
let mut capital_g = (capital_g_prime_xsq.karatsuba(&f_minx)).reduce_by_cyclotomic(n);
match babai_reduce(f, g, &mut capital_f, &mut capital_g) {
Ok(_) => Some((capital_f, capital_g)),
Err(_e) => {
#[cfg(test)]
{
panic!("{}", _e);
}
#[cfg(not(test))]
{
None
}
}
}
}
/// Sample 4 small polynomials f, g, F, G such that f * G - g * F = q mod (X^n + 1).
/// Algorithm 5 (NTRUgen) of the documentation [1, p.34].
///
/// [1]: https://falcon-sign.info/falcon.pdf
pub(crate) fn ntru_gen(
n: usize,
seed: [u8; 32],
) -> (
Polynomial<i16>,
Polynomial<i16>,
Polynomial<i16>,
Polynomial<i16>,
) {
let mut rng: StdRng = SeedableRng::from_seed(seed);
loop {
let f = gen_poly(n, &mut rng);
let g = gen_poly(n, &mut rng);
let f_ntt = f.map(|&i| Felt::new(i)).fft();
if f_ntt.coefficients.iter().any(|e| e.is_zero()) {
continue;
}
let gamma = gram_schmidt_norm_squared(&f, &g);
if gamma > 1.3689f64 * (Q as f64) {
continue;
}
if let Some((capital_f, capital_g)) =
ntru_solve(&f.map(|&i| i.into()), &g.map(|&i| i.into()))
{
return (
f,
g,
capital_f.map(|i| i.try_into().unwrap()),
capital_g.map(|i| i.try_into().unwrap()),
);
}
}
}
/// Generate a polynomial of degree at most n-1 whose coefficients are
/// distributed according to a discrete Gaussian with mu = 0 and
/// sigma = 1.17 * sqrt(Q / (2n)).
fn gen_poly(n: usize, rng: &mut dyn RngCore) -> Polynomial<i16> {
let mu = 0.0;
let sigma_star = 1.43300980528773;
Polynomial {
coefficients: (0..4096)
.map(|_| sampler_z(mu, sigma_star, sigma_star - 0.001, rng))
.collect_vec()
.chunks(4096 / n)
.map(|ch| ch.iter().sum())
.collect_vec(),
}
}
/// Compute the Gram-Schmidt norm of B = [[g, -f], [G, -F]] from f and g.
/// Corresponds to line 9 in algorithm 5 of the spec [1, p.34]
///
/// [1]: https://falcon-sign.info/falcon.pdf
fn gram_schmidt_norm_squared(f: &Polynomial<i16>, g: &Polynomial<i16>) -> f64 {
let n = f.coefficients.len();
let norm_f_squared = f.l2_norm_squared();
let norm_g_squared = g.l2_norm_squared();
let gamma1 = norm_f_squared + norm_g_squared;
let f_fft = f.map(|i| Complex64::new(*i as f64, 0.0)).fft();
let g_fft = g.map(|i| Complex64::new(*i as f64, 0.0)).fft();
let f_adj_fft = f_fft.map(|c| c.conj());
let g_adj_fft = g_fft.map(|c| c.conj());
let ffgg_fft = f_fft.hadamard_mul(&f_adj_fft) + g_fft.hadamard_mul(&g_adj_fft);
let ffgg_fft_inverse = ffgg_fft.hadamard_inv();
let qf_over_ffgg_fft = f_adj_fft
.map(|c| c * (Q as f64))
.hadamard_mul(&ffgg_fft_inverse);
let qg_over_ffgg_fft = g_adj_fft
.map(|c| c * (Q as f64))
.hadamard_mul(&ffgg_fft_inverse);
let norm_f_over_ffgg_squared = qf_over_ffgg_fft
.coefficients
.iter()
.map(|c| (c * c.conj()).re)
.sum::<f64>()
/ (n as f64);
let norm_g_over_ffgg_squared = qg_over_ffgg_fft
.coefficients
.iter()
.map(|c| (c * c.conj()).re)
.sum::<f64>()
/ (n as f64);
let gamma2 = norm_f_over_ffgg_squared + norm_g_over_ffgg_squared;
f64::max(gamma1, gamma2)
}
#[cfg(test)]
mod test {
use std::str::FromStr;
use itertools::Itertools;
use num::{BigInt, FromPrimitive};
use rand::{thread_rng, Rng};
use crate::{
math::{gen_poly, gram_schmidt_norm_squared, ntru_gen, ntru_solve},
polynomial::Polynomial,
};
use super::babai_reduce;
#[test]
fn test_ntru_gen() {
let n = 512;
let mut rng = thread_rng();
let (f, g, capital_f, capital_g) = ntru_gen(n, rng.gen());
let f_times_capital_g = (f * capital_g).reduce_by_cyclotomic(n);
let g_times_capital_f = (g * capital_f).reduce_by_cyclotomic(n);
let difference = f_times_capital_g - g_times_capital_f;
assert_eq!(Polynomial::constant(12289), difference);
}
#[test]
fn test_gen_poly() {
let mut rng = thread_rng();
let n = 1024;
let mut sum_norms = 0.0;
let num_iterations = 100;
for _ in 0..num_iterations {
let f = gen_poly(n, &mut rng);
sum_norms += f.l2_norm();
}
let average = sum_norms / (num_iterations as f64);
assert!(90.0 < average);
assert!(average < 94.0);
}
#[test]
fn test_gs_norm() {
let n = 512;
let f = (0..n).map(|i| i % 5).collect_vec();
let g = (0..n).map(|i| (i % 7) - 4).collect_vec();
let norm_squared = gram_schmidt_norm_squared(&Polynomial::new(f), &Polynomial::new(g));
let difference = norm_squared - 5992556.183229722;
assert!(
difference * difference < 0.00001,
"norm squared was {} =/= 5992556.183229722",
norm_squared,
);
}
#[test]
fn test_ntru_solve() {
let n = 64;
let f_coefficients = (0..n).map(|i| ((i % 7) as i32) - 4).collect_vec();
let f = Polynomial::new(f_coefficients).map(|&i| i.into());
let g_coefficients = (0..n).map(|i| ((i % 5) as i32) - 3).collect_vec();
let g = Polynomial::new(g_coefficients).map(|&i| i.into());
let (capital_f, capital_g) = ntru_solve(&f, &g).unwrap();
let expected_capital_f: [i16; 64] = [
-221, -19, 133, 81, -488, -112, 189, -75, -112, -223, 143, 241, -249, 33, 47, -16, 32,
-145, 183, -57, -99, 104, -44, 78, -129, 26, 77, -88, 52, -36, 69, -66, -37, 80, -45,
32, -67, 93, -24, -79, 87, -49, 68, -116, 60, 108, -158, 68, -52, 87, -32, -116, 233,
-120, -111, 65, 119, 144, -307, -98, 295, -163, -194, -325,
];
let expected_capital_g: [i16; 64] = [
-861, 625, -531, 151, 80, 11, 132, 547, -308, 4, 184, -134, -74, -61, 215, -2, -188,
40, 104, -38, -59, 21, 51, -12, -101, 86, 12, -40, 0, -31, 86, -72, 7, 24, -32, 46,
-71, 53, 0, -21, 23, -49, 60, -16, -38, 30, 18, 3, -41, -42, 114, 2, -119, 80, -64, 95,
-37, -18, 238, -429, 87, 193, -3, -111,
];
assert_eq!(
expected_capital_f
.map(|i| BigInt::from_i16(i).unwrap())
.to_vec(),
capital_f.coefficients
);
assert_eq!(
expected_capital_g
.map(|i| BigInt::from_i16(i).unwrap())
.to_vec(),
capital_g.coefficients
);
let ntru = (f * capital_g - g * capital_f).reduce_by_cyclotomic(n);
assert_eq!(Polynomial::constant(12289.into()), ntru);
}
#[test]
fn test_stalling_babai_reduce() {
let f : Polynomial<BigInt> = Polynomial::new(vec![
BigInt::from_str("608952554397054557983876280254475782156978778966514236337232157903009112871321999683643497269694189442905906970303786045645797783553603819271234233389723961161399883913029875233697100089950361781984561312574797799746866190588557496146920").unwrap(),
BigInt::from_str("-321198091895342626623905018079452846563740549837372660468562894512341046154970222611540742593012146136893774207013217934448033084417751742329986039507508103824063527509404104910887557717069726121009664272991060311076488206587527713367969").unwrap(),
BigInt::from_str("-511852458099561624239961196282485646021269605948503734916463216271741105669020643689485962072068026680773633158378214687137638656952667582984049436841521038937832328482550655620883633594646529561294167120997868894250092097125289410469269").unwrap(),
BigInt::from_str("753499692151616415251662722445327731480539623323000605380895648603405371851338467508575040732846737683390835245839956333926493086479631700998116314658893765004936549965922012760065249547741180589285017455538048794978342726037447740353274").unwrap(),
BigInt::from_str("-183951725423062894154142247006228629686028553344272108728906669710737867431299866959261567846158043338962173741060227623640390657223232373297828195388077477002393007770978315191221057900275286132154955867517828152370806350497427231775784").unwrap(),
BigInt::from_str("-601002944822358753730908286404268611783579577362298145349220422219337518495823156994812530727209827139319904644420562078413537022624501170363278280532068568605266646229790495883366738116427379176196534468686595436737518807388742965393276").unwrap(),
BigInt::from_str("624238805077664493322115890964268570726973934215001879901044583238147554868339541992616428233500727841616571552309882882912193503023373275313004172069274706976281040733564722134422543928965613410098136046852457807013063428923886900325416").unwrap(),
BigInt::from_str("99247320941428668744094858367782360465579561977614882360836919110717822389271909915623399678999810331939700577612687349369204993498887095160873936787628703559789561872359568953256723455070178252408841389920850163746998930970690582316813").unwrap(),
] );
let g : Polynomial<BigInt> = Polynomial::new(vec![BigInt::from_str("-276748395986364908221094085589576475403380860729035685618554719249731859131042127274390301424851882058378070539404235907974793069695572633477961322056365258258614312832511203946728028995719601790538904487894924461813173730797217250818249982").unwrap(),
BigInt::from_str("86812596127498460519207154109787274799874383708114200980528940455100071427257285893913175247659497014884186080805798356767162662189621835520839194646265741830798779072646145965638756187598754792152809555119081509898641068179709957911369677").unwrap(),
BigInt::from_str("116354193347135036416083176315819941089583030678185384093353987930114617677847583589518228207710036313227903774513592022562863039840725428131307408866838133762498621270855327564276484292086769092056758574610298629140002234098489707575021867").unwrap(),
BigInt::from_str("-301807527485830260261344620490924956518725241514546231783820178240968597102415190293928299169893150661326842964193337260684088468944872626419776842954670641099171003070476911114184625914895635366259003019569137386041706705684810645763462742").unwrap(),
BigInt::from_str("441299161379624032332866662487752791916685084733535111485266772869967918640142735209019134432254486721439741343615198249730448067610849591335249866703346142573143583974028002224021261123474948313561150275893970137607100222815689139896755492").unwrap(),
BigInt::from_str("-513595683023472695273563978709461994092425319855638422141058717955228319050940927987007122010294647136937120546974596907309751767539707235746382781851494092323493370150359286202256873867086472582425432902385470952671810828641054498438294804").unwrap(),
BigInt::from_str("507707498023164261062090937388345987181212863525863034372974903786763499191338982755471619717822792036379197240942561142666158588559211642577155844311933842930176434464164432666289434811839369974005888248331254542016292048307196783213633199").unwrap(),
BigInt::from_str("-424541034576343804926544811528101218199324642128826281424964488598284815916882148212061156604886226511172215884154920113476057900609708969461302301719829549643270043850114557922078292518535617173173882627190400853927778419866400469640897429").unwrap(),
]);
let mut capital_f : Polynomial<BigInt> = Polynomial::new(vec![BigInt::from_str("-97342744417091948277714584678980786347602848582001232696524345330053898461890905857357345522647395659791576336845694789964269088697943709632494103896150736987754856526288094356135043891715189900121635577150577171090069901904263254875521245315624957844848330067137803380242041663554024842364726847685705570657587737754069873830392344722883838185861856446427166745578895270214744011866852187668634399033333451988880963585072356564797880689406987307640156667060527684509114385593018612483494846977442876341441944273782084465101544305758331261519583332902607660135697475945108048943510260664248615671261521617250026778238255092974321549535707819637475555019670302268006897334037979565876100193827454386193593685346312255337401796479452419197877142101504566717981325166522192756168315219265835427100299487530858064429038294757391177110208660077768189200749278140542062111429636064358919395097447394238420136195092771198853073739528903982988240008769562060567298067006792354872401507668213840301663945476355828676076101348728787027731015289571543503516089252201650204507663487520270900747978472974378427525903102649318505202161064519237006859806152025919985674367021457032169619736078294842549345017292617772475933642016372517247977090292975644484936372855790236039389976377765185897735098315436552073999607483933071419474062067463853536456018502551717098578382604494344063626706791507541341347487247867708099201162394005495917990982824707093353836073985815839390962805421392351458137584205998343007060837735754607584839334483144667130735751831675732263736304562698362103000094056319122933731205822012313010623458271394051212191085033411035440730373545146217479865997198791400437831778193860459516502960270705959988852657161734374152500367040188203072291162413933721047973451881316482230645091519465510001328221204793454622422350467067865130194751282550433054905097011999725696067680468793414211611597394914303831646028924353339697533205884028844101579382205693609648645085691508254038293561864328207767643154085188892009511864883404965252411892034469089299192482787687447903300463868960833041894121824084367351872912172685026256443424998425907314626905144270523502119073066867541925703998772990378281760150482586964383887893172193821027330990438751440849297600603971254412263352398712123032888149167481748357202785915857221768499097028754865069831312645072064132026802150074048326372013245265961126894713312744612852767551595332083618109485960584996854212853771237433546199787147105038322994240082113194596907377332647923923013106078408382535441821706989156149157879244081692025585515685036929313372440240193549740784254890140567535650731900603775908057768046185165661840469421173265812206192326715324961335990477471241601687984503782713417943708664170860307353021708347365930541057868814674955038655657187294680000415392282320921673561445790478111637816487201128034009802124787806543122290829714020004886681948602456883884331810036777197637129173011966379731265688206419148915337562116254731483269286934954561089519320420638066716990363773997578485016737952129851819034690928729075461879175601612691673152541358883546153670560669125838788495232337085711101151160397208791808765076700221211931294779777730263960135578429297516680746776083492672023603438079137531239673668747022696815693083255798284885057597351047083494819001890834737515050552537443111771857261485182291641281398677347510155101389687726666681268449079828201683600477862547960089731272684888577897702311102143550714608").unwrap(),
BigInt::from_str("-40199423429375026434844861150776825132708397471941903364250719848280546169166117958111017009175151167135469508778313485099735253746988614555786590975620248088232346032255396603818698791407356171329592015782016522793812508618161984917153810102300972936054262023589555344644461502298960465755330339301753863334069805947495472939309203329299885807544382465678599711307460582979914099982811319409019464275835851130444271066974448960933649796098545566395401966091225964101636679728947093535304842903618071677818990096753011219479402822807885922670100651676830633539641562788681575785085184488466094435249018361651025285790177762185206581251329529695490141642523158759393224281463607616751530369066377702086463134779273307005152385834610903775675258022731197412842053435160425541511593823330715410635615493928366057384279371642304514948231382156777014904879359162307741680642773603701437040864313806281995321605083744076110071915490331148945276719089083641908872803547770269145860479379769946701868177761406001749927952691059918639426860482433238887260846650962548730049237077207091946658991527692280043915937217585062228794891360760446206520531652284415950868117954886621995866560047853533992319994761046989818226445958196840865453202365857550219784459402462821039582408991491339421474620200554243268596369172787124471783816445001699869322474723523295474643859272430275065568834497817149253582264034458440158650024275060464891714820380583451412292336703943828142139846147472734036444887603898311491918552998321552961129513176983567870563820696754428047879331162763709888020132290242729685343257062253348359994172944021257361578933060346041870403365208921653519122992339248369042568324814644107431690184556965851809758033897188519770352266312145484794588114117492275941267018473387891864568446708532533939153494280453316934655582178774552892782696683647219992682372679884375191951725297121552715778836596259952271239013765468225503702857720910030791704341210175154649870139932295712822259453268337612007768642331379540377429301626068551619091838696233935694440616663333969592995234005408856402030268774111311054221621206869469819084547434315713570201373321860455180298308686104445906669578923745475111787696133407367846669659776417716369238436856397798463665857708021677619587503918223326278366133835060908049491931494148134136206280775349517094131632148882444878857752093577677840553991393757255010916804751002148847265848603442085000279575294445536411175031965294404920405810810385464494938484898923746399812965718602409254227583454806056421900854353304141437044134489534168624971717278698486022538592087484084213875097363874481924689371350310923800410448063791315058169774653891020232949583406535994806918719303855873715917495572486371828035218353212623405946162884229511067720276291392442580632126915389600748286630377230539928176951037681981216911716279761190396683774126451934035680528588715886786691332565394312800154847212692687897609019110267613258152666046552294439205268289479776181166366213745644470858323461983304370009064232095992284964020480794039597662678078593522548889541753455575970587878832444555502322469328408156815103105435559876477012158451480253124667051810550075753709027819128298567508604365668768218884070792730578870958060020865129811628192423129510671810012796863333773303827340154481430178470030734526187102075826446553595281410037896163317291422088736710507398696911194435746504050742960606866560145839069915552558081388925997812824945124363582900528796").unwrap(),
BigInt::from_str("23063894192859591173030835913873782486164361699836036563852352800904352214397244642449406941844833955453088146133969028899491573888771404667829410533968057458986302277840054127644309065093153629136866995983617702649682422536220209833284628212041883289242737650074790038163958655782891383765579048762016695048175830659443175703907602717296808669093247287824826703186293786566236927614533458440662604916994162544507850417211506838215396669298763544030593137467624291704183954573330426106628947107215847536539055115455437031168600481887588878137723813822961857343945902798309577408308409376911354703533548368865076755124644243070915347903854647092366943251173142886048587420335600323692198378079624068441218676722589469958222644559900555331556141266416289586239514163236014064582292151198297679629943210642907164554434936406704592665657249953837549508317537401569684044816621909572953969591884017355648119185606383787266158261461395720332072889242890611339752996782965227159833164750535968584248400584151623710915436054877286596982194382854444299762625019662802564599907099118023006838457663621657820335804271818703149830084934745918411934941907348010299193223828181977532597471269968460875691279585628010869614079030676302139541324243371905216233688275573425607082958432402500448466076296274598080371236924598034066604518351908180644873458231640103040865529911997961398881105674354434047869986145587512145741533137910526639528155279993413571441914876524582759664215279275364639385564377049902001122280809809358394261493669116771402266727817983300368955649981421824707262708866774813800927652072330147301152669701938555414906054913315751151066223395431595760680614879151131953733108435265446067707797467337661698589617084410957374951248239605676490890877178340397301260397326504645385287008053951205864383904414574729835729440019467929025494101386006227670381845533411297310207152996191236223109558515001850499450049427966882147830838829580971740268898957062389401141070711329500314214861712465048667616464176963786778618207238659950074857484851194218988055415210091191364776171732456297616045584248314825380521083038133570218852423732245146582946364053858192184869507939163740534742990365563810662846579157962433626712748338932771850732248710673052768931351562677967520449310517876740835385916982391519374343121848112693365193853066122346896968171696311685195592309912573197061514780894425161074249436542895843176006436614304052124141230870036296073241706232253572599189350478916786287583184801807676170625367317695552376436321228407099658312951605123892140091969829104597460929357087498783344596851375823989596649212886288274416051085869022071626755791458701218955261229387820858894479502466834634757278629005218799822616695871021729280465046245445802265549409440197956265308417584483779998097300706486045396835911192235992938461047479065758908243609143953349066093839674857683356988127553638589370490637101085132575936927219244446403074067109978947589235920721881162527387106991190762475138396968554404665117514231954387031051353381638321864113069020148411767989579802124954103045098175890233490311197167687684755104533055330281250230237216482919974114037780933592076307955624901929983083710851599667771011031265286819513332016006290315397734474968044946301491882628437620892012813859211678585260984315208702548378992041235818814968204642191558732426499304704854813907797574961688617722695100276023766096388513790347413858267472533940058171955610336424646782276723254586570447208").unwrap(),
BigInt::from_str("82815943283266288721606087193975283987940740937438952778835382312767930042874638313350527346912444241126774234786291648146343862022529767795106555516971118710199001491236288946574166947109422940513175508363623204961455912283221036353409348667988864796952708769611037738714480879623768724793885092519328242966714657341083172269602470615169396974943054322116684460143610979367903861798830981742543316478077058252686060004485560516565657801909302687298252787063690129161318147468937655070594529788166559020093818257718957500577015228188889847361759159853186061269075273415855615431364030641334560480786871354836242426796209377447494788719299768111406967605804723241308486960656347443158526075092845678727420646260267609619717995172211336723249712132416073863407083988007791603937121351334481838776444338921000781249139620510104537219764853164090642530072553514517086285028511721197216956906277923750922427989972202115461710872404361958988634339705079769469191221660260376664320681165403537042472544717977874670286354892612107059920839752880333981247337250949226467817620021523728997775718246812634627693115450810586516737228766244318711421936391593321330315409510908880437503322254898191906327782353409631487268159755507442773207840764385578724296063332573061534475377956647178951485153597527330102533131347773078270646224423038192403619412669605229343381780501617858433517168987186036423436875043029260232944406501555403779724925105673738692159327988026814565803753165634345757516843782961431228203695823144650512165168574038171987079687122809424060905757404774952501849267792145645958654493366870533240746079508765793198119822852387387362665541001421842926648444078587865210049172794619757272945543889658321507769846279141231835358234287035598267418567575811749075007031096201884936747899130123416992099598396453644484407991063264110509459943196507906816053356373100655787143255036032942617507381315950239472678934126570731886323118346586064749570439870994086272015616418026701677223939198177953195468527774038806248149829264813312833877166465942542656943096181623547351471330298022813982539265677208925282736724512608895988485204262827558656206154703112195671994523380441968930456364084990832810637585126796610132777596868888125936477445869661091091417215049168675336581086782290237998011412349073503961531997022872318709141713781764830046070375011253962417951819008993837066044969752839361625406121643780943247058102292975259123331481844858624887960371220382563662709298452578463308632421001923938722855000498873848864415289498517868243879151292098503541020426612835514583629827129269299676888121021505149203965358819744210570968714464419943542523574708103432264285136708637940632482018474697111207320138637971422564248722964776282135683194498438713085566697174420071785799333749822576799757257509464953417392898952092061048176169137821838632455615550603173658036474577830025417702866884684819114135026595543482559656603890716133199938755935120373662369868822406922819952941319439716765567977644764416657145382259873821562475059052420511843784691672284391660470727396590790503734432467833217972748757122811380956628970243274937022902511855451979471787364547673906565999829341570488417895974974740278627497988478186895521796201064299126534316554770168777413277256571295997982002070361714634534680918891188157729342281936254433048068397233714110487401523135708272185671225743329140159638070677306450388684582460495547059014682189410752880982555292985685908666048247952352321419436").unwrap(),
BigInt::from_str("129960017263994841577803130018060127323391520569268206584664330259024493784137578699761135346920720747650961052435817136818605064863743818168054215287099273457302382431496390700791464697162018046377624203872220828112251819523049476537089349938220705905825224582917492902634814244939930604304980085442860491872004227046983722673061256229509910663626942912227586041620007761307481902052658045447981296728700350570132301495130700072393602531615152157637989193766132397458032356087454369477504724248657352413632931054079823577342336966863915409072448838961417766406843903246090505000244239218255479253214141914882145891226576154225310208959529777095309983436325365121352717878321623550961110765921541169001531466622990360645334351852796843986214179047115742057829297115931133452318846745818086981978067522240681138060659389103442170819599671342700918254093726076525397892610643599097464172479650467384412979133023874606230205400002879286871974024069049543194651279213126285354559093564471386753127728347728874639726887316640798575790414522553926803735375455521119449169225770467654038711632205392177931184561058211957075971258640053611431653934728810273724069202427237333929082932595592254670641580312223678918425512357022957462228302058186240509307061369722798068999381597288873789922739495498248436627382184596938790426041251575455346826259046597082940260036660554883416366738367700034028903793598267626464344348164661553083803652588842006633208299741155854010979754156693125279065294331057760897930759110403174913033671489851143625703785711739094879943682043738866464724479359280778843818547506731210381818324193926085290785990846071785502586162660022378245729320538004642101718210300547975520508869189774528086930446092447166871552097322731201728585467032778054628821968830165633814484456490345217652880485490442890528076518041061597000659791876929015232032860262364932447515052222552836896147957307906727339134887620731035814362222501475087123629210341035914730111359550516436143694127525666683329349571492134452560336450015220415659521665139357852440433562307966163046168978922323995586634235260919312146410184816217745114632631060196507544529439209581547571893206651734416361722499235806423525857469766526348355041610945857122084189768174541857249998468546328169181340219156133086449598529937538118491097454405537811478320029028402573659347081037035373985272310229717250375943518504517482736608927209749080909631307118242911197525232048182292615869733852784245326109450849801940833592576911796208475731012819746539526760980423329429610326861853479482405164892539689893697128721734451699260340366360294572568824557838510430374456336260332276512664869673648352919942666340843686795027763265374664288802856938797445195215642092679793751511518376834633997290212858269386997026306283023385261479968495350373871050975411655505876290572949107619627921434920811660751914072447371686801796188509141527669238695021260901817593990704925771542448806400190541530412859072090407214724468341387777287092817623594321341310057739075723141512255631085127180469482895771641184984150957542287577470947292180714811644190786654041673184516603462582715492334809407627254818089277514331452620823124261365687308271393301355584638923818607356356807027393304019042406438680580777432789996883951562077168319543938980636034744455305808983341535870224500902258875354396977756042727047749469177917812246592515448606772789931131381904184797280125883024296920099512948815744510822258517137699988822051003495272").unwrap(),
BigInt::from_str("157318857411811049942358978851785103736005792046407585858594324999860822018489888486734547061457315358247155658205156535226413839294230770381949835430002112741760699488552794234973193368326485770884744029284554868511973324669248251550757503281990221564610793194100852003352707013081317928532703447807410668178468097189789827849608112035937370672875275243971186910530678879150736406531535971011596617049053959208135122007631371539607413506755202083816718282579974910845135926867323187079757088793763564813242869661109478805699748518409564320123726958684348727365142071054494832063285106059329021111821303189589925760021297372257052343071982483012684722957014016689622160060781153208310802141684729974802725988988342634641713401829699610592790372908044608148455432623228411412239786889159986061871587146533240682182883676518473172381949434633933596835067988620275366112986912547292253916248195613442204653262722804581776208793674038204428362491736544969338457952823731520831129144795379532199324546403701161570323962148029242523225033473073522692677393471608056329540073901805557626169122620185702432220733776078461735565834900905535279781016355327579471238337360760650543268415013715685425519183718875509972736807648408086522924272942735811806893272581203266980848773942045467216015937710012126422807288787056040064145667008441087614139631266402305495207891588253122701386203730477886575225224164764534102702242100892178474178401414229330625918344405663340592217440497270797446598536815482175341364061667444237139447771306893788189710451174613936886219006288165329777927024934889628048898499582149619193286753594661045713496450899632241476034330039584160602757967324641491787936947775734615313765992572168972961137064866292606465821693931593950093884017744449112130521553493849566587684493372305652127255194246468380270033905737170240139352066666222979874910050849487125628537938507193351777047029552754535809632615176726576143325220940990225091947505970490200601723970770125987691089449174008474247081643825132516455773110304118975356845785866493639394369714487412375863686596757959258823298906324713468810330886602102409583631432653193959422730146098433214232939972604917545063005395851076267072021343399163774067419977165166899272804453432833119595164796554626201670778611205218587100052347431458709073828363812013509683548372235054182030735764115990879731470354223691533793986195523447733441955009134227654422708080943643283855524202933017201872575152056180037995990372616116431301629342671086597126650034032367357158311514404302401209188412705773887825066409325557479231305259526221955063494195367004619690543151864566917523658356582125570841223699740580031106478348813718415943429126163189919565599569442904038698052010073189072096438121191653710851614902141002695528783465592216914087127271354902386199156560900416567434166896783382514707075768120661602175826524648238997985093766174858817549638179804511648935105352138175495426277423345761868789931398243582368288857330703001630089086307187209608644203950454208895287545748767700937116345488177636753149289636168934636155938271456657709808357282489907649718636519155401443712154932563619147917812527287851072069421830264227219243473137137745032591132212523383376400464630709553347941589804274261765147655843345460475023406874278851727998354103597255141821957554172767796144619691251549952540608707002955089015885570380386529187684009501163512639571912739163958847537656670265255653146375115855344732608885202213543864925532").unwrap(),
BigInt::from_str("160727326826345673265933494622052646366281871082182011207978950454349983621713919490680797239917947780771646150986988413900897769303331870818162369811460475433808641155168164101460761450288800085366329802935994383257605710256975923810488599400346050855437632920300012267869300913970025298890470294449738310979263436603013147524992157222775646291490592773330403163567018383583000538304275710085425797260498586836071428260339601220030494860624140022374322197054335196942720266202078718473708128194762917309339151867901629436866997465348074713899889027798338933296089777551714965809038663685044426625622890428335206108044225771345738185973876011650306201833851248946849150860979497241090019717725677372372811511916083343251676939006360268797078970032233781647725474385351844745402845230533790336040533482374579088081542701117030278331292534922050953963304054046377112435817468455641192832086089846916401859263792783527900956134293062949656560280585706011410902942289020049217235722031557167668631346692405048218708066074570204067462546377138815191460128636927231108474939136727222642409523529949332579525277508743310487758597596798673522833317062459757410387713954229739694532179950094467422408240048278964454872297739433181597331850419271610763147172130203768939855471091227316488740920395030822902034332745122520132076489340502616531735689232411577716317283644937140618958799076517285087513856245224536342668004132508982743234806336805961294847256169687901027180192522786685328941600890434527198149817397893853226238561059367254512635170204919370869813476647712548508059275431631000956346817068822870198458950850718595789764286657516106060043731264566387015378644581104274000881570922812657036743836365615628210078167260056928473593289063351372285634610236296278842475148835425612028344981642892765207868339736634747473946728389557159585282998412037124926808408953056899451612920591173191220139887219506744120009346250472718357258320664596831653467928417981328115879930144243858142897255970598142848456631459329778560199588204438759702343895448524332146431156128166613463763201510714813197263529510964984854150064088221454370995749762551399552708792936776845984997511297380744975071330223560747441389307206544127566876137367550228760794153647249641637306304627212842299215844633692592549261768556593025492044983972474236196267163748323134834979184114286157412616718562523501309765658160841104884707164369214065568919724119207695602585749218051276677541900045541216702255712457387394121310078152155313053789483382984805628075990523343282679580639171037565333569393990721007937326671724033160215135982750382683992061084148896329873728967697961323302113277960360779749863820901468211248360193681504648430248195244684299877489488077813689014069256307450180098132812561342717883162757166250157325761337381612841480189792352117144673959623643326363640476591869065758278127265749091498218354910304822110738490815082541531964148951163852875383893376065826182217176401523933605713278684046958725759731777639079336087751638243960315872637465453478713573107275766475318290040216976678996985205561827302851576861947925405235142455245496149424949125526431590363262803858222467943818536741676795578719821649119701390613942969928500464626886044705261865440703733567422980465316862025774423326944572873651137817212254368279866674299541948824010118150710313929225789956752870880879103997596609122915151185685773493082120237330688480975934690950122384371214468993434777480379333928329930708828658040").unwrap(),
BigInt::from_str("139666516235023288211350018491681865223660616577095431445971152484805090227709511355527731874693054881128496655364769749307770309515844990573794143405139381693840678632201945948985533183937572450121871549805666934528004057139966486219265893620843918046639166875166497259940176562093555797611501983070018166047827677018417739557730136707351371031897827786572959417833125963087475917056269995939303439221755089613396743102665053178388913276481198818564760639045722481399129978336445274126456124963743251395836802657022642049858479782499747258394786870159907333584626791576685484102087102705449791310187459209736274126075681696787460390372577963799469729455239496294946878300115518275771042453542353419931214421232108343288976956375633245443484711817492513868866884205160318586710056572435551897990591098075170557998036706918030424754549453675656908929649299041404784777568142986219993337941660573772956023166231336191835675599087979834849088830250726985327254390100435935451457315979007061545840796177567515183013778053991492621194647666568242086410939793913271969764967175418295713489276793415071842076201984751674326468368093918950318948191458858080084961923280892391924085974134542460846709434740342814243047473303598975784631915255297395606304283195838651399772334619779001873411475435243706782567485343108617873693695716569738650118970538057705218536331697030081693344919243234925525385331390664626653997528502188131646089853796302887130728794127462884333293486060397375314061510212521557156009764054034786333004253081905763380739085900228196747064784100661898262775893499086778400245463993350070241633717811568441956268424914989444274393704192873000511125579423546272706847351354123100950773151058891512739771625434124870386445709485571116426901352466980232554480616927547858035791391893280200201021760182870529282964505030887242559237362652401949102288568356554830577293556245605050579235708611554683197158981732682985277472263386906592118467615795888920573350022624533324937468764991785842110638526949984319626372722770560944498997611332620670909377740891859318638547835818474021604238756054015598650513075163677563385360194305651619168467271821714827448846764477584770124583125884678038994369954884239642467754459962920323577858921965372419356583409344281842414494326970311105865958527470344409435212084991142628555545602720959639330632464043780719809702055478736494573247336709416559478593381304035501795477960787976701730003756239133038818597276328516042547896573192123699289305962196574541495629792666647509383661599613400826251754552013840796151037465806497934539238326234232661212864664308120231073692827141601610317063511602829412956485392343755162736584006469271014622922106835327098319574653404032384227870920686743811291905000530069323569788300744001418071152737435032806915031382406962902189268561319264073838913707782938231178031717944610815900574287231758022335433340511195328967010260938193497975170854870764894704570939323073113307161536334187592884539029100330128763930396825521979361798264670173491612906499960576097692833851912201345742816828484345284418540328409412856228959629358948837029490932312926664065141761935613595530356485628951625968950854116321141506549784004455168351744560449673667651273591536152691821550198588393307363885868994876513807738240426852909856042218829419743545501486813017912360254473631418498414506267868727927044551235164391826286921801984899801243650467215779739586182580619210627585638837167187417646755772284749687114923044").unwrap(),
]);
let mut capital_g : Polynomial<BigInt> = Polynomial::new(vec![BigInt::from_str("638708239932366711425188882448605599695932059889512809584527020036603771959331792003292637552839931599360703148456219559613343411460921520950241436164722495225868320954524607204338441976762485072295766235505921887200681246324080388009931693795331832702110062333676316878296360283279257058355719138909847747096791092810293141458755916539153881039045261921320710001169751106374000284255971432089482683327747247388495482144058065207406866775986174240703086664772482315293658553706378207190934203875550207408578489078410663016576426076397573484331019222754745451632385332250132454461027447104946227091252435986554164860178425358833094324473227639629480260505390171333481957258054356030217580462501177398166722499772740903311935669827107779891546011184596426728054754423879890928796819102045844247470280946061885404057394791079441008577476913195763617757563348655455439317666324833674462652313704189957682817698092791191452939014290791345406545956533556640438916607471535950421595840538595301548756859874720348935974392016223052859055826469967346247505614407462049621160079913083898577625454846522226081226259905628436054927267490239742569783094016971962157434338552385618193185818081300068100598240121601898464807729539609615424134952118743845352768167668589765718136270988531034718343381468107141090640169081358274470989879516172777189051811363439942317667762134030399644604969191148479019274770006936271875451319622203134494096594388538966227297573332763899524480602630220820763786475707421858697006918142649313194142961703608626113653613827439427298221994326515297572617100411200143180371885312911622495191290924986205704183674446966780236860578143813699424035682982902545721797415169313269076101687289760048613145874075380890474624733418633137124187947049972569269725648283403330254746342819824295168946983378145124288035528600144958740980746034935573221483491805559714476849518487781271394389644618009451746151264027704208906537995878422334668176271868833853315627987941738357068726141456727068088650575230043029697488898775340030704202691414530874550706414851659838037618269961334593641359158539503774940691478732853825678728393130426531736937746958199577536374615579208202770502444256567755637648462985678873869274259785254357319772239737130092042134973897538757033466599823333916999877467862127589360535185731906938909056730212681612264635450180454286157715984114175899613115849288227142173157597042854935501039927274019876878384248627803309218062233683245071631088627312226968120122019245603385469539245333348172099541807680513026470812746446471380858803450176868971613424252354243853792944368109744354297615538555573646510003799849724770422653356634120055980997192773671758359685033893387665464353498231183629480224704782234215746506732227390378485603640060399699554902203602965619998501873568213579227551635590103495858587446934298642209510703887141893904189668857899610007754771792138811684570100657421161556898377737821273899304447606372065752838583165396113784157551097776971185019012719291966116321186129320021265087811429003744914078057246944253416282322950315084442059474381557024635136852518045576044921848404917874572206682611155973712665061755081741584651431800522608594751800350463584585404515384775131945169689598298853868927440321580123278394842913962102802952598120728921745055082841269584404787196614471401262465291040473822280371715846424914434703438804146224980254245426518777179772555466424237615552397976636288950986958502105029239858466516410310179").unwrap(),
BigInt::from_str("357957442106052591755302684406728607618437781196580059495033146167705961351211718090673547738807632845671409478001748875470714263782671542453395869006723361103993874133624948498371241166877129629926248938972378724663704821249175615167884012987350540900916850767606147804182458328724271384688661961528126323036215754115690393116934381144717566248920146581161376762987454240082211508344171815911226167694693248440995173109257873157442808944800681113868110158550535760302755855574666947446268942745847453403324149684919987393810749302507773221647928036454905978977042119070054527205378155043537683340733853039832988828517173743081779588726677217383455497490248394815929699091937467642502037688894319419258291082314251551467451289843777783807389183956201963541047882356951898338525300414370130062485077540896390966566736655633397943684638449796084217350546004248995560277878952690834259602266145583329736045791215452932053774031225442595052741515383728458077815223133437177321401469394849185084031616684608304500983665597377702505754288499368923386083055608659865722662073426589535027338142830225381999195968801573281644215957144109519265793543934616601415232654968165109648029496402512493449486975077615184318486546680702779579848029747871780894907599307757330206541303599028331608981429758218315333223210899660299326543460118353628057529167865105283475340907140963949792212172678319931168333440727895415965474032910804023038208071469984394522205041000300350737228079640415288946599518174810257631463687172903822236967771381501594595570849421766226581628410575395519153141863021330118673355892630189659147635145848041716807323752927174056377974561697130571782638523022196397538033871345124673273544487729847435746628262166465035616528586258299552837434044578712986178521463590938959071665769388236101449679282341549790034614101041618075103292506476525328609272590287017266633459519010275731122696495978625971539478567240868333364444447258743061211562343509928922777905977320287119764360544846631592175122735542902697474560484317665227047955959987656578408148577467178058508355632373656476615430009284591690933440649316484785013226160782730077772346363894821401625047120839738104415464324626771291634052315710768430759085389199790177838489968838122031503744061023715573729093877211729422723733718711171533987992949621396671343036906627882085224308369284506945903723046882519399751178732343151681574428086776923262638875409493827116591223619294227889059079556514338435869239491080208855827324574251710045315284005517216720259715150841633445421660206650249032259462381772238234788166949614289592959509387399821219693823576111171007832711135268566863745313258423464937764239449032413740723774428803423362865766862231970799768906729805941912659693284580983103089941876373208070311170522793483028326514548599472992011315348341703218646956779056861252091598965128757969681547094399323655411785182160256204920463881824927462746700942141217060969769109209995781354742205733653519520752666978553219562335229673432184543005041848241135177600661034965364379117764691139963553198564240602996011344186835764579421734766127713181372906231857591547449215883381001133249837342079472887256324016563455973508323205789207502539096141744106991683578769699855100998640256422978939548980755412867330378512423190310618530188137101997394741478480890568433825234465125456091343864710262313379176415216287921505896848821549499656343895247373878812602604378271874838828047587604635293171716364535530763529").unwrap(),
BigInt::from_str("438966594880305812061951835079983359125571298624460297232882710573068046060576128889209771856682690173269213302744521384093809866628694950279506051184378492584058580354434416613397236404764452934765167152966474388990086773269415527306472917202332461331246902771773555667719321737334931232070739123457767996738716261737568564051248824236622195569275790514752558049435118328576177589139122644892136282373759843895776321675685188410523493356479464482004680110983115834961885574363776067457590212527509004790477246166539479030878634710652663566998538376545239583118991495701909370447563776979674443359950116857194515035118665134552622636637336923503908265432959544283408682786644943658286443531720727161773287970440806480422482894798936857110179278030221874209597135188716430761932041089377260407321508665222526929483432450686575218704193378772287628441015082169139739308526831190325825561488670125641179641327640960530368205591210431986729841409234893045929015820756420442465474324490735932691857821222934197760124445582736870618421714918501391343416798065526674697272968912583767016141437053911439302080199923339801334941438110874584218788533354731754981102073549494930057213871003255363235942922643233727539863340805151637801912196675173939370353208072760445909753699006537668645876186117808008412820960988846738833676262787589375037983820860431599997311426012790614225274185978598766105608842924218392159322060197474058768487336528655409930591337229770172214096215757414230277270946894910430712343396515145011543923289478720247370769064071175509416128768359902107157793602267671203453442649673162523102177468027546384030806319011999051846955087940037576783720175306686725409883857667378646139295677661883567308179248167816708079279928984463624339549816205119403573576090719275109140882265078549022955098576557301429846714296015465798529062040296570141656125511944343661928577867822813402484477636511526523306199262832344171075496584783575025004155480827380280098557438584899627556186836690821180922030503612257314467459442535296329568442060678226153147294641887886521644434038713412372468581198955398547307462927734705393709939379593886402189928911608705510184561364611674815794788821062953206936254368780970813691576393277745769654382026981974838403289458627134428014092070615325846597175637748114808510596232878788688251292035677973954500895598275934714193310503033303371499448759604601846558566922828523637352553674984832227896552947207624954159592765500230526353056169395831051020831559917168213775129672447534791490159240451640459173512113077308790976393853926542294558261607771989828151989356687760671347403948389645190560855782001680661327821146507009524232648907512478094820938937044934486301161459987129429552261787158650478670270529927663564216444402058774512158159712788658234193739436489634328517310356661126379736758010655080921724372280726677379206956267935217156202481653431647953853144349902438884807782204345070734979754035979732599136952433987615539639936042958668632952103886589400576176039006102487405308595657371027930174147172448096410229057954560497306580272635366973365910696178668636289477641036960488854926405223727012755341527996104911606756756556020428736181472599842739613358254964824040455306884052397670202305024775530608059263096003762417411423640277594826091454453091313505478936319483424221969958276938474179382525427581138562020437427982502937397842987732982808671938365724086003524082795239293915453124018838028365738815673340289083439454").unwrap(),
BigInt::from_str("-17913490430078572971550255173536329671834618912592071490717636664315169008729929305781269342550284640832934412569874333523260791344719747782379926489547489594575817831323584784272986240330194706393886171964014414363109484096940507730447564628407698446372537903582819632787715488515270222201581353461060517906835397520426857618418516414885589011476771616450578281396494495046185591863457456143701304160169390638953044823039522748172031339203334002079997600049335769085380195585402241953968546503898298852296284539355218059652613164827346022100654758467451435187792439737995599561929910946626374799600131667623117664281974580135215475771126823915274260797408596881467026012321601924885972112107552146597350653352338539280034126428824239605528525576684088079507790028045014976536399243540169338882320554847800743533900727521619034213639900128245967689129721796348233592318112995324751412566770896726719602531905915935137196179910858465231309054923523252919612518119213728916755502883749501451958794211305714467092211309261767303282748268060592712374356344386476128153421123475902011008653430121954857223142139565509614650510165214044456741903816804988548248391678431732224670165131221371280284893361150966010704562380203256104778339126090740172087536976994173978843982299113309931740831553519204272729604163333351611939861703112983998921648468673210303415589793639767594829777716654462229055762450779403293910903176958977536917020357307908715108672920077824819549183779164955938235508720742277356741316155562728055857005970665319797747077169363571558743540470395570661528799177357579344779179408350448841953702034481419220846059778552028455750750368298731341790634032164656299685499193516530513024094317627210341902449115043792203954765178857993166458669009426485114995671486169653001566644900150152422647875178131661038230442363284323127063387353859291425792074828572518570493022358116324855634502124934464887952951503907547131955359156703806309265810794853526654940604750592289234521551618886404720010352620767386471820907962824811847963429755229732559351238612218711160541318596345351033485975465808339242607019645982160294849862707940311465715576418965795364570686160102227563018600128689532457286221243869524888998886380709357634170715796655909225301091965556425031785473751689292042061504313138578464874735942970480139364820585594890470549914188298653562297008886783869097537376377424473946882039160581842521770174611320626415116324967726657212878500552805089902408210951224949351104012255550400268931170066612406797593237193600182813612351872724925921804187735278769494897588557540254671739653034022104063758479558907884792580439054809716294174185505896383471282436842288390059365677679994357388780666937918886200611299825064335524903335372930894170537366661513369484945563457258533321312033105366195017205796359050696579484240694520958260591681914616238354575304030361709940088121034475763682337033068288869006615230482235690303338841569387689207445606740242962953979680983162717319383909247196215234894054588625043871795966241765555529408408692744832374392562268712006534903699733572177338984344685686562208086320953703280520172149832100087822223099133623757719679615724209824894048860563137665427288101307870031310166638514581766212328494464241987927454925724297526353683894053045855406617925231818132187997187144131594024338988651191426164609599927787389301998976313932790232890241559433512950222303636513281937042332744040681115769690896358870623678035367114872245").unwrap(),
BigInt::from_str("112450568190774082130023493844664098515209968205629836716873566696068142926785237489087624404616463819926968966356619611440677243147431874931855555908759978413789033153905699485459058893888669534097025076320677988056121706014726730938243598133211269605811375047088088497528385994152343239496232667090588576686863640797318029750969163470286027094363809127852820468187907591394220225593925499242095427523015506538266141062120597718065364813458375184502582116988367873230539878027421393831292360006174574451998285968069169597498160776234976747110865463917748628211148920652955203652194292922826988978280913989590395791773995312082410833156335565264366322059962316739283082022318428210046104504995625740339861010359220383950106740838588669858886408143186190246425810674614395428807700397926577634790810841252195384739974227265004040332004717007007584262613649296211193504780118417689603084315987407954906239674385341779048634351821074882416987962498537804743357506191923546751842860398381072432370730357062258440689342001094686593463148933258112536939612729731271855830002530521122729425622459601978020415381598856019906111982711835296327970143670338414502365455027589714676700371801180326155935080200957406240996484745727261800966789525308168134318022442887371569115519627022474872317768901052549748124628020019648377938296433398195348164117871265757145353918920675193392687733855523884151276300732230302922812320604285703204757058504885469371514650597477241503092400929761232984348413547530856665384531740021134440352926429752989393005827093086193049289071358601966844386306891516444587139737051011866124943280010081436488239931650111980953222714794795335355454573014791652425693766275243578970341750617411191061749154796575407175948714104205531649414390996821411359248634762764300149959203268581064898926412374780067537106146924451610976508704385438588605959489349499705018431236161120264435082744857921375639800450369340214529704874353707624070101691149175718023447616010152859979351060468493571839721160217209648863876580295712216622922866284605321598929024514109420270649225862926516249158801430779928507065089978740640078041637004157345684783586104097482287528783402163751490536175341522757790471173596091432396867366625400358383610752106110468533404038697984355097404664703878168202659873231422399524384510884434416252644955401483067819272508153799654183869328121008475827637493913422539492053981691259407699157241223591983984501856342297141356509624863560547689564231309265484638607001315226835110636168663765528461257672726903142017546646610239567961814178106451571074904209798471677559819572608691964601539120943027430839498337956084301736575371053612451558536228430999544761988752602927288256415831040972684547051372499734407799766567667679599304423471590169602856767515556654816815196518328708499418286068214254704397353021712556930444147752568105585348737266247739140385387652436485837246315623378585875425214673156060818269967348035167554397208133491893555769604750157311980729785301727671924712069801064170301172164007360788919538138284466023058636706958360674959381632907636545179967967641733808586845290026106842101908154704234105434209084262497332421209580956197877712031388905001824602547042530843400865703177157924448255297562081975468336776717270759946923509644784731382530193302215378457146793896941425938025955011921129717593073433021933786152912134467729576526029875053663655131019188989841976243345185956677950356691049505118574220198289595304477731778").unwrap(),
BigInt::from_str("-198931678970070611264094888386680144000292585721266297795539724943360125923791646271487564454481577713986764179615266590005505358868130008076143280330530809600593282556715217648117345661712870397115053355020513708946852887875519472059279327466385216680695182760922122899079117860050440450662733437203435893319626338196629319243814093214207986660832833727633529455288570818748362117281397796638260938923706160060881099774964321084301784246483940290039638295789104206619267655171955284294489404759419708863365051666773466393292796409462108075339691288607253673823448579449752766772078785713766872988462017739097507892505832145907022582960361343938284748541750575718041227580181202330788375329394962414535261633099405412100779914803019690773333530732786784082931596292485824026325065011893736103249457734479995711936168269159191203809617828240164158257417030924237578267886164756042810621317678173741735715265209828664880585054742197249471567655347997855204399524563124793723855390113325316925950913098747111369506448674407717474440323993587845865089537232570213257301126181245321848358229330808750717960491214756199146701406466324996143333387469088239737090788756417159312796129674215075064002529708192317003051920911859192664281957566105301118482693635051612578766958705541817724210584575028019881674966765684441599595105063666357208682714895347386656170868090620976179648173377468027747871022256354435526224047123242029843192335199823851083999590158619687024604659016432414174984655811587289461317429583657346708907263235247242665513108560081264276209969981628802336818612836509955839527433733371585041782744845943836757064494544894645938065087882491936902541255028556569589072569890639433566971236711593934066242537110536310354937064543106469617114066176457279433913344177264769430213663127907189540465017110632491224778814206784773885413603958066608446649225566294989043971180164460752891889489340271889321088495861543925234207792760833195740118046140958499039902365503078868841495047882546754703516171734939715612072125438797106844304720927894850994862442099591620463606280842604591452243058047723119689620396453701482715939148915345012291849880682571142412794914747242396487032185858161769516408926009381067598978070476569935259335548569229137875834423025902002708187284331041540717368085962863173412396201786991860249175683488425313484130740831921138867620740068452041897647085770180538691235181138471366757725198595889857154225047798088085488378056258837899728588202669901860979337921165710061407625450207291062654783758698830811346660138508036001217141811224777875248395712183782256590595789232467768565976567875009595793612276271024789708603197079761933661880553434772814674665376932980978843671085247824559213654704309843600022575961510359376741792136168039133071314223282218602029911921893086341179651075772027624116691836760286540567079303547241066414276589349681470970846898731545273210386571659640502035501988627181931040755763406297201702121075452870373239187418228067098064272128154711601276097168414425469196250106545275662375269281542463747103910997824610706644230339084754947046257869373552532480567521403841202529659871788642806666514495557400286551074946890961784655438142246039835361677602169773318980050139513902767836051279244757243697561078132148330786566490811699946345949439653672187471062920711132485486994748199355501817481047429463851029198996169625156049288026606006702778142436369736281904478119027545291927486836318614706637091668362185618282").unwrap(),
BigInt::from_str("-464304901754039625155901972963401415991075690213387745367578442323958553270831602973660106216711579367880501808444172391636268021249592403846837899798265351001376084875628741496647734430672363496570619901347766601498772819572773308657480362843661741001626693443322711853735421336881902729795707897937125682563650018574673707617917744477462515892439325954056969321976073734460721630626205005637731435070982767922402039954609284591216222240052008300600743018778601347059171123191191332555147054651547849343444545559044655017175130100020964419157941094901179295588036198202849396998816575249919048910213744761081491387936814935089396315724729667663574551953040703900075110143858478167314625380023940531565892944407152983496811659625714209620132029148767164178806677226331220433688875388855933815914939151075166851178254704897373602399049941679058364476627828633100437332095314120822909101469019990999547805453743407955496772808282818503658617200892883848456110632942536921456692426361485337428946509407726612163144337936909030237131990168718682424829681417631252522171653069918454636051056202781190645874555415278216184641657090131336452027008427208332068008982380686117775146536481573954447160586077898540977112417222382865869586844700560477015396704936943840477842243863540079398212989364562814370661019101206551604517590832469974904682424370553967751286986877276987497837783437732579325735600184100509175928425561548010588710634541146663118840282355885665875979675412303254838625432556755065075192893088712058496751274564155149858191588195281775597980817576426473144225469982467785298672230009046980255471814529384986499609487469476846936009115911346728060405103027607906303988864591802710234953089303853421483209119206382397346324309779722374696597206514251800389525710464501563709346477113149098275348042633036474896527759426350325965376422625878578508136496818278605862810036975435006879488835785159427115010102347114354303385340080198160520944384608752234812720615309221701916777853258528090525962146760636407822408913684689854643169552406817690929996740940963461388977988371622438294003019404779576055559543378018148899425155910283837891383415246028284715182727887592052990625125841553588922401484974791958019208821922142402542627786582214320549041151306260981998548281458049665961725074718795626871038175182986434862235523007368207429113581473788781333345190037565372522900866784407406322008404246306423855055522559855064950789398252178867100706702624375120546869150855695781374069141689752897619970784466797029834136892815988370911618252180933157441877940867475784554117533571419964395506748021824472601418293756353490352329659648340216219987285727035972890989338425882956295271627624190356621745747863210734414785024321625070281801716347183062093717325071437290923147477305546999914592999648619855011819299931311105912824032413171789047139574079631139682270263333166063364394947865163467123501583313625992059945269698660570808712550165349378644408625019418926633309136794600483679502062093384273871870592094488691701522907587110289103619968232547287574554995619195260220919752203712962274577634724525489526113581554302047958329243357423742251920833221480383867499947926526884472867638517066572063525224726226586032195235337806021210093794104273605022292987288110882574295677128379285965311574469179006702193839742104104685907139917059633738687673032284053712208701144388257571197553966170743397245707073775581528110405108857971857916569728090608706891836566704375233").unwrap(),
BigInt::from_str("-393782769248744330715547506056841795904575235201972281078825887775054994830333286693764480737209760725659601785542885680429102013119208829396171022436781080452235488177109524593837722925712025282843580307132291475672053274107638901943019848327877432566010646757232518649619815648978529284127318971323145951266940420789386323070111229023999445446429197207548199480739768773999832545611888451260787930085167997486022254023651821662359848178785358020521474562150010575218174660986063317498065193845059308647269655066944500920649703408966506715330295333088829339085403085114771042760659598264187783709982871144631315722265435921933299525866220730475614832175460401413076703408419554493197960627212462628131037965859969174492415694274451570485269460437969124029643208800267404175257771126214888575962678256422837272441266629343589561513756466857000243984869035008050958771882997173875952188110659687954976551423601701789282468579910792896008067730059334088093287515852522958603563541367443100930919677122091153227560749598742453976310577039634708824755244542416066238977934883741347790734753742554369877718110512364172810075922956910334173822275001402227260108353265427976049893024315007027833182903463120267242035128855970762939622147757972468428632499552994995982575812708503520348469067792946083046622322269871541018576971052155506647423817557017182062286443979327614427617732184953962274878006827319683298102979478633891854701273115469119883874002644876942965243100499144434201263786097610195050863839920713647626036145178529393530817458909038778142010836762879969450227744127647790458291807936996336527241262999565490624019695661300434247395187625984237411489969398587300083205348615323900818343737712794070584840839088771117369483944610173282994391531194691934146301152603466029106549491127829075822447712672368563082951818983629744499599177258405384904896725089318063682691036899279918389464810056594831537669906039641742921416285123482089131722631769142098209443189748267352529003507030229385518903334534588592644788841857654843250356849409549635309889327766898652380436904201806692197510873007832377460749973213619697944481020409800286008575794132311901890597574673457579859026370532052102960134716511319056916621556595530403992621660070662572134740776789731337449818747551536040387813568240253963377273141938056357776324050523575641180152681955771911758829051380904169583998187328290620242153737676581620705447600135041149204477398730546130052798070621839137148857920388517953516356514187196328945815022007067881313642461594574534679233600219984486392996303082319926819255068576408842890863697479965253864363078584315553802246342180998341850284652612365084446956695415293408941522604673221639841845308296764524009683582241669567951425329501410690729081164163531646445116805306086278198619731135756944206439201557841553179114003670534197788264558397202658507057017427956817311338975039153596918348103328693171560909310473931749676495685427290253927310601010756689983230959102428713384658593341799778164039390611045732412156593246188213109205124814207799508527293872230114057490322264713450433894433051413114961400316210430168611251475313875204619182514980946047877853784855081232010341109846656809556450135890562938637533714153139918845342050243487240425285832686907937143202561280541082111341061680674892065271064845315065586653209792785388614987418798262518429931444250933025891473523971134157989250567514369727217584190945611862567451026192380278431223328710288361177").unwrap(),
]);
babai_reduce(&f, &g, &mut capital_f, &mut capital_g).unwrap();
}
}