## 3 Basic Computational Scheme for Montgomery Modular Multiplication  
Let \(A\) and \(B\) be the operands of a multiplication operation modulo a large number \(p\). The fundamental concept proposed by [PERSON] [24] consists of an additive transformation of the product \(C=AB\), allowing the division without remainder by a specially chosen auxiliary modulus \(S>p\).  
To achieve this, the following equation is established:  
\[C^{\prime}=C+\left|-Cp^{-1}\right|_{S}p. \tag{3}\]  
Given that \(S\) and \(p\) are coprime, i.e., \(\gcd(S,p)=1\), Equation (3) guarantees that the integer \(C^{\prime}\) is a multiple of the modulus \(S\) for any values of the operands \(A\) and \(B\).  
This property is at the core of [PERSON]'s approach to constructing an efficient modular multiplication scheme [24]. The modularity of Equation (3) follows from the equality:  
\[\left|C^{\prime}\right|_{S}=\left|C+\left|-Cp^{-1}\right|_{S}p\right|_{S}= \left|C-Cp^{-1}p\right|_{S}=0. \tag{4}\]  
Therefore, the number  
\[C^{\prime\prime}=\frac{C^{\prime}}{S}=\frac{C+\left|-Cp^{-1}\right|_{S}p}{S} \tag{5}\]  
is an integer.  
Let \(\left|x\right|\) denote the greatest integer less than or equal to \(x\). Following [PERSON]'s Division Lemma [29; 30], the number \(C^{\prime\prime}\) can be represented as  
\[C^{\prime\prime}=\left|C^{\prime\prime}\right|_{p}+\left|\frac{C^{\prime \prime}}{p}\right|p, \tag{6}\]  
Then, by reducing modulo \(p\), Equation (5) simplifies to  
\[\left|C^{\prime\prime}\right|_{p}=\left|\frac{C^{\prime}}{S}\right|_{p}= \left|\frac{C}{S}\right|_{p}=\left|\frac{AB}{S}\right|_{p}. \tag{7}\]  
Thus, taking into account (6) and (7), the integer number  
\[\widehat{C}=\left|ABS^{-1}\right|_{p}=C^{\prime\prime}-Qp \tag{8}\]  
represents the expected computed result. Here, the number  
\[Q=\left|\frac{C^{\prime\prime}}{p}\right| \tag{9}\]  
is a uniquely determined integer factor for given operands \(A\) and \(B\).  
For \(A,B\in\mathbb{Z}_{p}=\{0,1,\ldots,p-1\}\), according to Equation (3), the following inequality holds:  
\[C^{\prime}\leq(p-1)^{2}+(S-1)p<p^{2}+Sp.\]  
Since \(S>p\), Equation (5) implies the following estimation for the number \(C^{\prime\prime}\):  
\[C^{\prime\prime}<2p.\]  
Thus, according to (9), the integer factor \(Q\) can take on only two values: 0 or 1. Hence, to determine \(Q\), it is necessary to compare the integers \(C^{\prime\prime}\) and \(p\).  
Therefore, \(Q=\text{CMP}(C^{\prime\prime},p)\), where  
\[\text{CMP}(x,y)=\left\{\begin{array}{l}0,\text{if }x<y\\ 1,\text{if }x\geq y\end{array}\right., \tag{10}\]  
denotes the result of comparing two integers \(x\) and \(y\).  
Based on this, the main steps of Montgomery Modular Multiplication (MM) can be summarized as follows:  
\[\big{\langle}C=AB,\ X=|CY|_{S},\ C^{\prime}=C+Xp,\ C^{\prime\prime}=\frac{C^{ \prime}}{S},\ \widehat{C}=C^{\prime\prime}-Qp\big{\rangle}, \tag{11}\]  
where \(Y=|-p^{-1}|_{S}\) and \(Q\in\{0,1\}\).  
As seen from Equation (11), in MM implementing in a positional number system, the main complexity arises from the multiplication of large numbers such as \(AB\), \(CY\), and \(Xp\). That also holds for calculating the multiplicative inversion \(Y\). However, its determination complexity is not fundamentally significant as this constant is a long-term parameter obtained during preliminary calculations.  
In RNS arithmetic, all operations specified in (11) are modular. So, their performance is much simpler and faster than in conventional arithmetic. The inherent parallelism of RNS primarily determines the preference for using modular arithmetic for MM implementation.