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

Authors

DOI:

https://doi.org/10.7719/jpair.v31i1.566

Keywords:

Number Theory, cryptography, expository-developmental research, Philippines

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.

Metrics

Metrics Loading ...

Author Biography

Polemer M. Cuarto, Mindoro State College of Agriculture and Technology

Calapan City, Oriental Mindoro, Philippines

References

Adams, D.G. (2010). Distinct solutions of linear congruences. Acta Arithmetica, 141(2), 103-152. Retrieved from http://rmrj.usjr.edu.ph/index.php/RMRJ/article/view/13

Downloads

Published

2018-01-21

How to Cite

Cuarto, P. M. (2018). On Generalized Solutions of Linear Congruence ax = b (mod n) for Large Modulus n. JPAIR Multidisciplinary Research, 31(1), 93–110. https://doi.org/10.7719/jpair.v31i1.566

Issue

Section

Articles