On Generalized Solutions of Linear Congruence ax = b (mod n) for Large Modulus n

Abstract

Number Theory, a branch of Pure Mathematics, is crucial in cryptographic algorithms. Many cryptographic systems depend heavily on some topics of Number Theory. One of these topics is the linear congruence. In cryptography, the concept of linear congruence is used to directly underpin public key cryptosystems during the process of ciphering and deciphering codes. Thus, linear congruence plays a very important role in cryptography. This paper aims to develop an alternative method and generalized solutions for solving linear congruence axb (mod n). This study utilized expository-developmental research method. As a result, the alternative method considered two cases: (1) when (a,n) = 1 and  (2) when (a,n) > 1. The basic idea of the method is to convert the given congruence ax ≡ b (mod n) to ax b + kn for some k, reduce modulus n by interchanging a and n, simplify the new congruence and perform the process recursively until obtaining a congruence that is trivial to solve. The advantage of this method over the existing approaches is that it can solve congruence even for large modulus n with much more efficiency. Generalized solution of linear congruence axb (mod n) considering both cases was obtained in this study.