Robert Dougherty-Bliss, Dartmouth College

Abstract

A popular approach to speed up computations is to reduce the input modulo several relatively prime numbers, do arithmetic on the residues, then reconstruct the result at the end. This improves the running time if the moduli (and their pairwise inverses) have "nice" binary shapes, but only a limited number of such moduli are known. I will discuss a new system of moduli related to a family of trinomials. This system has shown promising real-world performance, can produce arbitrarily many moduli, and its elements can be computed quickly. I will mention some theoretical limitations of the system based on roots of unity and graph colorings, and point out what remains to be discovered.

Joint work with Mits Kobayashi, Natalya Ter-Saakov, and Eugene Zima.

Presented Via Zoom: https://rutgers.zoom.us/j/91865817691

Password: 6564120420

For further information see: https://sites.math.rutgers.edu/~zeilberg/expmath/