Studies on hardware algorithms for high-performance arithmetic circuits

1.提出了一种计算三维计算机图形学中经常出现的三维向量欧几里得范数的硬件算法，并在此基础上设计并实现了大规模集成电路。提出了一种计算机图形学中立方体求根的硬件算法，并设计并实现了基于该算法的大规模集成电路。利用带操作数修饰符的乘法器，开发了一种生成累加、平方根、平方倒数、平方倒数等操作数幂的硬件算法。在输入信号从左到右到达的假设下，我们提出了一种硬件加法算法，该算法在理论上是最优的，在实践中也是非常有效的。我们开发了密码系统中所需的模数很大的模除法的硬件算法。它是基于Binay GCD算法的。我们开发了编码和密码系统所需的GF(2^m)上除法的硬件算法，并在此基础上设计并实现了LSI。基于费马定理，我们还给出了一种计算GF(2^m)上乘法求逆的快速算法。利用公钥密码体制中所需的射影坐标，提出了一种在GF(2^n)上椭圆曲线上的快速加法算法。证明了加法器树的位片的VLSI布局问题可以归结为其对应的p-q个DAG的最小割线性排列问题，并提出了p-q个DAG的最小割线性排列的两种算法。

1. We have developed a hardware algorithm for computing the Euclidean norm of a 3D vector which often appears in 3D computer graphics, and designed and implemented an LSI based on it.2. We have developed a hardware algorithm for cube rooting which appears in computer graphics, and designed and implemented an LSI based on it.3. We have developed a hardware algorithm for generating powers of an operand, such as recirocal, square root, reciprocal square root, reciprocal square, and so on, using a multiplier with operand modifier.4. We have developed a hardware algorithm for addition under the assumption of left-to-righ input arrival, which is optimal in theory and very efficient in practice.5. We have developed a hardware algorithms for modular division with very large modulus which is required in cryptosystems. It is based on the binay GCD algorithm.6. We have developed a hardware algorithms for division in GF (2^m) which is required in coding and cryptosystems, and designed and implemented an LSI based on it. We have also developed a fast algorithms for multiplicative inversion in GF (2^m) based Fermar's theorem.7. We have developed a fast addition algorithm on an elliptic curve over GF (2^n) using the projective coordinates which is required in public-key cryptosystems.8. We have shown that the VLSI layout problem of a bit slice of an adder tree can be treated as the minimum cut linear arrangement problem of its corresponding p-q dag, and proposed two algorithms for minimum cut linear arrangement of p-q dags.