eprint.iacr.orgpaper

safeRNSgcd: Accelerating Falcon key generation with RNS in SafeGCD

ePrint paper presenting safeRNSgcd, which computes the single Bézout coefficient needed at the deepest level of Falcon's NTRU solver while keeping large integers in a residue number system. Centered explicit CRT recovers the exact low bits needed by SafeGCD batches using single-word fixed-point arithmetic. A C implementation integrated into ntrugen reduces inversion and private-key basis-generation cost on a Raspberry Pi 5 and two x86-64 CPUs, versus the original ntrugen and a variant that skips the unused coefficient.