DocumentCode :
3195406
Title :
High Performance Point-Multiplication for Conic Curves Cryptosystem Based on Standard NAF Algorithm and Chinese Remainder Theorem
Author :
Li, Yongnan ; Xiao, Limin ; Wang, Zifeng ; Tian, Hongyun
Author_Institution :
State Key Lab. of Software Dev. Environ., Beihang Univ., Beijing, China
fYear :
2011
fDate :
26-29 April 2011
Firstpage :
1
Lastpage :
8
Abstract :
This paper presents parallel point-multiplication on conic curves based on standard NAF algorithm and Chinese Remainder Theorem. All analysis of parallel methodologies should take advantage of the basic parallel algorithms of conic curves cryptosystem in our previous works. We employ standard NAF algorithm to parallel the point-multiplication over finite field Fp by adopting the pipeline technique to compute point-addition and point-double respectively. The expression of point-addition over ring Zn is deduced to declare that the parallel methodology over finite field Fp could be used over ring Zn. The operation of point-multiplication over ring Zn is paralleled by partitioning the operation into two different finite fields based on Chinese Remainder Theorem and then combining the two temporary parameters to get the final result. After that, a quantitative performance contrast is made between sequential algorithm and parallel algorithm to show our approaches allow speeding up the point-multiplication on conic curves and reduce the time complexity. Additionally, the parallel method of paralleling point-multiplication over ring Zn introduced in this paper is also more efficient than an old parallel algorithm we proposed before.
Keywords :
computational complexity; cryptography; parallel algorithms; Chinese remainder theorem; conic curves cryptosystem; finite field Fp; high performance parallel point-multiplication; parallel algorithms; pipeline technique; point-addition computation; point-double computation; standard NAF algorithm; time complexity reduction; Algorithm design and analysis; Complexity theory; Cryptography; Finite element methods; Galois fields; Runtime; Zinc;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Information Science and Applications (ICISA), 2011 International Conference on
Conference_Location :
Jeju Island
Print_ISBN :
978-1-4244-9222-0
Electronic_ISBN :
978-1-4244-9223-7
Type :
conf
DOI :
10.1109/ICISA.2011.5772434
Filename :
5772434
Link To Document :
بازگشت