摘要 |
To implement an operation in Jacobian with improved computation complexity, the sum is computed of a divisor D<SUB>1</SUB>=g.c.d. (a<SUB>1</SUB>(x),y-b<SUB>1</SUB>(x)) and a divisor D<SUB>2</SUB>=g.c.d. (a<SUB>2</SUB>(x),y-b<SUB>2</SUB>(x)) on Jacobian of a hyperelliptic curve y<SUP>2</SUP>+y=f(x) defined over GF(2<SUP>n</SUP>) by: storing a<SUB>1</SUB>(x), a<SUB>2</SUB>(x), b<SUB>1</SUB>(x) and b<SUB>2</SUB>(x); and calculating q(x)=s<SUB>1</SUB>(b<SUB>1</SUB>(x)+b<SUB>2</SUB>(x)) mod a<SUB>2</SUB>(x) by using s<SUB>1</SUB>(x) in s<SUB>1</SUB>(x)a<SUB>1</SUB>(x)+s<SUB>2</SUB>(x)a<SUB>2</SUB>(x)=1 in case of GCD(a<SUB>1</SUB>(x),a<SUB>2</SUB>(x))=1 where GCD denotes a greatest common polynomial. Thus, a new function q(x) is provided so as to reduce the entire computational complexity and the hardware size. Moreover, in the case of D<SUB>1</SUB>=D<SUB>2</SUB>, a<SUB>1</SUB>(x) and b<SUB>1</SUB>(x) is stored; and q(x)=Q(b<SUB>1</SUB><SUP>2</SUP>(x)+f(x) mod a<SUB>1</SUB><SUP>2</SUP>(x), a<SUB>1</SUB>(x)) where Q(A,B) is a quotient of A/B is calculated.
|