A New RNS Approach for Fast Point Multiplication on Elliptic Curves over F
Tao Wu · Frontiers in artificial intelligence and applications · 2018
Elliptic curve cryptography is an important public-key cryptography following RSA. Here a new RNS (residue number system) approach for fast elliptic curve point multiplication over prime fields is proposed. The approach applies the Montgomery ladder for parallel elliptic curve point doublings (EC-doub) and point additions (EC-add). Meanwhile, residue number system with a wide dynamic range is used to support continuous multiplications, after which only one RNS Montgomery algorithm is enough to bring down the temporary results to valid range. In other words, both tasks can be implemented as many multiplications and a last reduction to improve performance. Also, Barrett modular reductions over small multipliers or modular multiplications over generalized Mersenne numbers can be applied for modular reductions over RNS moduli. A first analysis shows that the computation time for elliptic curve point multiplication over Fp can be reduced to a great extent at the cost of extra multipliers.