Low latency data-flow graphs for simultaneous modular inversion of many inputs
arXiv:2607.11337
The paper designs a highly parallel data‑flow graph that schedules the auxiliary multiplications of Montgomery's trick, achieving simultaneous modular inversion of many inputs with a critical‑path latency of ⌈log₂N⌉ multiplication layers plus one inversion.
Abstract
Montgomery's trick accelerates simultaneous modular inversion of inputs by amortizing a single shared inversion, but auxiliary multiplications for complement products are typically scheduled in a linear, serial form. We construct a maximally parallelizable data-flow graph (DFG) that computes all complement~products by scheduling auxiliary multiplications into idle multiplier slots during accumulation of the product of all inputs, and that of the shared inversion. This scheduling ensures the post-inversion phase adds exactly one multiplication layer of latency regardless of , yielding a critical path latency of multiply layers, one inversion, and one final parallel multiply layer.