Back to search

University of Waterloo

Sparse and Scalable Modular Arithmetic

Abstract

dc:description.abstract

Modular arithmetic is a crucial concept in computer algebra and finds extensive use in applications such as cryptography, polynomial GCD computations, and linear system solving. This thesis investigates methods to enhance the efficiency of modular arithmetic by focusing on choosing sparse and scalable moduli. A contribution of this work is the exploration of a balanced binary representation, which provides the sparsest way to represent integers. Techniques that convert to and from RNS (Residue Number System) using special form moduli (e.g. Mersenne type, Fermat type, and ``trinomial'' type) are also studied, demonstrating significant speedups over conventional division methods. The thesis also explores different schemes to generate scalable moduli sets. One important result is the discovery of a close relation between the inverses of the moduli in sparse balanced binary form and the inverses under a polynomial setting. This relation allows for the generation of scalable moduli sets with Fermat type numbers. We test the proposed improvements on modular arithmetic on a two-layer modular arithmetic scheme that leverages scalable moduli to improve the efficiency of RNS (Residue Number System) conversion and modular inverses to show the effectiveness of modular arithmetic with sparse and scalable moduli. Benchmark results demonstrate significant computational advantages achieved through these methods, offering scalable solutions for large integer operations.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Chen, Benjamin
Advisors dc:contributor.advisor
  • Zima, Eugene
  • Labahn, George

Subjects

dc:subject × 1

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10012/21297

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Chen, Benjamin. Sparse and Scalable Modular Arithmetic. University of Waterloo, 2025. https://hdl.handle.net/10012/21297