Patent ID: 7593526

Claim:
A method for compressing a Rabin signature, s, for a user having a public key, n, comprising: configuring a processor to perform the steps of; compressing said Rabin signature using a continued fraction expansion of s/n, wherein said continued fraction expansion of s/n further comprises the steps of; computing principal convergents, u i /v i , for i equal to 1 to k, of a continued fraction expansion of s/n, where k is a largest integer for which principal convergents are defined, where U i and v i are principal convergents, and where a greatest common denominator (s, n) ≠1; establishing an index l, such that v l <√{square root over (n)}<v l+1 ; and generating a compressed Rabin signature (v l , m) for a message, m, using said continued fraction expansion of s/n.