Patent ID: 7236589

Claim:
A computing device for compressing curve-based cryptography information, the computing device comprising: a processor; a memory, coupled to the processor, the memory storing instructions that, when executed, cause the processor to perform acts comprising: calculating point information suitable for identifying at least one selected point on a Jacobian of a hyperelliptic curve having a genus greater than or equal to two; specifying at least one point on said Jacobian using a plurality of polynomials including a first polynomial a(x) and a second polynomial b(x) in Fq , wherein q is an odd prime and Fq denotes a finite field of q elements, wherein a degree of said second polynomial b(x) is less than a degree of said first polynomial a(x) and said first polynomial a(x) divides f(x)−b(x) 2 ; wherein said hyperelliptic curve is given by an equation y 2 =f(x) over Fq , where the degree of f(x) is selected from a group of degrees comprising 2g+1 and 2g+2, and f(x) has no repeated factors, and g is a positive integer equal to said genus of said hyperelliptic curve; factoring at least one of said plurality of polynomials to produce at least one factor; determining a sign for each said factor; and generating a compressed format, said compressed format indicating at least each said factor.