Apparatus and method to compute in Jacobian of hyperelliptic curve defined over Galois field of characteristic 2

摘要

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.