Parallel extended basic operations for conic curves cryptography over ring Zn

This paper presents parallel extended operations of point-addition and point-double for cryptosystem on conic curves over ring Zn. The data dependencies are deduced by analyzing the definitions of two extended operations. Take procedure of paralleling extended point-addition as an example. We employ the Chinese Remainder Theorem to divide point-addition over ring Zn into two point-additions over finite field Fp and finite field Fq. Then the temporary values of point-addition over two finite fields are merged to get the final result of extended point-addition over ring Zn. The analysis of parallel methodology is based on our previous works about the basic parallel algorithms used in conic curves cryptosystem. Computing extended point-addition and point-double both need to execute three steps. For getting the average runtime and speedup ratio, different cases are considered in the second step. The performance evaluation demonstrates that our techniques improve the efficiencies of two extended operations. Additionally, the parallel methods introduced in this paper are also more efficient than traditional parallel algorithms.