Fast Base Conversion and Its Application
Fast Base Conversion (FBC) is a technique used to convert a number from one modulus space to another. For example, if we have 14 m o d 77 14 \mod 77 and want to convert it to x m o d 390 x \mod 390 , FBC is widely used. Mathematically, it can be represented as follows: Here, the above equation represents an integer x x in modulus q q , and FBC converts this integer into the modulus space t t . The modulus q q is the product of small coprime moduli (i.e., q = q 1 q 2 … q k q = q_1 q_2 \dots q_k ), and x x is an integer such that x ∈ [ 0 , q ) x \in [0, q) . We also note that q q and t t are coprime numbers. Here, we remark that it is not necessary for the above equation to produce the exact result for x x . Instead of x m o d t x \mod t , it will provide x ′ m o d t x' \mod t . Thus, the output of the above equation is as follows: FBC ( x , q , t ) = x + A q mod t , where A ∈ [ 0 , k − 1 ] A \in [0,...
.jpg)
