Algebraic Algorithm for Solving Linear Congruences: Its Application to Cryptography

Polemer  M. Cuarto,

Algebraic Algorithm for Solving Linear Congruences: Its Application to Cryptography

Abstract:

This study is an integration of two different fields: Number Theory and Computer Science. In this paper, an algebraic algorithm as an alternative method for finding solutions to problems on linear congruences was developed. The basic idea of the technique is to convert the given linear congruence into linear equations and solve them algebraically. The advantage of this algorithm is the simplicity of its computation since it uses algebraic concepts which are easy to understand. Some illustrative examples are given to show validity of this method for solving linear congruences. An application of developed algorithm on solving linear congruences to cryptography using RSA cryptosystem was also presented in this paper.