Fast integer multiplication using generalized Fermat primes | Zendy

Svyatoslav Covanov | Zendy; Emmanuel Thomé | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Fast integer multiplication using generalized Fermat primes

Author(s) -

Svyatoslav Covanov,

Emmanuel Thomé

Publication year - 2018

Publication title -

mathematics of computation

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.95

H-Index - 103

eISSN - 1088-6842

pISSN - 0025-5718

DOI - 10.1090/mcom/3367

Subject(s) - mathematics , modulo , fermat's last theorem , combinatorics , strassen algorithm , integer (computer science) , discrete mathematics , binary logarithm , prime (order theory) , multiplication algorithm , order (exchange) , multiplication (music) , fermat number , time complexity , arithmetic , matrix multiplication , binary number , physics , finance , quantum mechanics , computer science , economics , quantum , programming language

For almost 35 years, Schonhage-Strassen's algorithm has been the fastest algorithm known for multiplying integers, with a time complexity O(n · log n · log log n) for multiplying n-bit inputs. In 2007, Furer proved that there exists K > 1 and an algorithm performing this operation in O(n · log n · K log n). Recent work by Harvey, van der Hoeven, and Lecerf showed that this complexity estimate can be improved in order to get K = 8, and conjecturally K = 4. Using an alternative algorithm, which relies on arithmetic modulo generalized Fermat primes, we obtain conjecturally the same result K = 4 via a careful complexity analysis in the deterministic multitape Turing model.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research