{"ID":6537602,"CreatedAt":"2026-07-14T02:54:43.516908796Z","UpdatedAt":"2026-07-15T03:28:55.185153975Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.11337","arxiv_id":"2607.11337","title":"Low latency data-flow graphs for simultaneous modular inversion of many inputs","abstract":"Montgomery's trick accelerates simultaneous modular inversion of $N$ 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 $\\overline{x}$ 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 $N$, yielding a critical path latency of $\\lceil \\log_2 N \\rceil$ multiply layers, one inversion, and one final parallel multiply layer.","short_abstract":"Montgomery's trick accelerates simultaneous modular inversion of $N$ 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 $\\overline{x}$ comp...","url_abs":"https://arxiv.org/abs/2607.11337","url_pdf":"https://arxiv.org/pdf/2607.11337v1","authors":"[\"Tamas Visegrady\"]","published":"2026-07-13T09:55:22Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}