Apparatus and method to compute in jacobian of hyperelliptic curve defined over galois field of characteristic 2

Abstract

To implement an operation in Jacobian with improved computation complexity, the sum is computed of a divisor D=g.c.d. (a(x),y−b(x)) and a divisor D=g.c.d. (a(x),y−b(x)) on Jacobian of a hyperelliptic curve y+y=f(x) defined over GF(2) by: storing a(x), a(x), b(x) and b(x); and calculating q(x)=s(b(x)+b(x)) mod a(x) by using s(x) in s(x)a(x)+s(x)a(x)=1 in case of GCD(a(x),a(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=D, a(x) and b(x) is stored; and q(x)=Q(b(x)+f(x) mod a(x), a(x)) where Q(A,B) is a quotient of A/B is calculated.