### Abstract

We give an O(N · log N ̇ 2^{O} (log* N )algorithm for multiplying two N-bit integers that improves the O(N · log N · log log N) algorithm by Schönhage-Strassen |10|. Both these algorithms use modular arithmetic. Recently, Fürer |2| gave an O(N · log N ̇ 2^{O} (log* N ) algorithm which however uses arithmetic over complex numbers as opposed to modular arithmetic. In this paper, we use multivariate polynomial multiplication along with ideas fron Fürer's algorithm to achieve this improvement in the modular setting. Our algorithm can also be viewed as a p-adic version of Fürer's algorithm. Thus, we show that the two seemingly different approaches to integer multiplication, modular and complex arithmetic, are similar.

Original language | English (US) |
---|---|

Title of host publication | STOC'08 |

Subtitle of host publication | Proceedings of the 2008 ACM Symposium on Theory of Computing |

Pages | 499-505 |

Number of pages | 7 |

State | Published - Dec 8 2008 |

Event | 40th Annual ACM Symposium on Theory of Computing, STOC 2008 - Victoria, BC, Canada Duration: May 17 2008 → May 20 2008 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Other

Other | 40th Annual ACM Symposium on Theory of Computing, STOC 2008 |
---|---|

Country | Canada |

City | Victoria, BC |

Period | 5/17/08 → 5/20/08 |

### Keywords

- Computational algebra
- Integer multiplication
- Modular arithmetic

### ASJC Scopus subject areas

- Software

## Fingerprint Dive into the research topics of 'Fast integer multiplication using modular arithmetic'. Together they form a unique fingerprint.

## Cite this

*STOC'08: Proceedings of the 2008 ACM Symposium on Theory of Computing*(pp. 499-505). (Proceedings of the Annual ACM Symposium on Theory of Computing).