关于大数混合基表示的算法与问题

本文基于求解ｎ个简单同余方程组的思想给出了一个求解同余方程组的算法，算法将花费３ｎ次模运算及ｎ次求逆元运算，优于牛顿迭代法。对大数的混合基表示提出了扩张问题与压缩问题，并证明了扩张问题与其求解问题是线性等价的，而压缩问题的难度小于扩张问题。

On the Algorithm and Problems of Mixture Base Indication for Large Number

This paper presents one algorithm for solving the modulo equation system which is based on the solufion of n simple equation systems. 3n multipiler and 2n modulo and n operations for finding the reverse elenent are needed. This algorithm is much better than Newton method which needs (n-l) (n-2)/2 multiplier and n mokulo and (n-1 )/2 operations ,where n is the number of modulo equations. As for the mixture base inducation for large number, we present its expansion problem and redution problem and it is proved that the expansion problem and the solbing problem for on e and the equation system are linearly equivalent, but the difficulty of redution problem is less than that of expansion problem.