Patent ID: 6901513

Claim:
A method for generating a digital signature (“s”) of a message (“m”), comprising the step of: determining a secret key as a function of a first large prime number (“p”) and a second large prime number (“q”); and generating the digital signature as a function of p and q, the digital signature being a zero value of a polynomial P(x)−m modulo n, wherein: n is a product of p and q, and P(x) is a permutation polynomial modulo n, the permutation polynomial being a Chebyshev polynomial represented as T(x) mod n, s=b·u·p+a·v·q mod n, u·p+v·q =1, and a, b, u and v are value which are calculated with an extended Euclidean algorithm using the equations: ggT ( P ( x )− m, X p −x ) mod p=x−a , and ggT ( P ( x )− m, X q −x ) mod q=x−b.