Restricted Congruences in Computing

Congruences are ubiquitous in computer science, engineering, mathematics, and related areas. Developing techniques for finding (the number of) solutions of congruences is an important problem. But there are many scenarios in which we are interested in only a subset of the solutions; in other words, there are some restrictions. What do we know about these restricted congruences, their solutions, and applications? This book introduces the tools that are needed when working on restricted congruences and then systematically studies a variety of restricted congruences. Restricted Congruences in Computing defines several types of restricted congruence, obtains explicit formulae for the number of their solutions using a wide range of tools and techniques, and discusses their applications in cryptography, information security, information theory, coding theory, string theory, quantum field theory, parallel computing, artificial intelligence, computational biology, discrete mathematics, number theory, and more.This is the first book devoted to restricted congruences and their applications. It will be of interest to graduate students and researchers across computer science, electrical engineering, and mathematics.

Preface Dedication 1 Introduction1.1 Motivation1.2 Overview of the book2 The Restricted Congruences Toolbox 62.1 Ramanujan sums2.2 Some useful identities2.3 The discrete Fourier transform2.4 Universal hashing and its variants2.5 Multilinear Modular Hashing2.6 Fuchsian groups and Harvey's theorem2.7 Counting epimorphisms via homomorphisms2.8 Generating functions for graph enumeration2.9 Deletion correcting codes2.10 Weight enumerator of a code2.11 Gaussian integers, spectral graph theory, characters3 The GCD-Restricted Linear Congruences3.1 Introduction3.2 Linear congruences with3.3 An equivalent form of Theorem 3.2.43.4 Some problems4 Applications in Universal Hashing and Authentication with Secrecy4.1 Introduction4.2 Generalized Multilinear Modular Hashing4.3 GRDH4.4 Applications to authentication with secrecy4.5 Discussion5 Applications in String Theory and Quantum Field Theory5.1 Introduction5.2 Counting surface-kernel epimorphisms from Γ to Zn5.3 A problem6 Alldiff Congruences, Graph Theoretic Method, and Beyond6.1 Introduction6.2 Graph theoretic method6.3 Unweighted alldiff congruences6.4 More applications and connections6.5 A problem7 Alldiff Congruences Meet VT Codes7.1 Introduction7.2 Main results8 Binary Linear Congruence Code8.1 Introduction8.2 Weight enumerator of the Binary Linear Congruence Code8.3 Weight enumerators of the aforementioned codes9 Applications in Parallel Computing, AI, etc9.1 Application in parallel computing9.2 Application in artificial intelligence and computational biology9.3 Application in the Subset-Sum Problem10 Quadratic Congruences, Ramanujan Graphs, and the Golomb-Welch Conjecture10.1 Introduction10.2 Quadratic congruences10.3 Proof of the conjecture10.4 A problem Bibliography Index

Khodakhast Bibak is an Assistant Professor at the Department of Computer Science and Software Engineering at Miami University. He was a Postdoctoral Research Associate at the University of Illinois, Urbana-Champaign, and a Postdoctoral Research Fellow at the University of Victoria, where he also received his PhD (2017). Dr. Bibak previously studied at the University of Waterloo, where he was also a member of the Centre for Applied Cryptographic Research (CACR).