The majority of currently established public-key cryptosystems, e.g., RSA, ECC, requires modular multiplication in finite fields as their core operation. As a result, the throughput rate of such cryptosystem depends upon the speed of modular multiplication and upon the number of performed modular multiplications. Montgomery algorithm is one method that allows efficient implementation of multiplication modulo large number, as required by the RSA cryptosystem. In the recent years, renewed interest has been payed to Residue Number Systems (RNS), due to their ability to enable parallel and fast modular arithmetic. Within RNS any integer is represented with a set of its residues with respect to a given base that comprises a set of relatively prime integers. In this way RNS distributes large dynamic range computations over small modular rings. Thus the computations are carried out independently in each of the small wordwidth RNS channels. Since the RNS is particularly suited for performing efficient long integer modular arithmetic, the Montgomery algorithm was adapted such that it can be utilized in conjunction with RNS. RNS Montgomery modular multiplication makes use of two representation bases B and B', and during the calculations requires two base extension operations. Such a base extension involve the calculation of the residue digits with respect to \(B'/B\), when the digits relative to \(B/B'\) are known, and dominates the RNS Montgomery modular multiplication computational complexity. This thesis evaluates existing base extensions methods and proposes a new improved approach, which makes use of the linear Diophantine equations theory. Assuming that \(B\) and \(B'\) are \(k\)-moduli sets, to derive the value of \(k\) new residues, our method requires \(k^2\) regular multiplications and \(k\) modular multiplications, while equivalent state-of-the-art methods require, depending on the extension sense, \(B\) to \(B'\) or \(B'\) to \(B\), \(k^2+k\) and \(k^2+2k\) modular multiplications, respectively. When utilized in the RSA context, our method provides a speedup of \(O(\mu)\) relative to the stateof-the art, where \(\mu\) is the ratio between the computation time required by a modular multiplication and by a regular one. To better asses the practical implications of the proposed method we implemented RSA based on state of the art and on the Diophantine theory and compared their performance. For the evaluations we assumed various RSA keysizes, \(e = 2^{16} + 1 = 65537\), different RNS moduli sets with varying cardinality (\(k\)=4, 5, and 6), bitlength and Hamming weight, and various messages to encrypt. Our experimental results indicate that for sets of 4, 5, and 6 moduli with bitlength of 512-bits, our method provides a speedup per Montgomery kernel of 1.93, 2.42, and 3.17, respectively.