Patent ID: 6721771
Filing Date: 2004-04-13
Classification: G06F

Abstract:
A method for use in a cryptographic system, the method of comprising:initializing a register A with a value a(t)=x(t), wherein x(t) is a first binary polynomial that represents a first element of a prime field of order 2m; initializing a register U with a value u(t)=y(t), wherein y(t) is a second binary polynomial that represents a second element of the prime field; initializing a register B with a value b(t)=prime(t), wherein prime(t) is an irreducible polynomial of order m and is of the prime field; initializing a register V with a value v(t)=0; iteratively reducing the contents of registers A and B to a value of one by applying a plurality of invariant operations to registers A, B, U, and V until register U contains a value equal to (y(t)/x(t)) mod prime(t) when the values in registers A and B equal one; and generating one or more security values based at least in part on register U's value, wherein the security values are used in the cryptographic system.