Fast irreducibility and subgroup membership testing in xtr

摘要

A method, system, and computer program product initializes a cryptosystem that implements XTR by reformulating an irreducibility test of a polynomial of the form F(c,X)=X3-cX2+cpX-1epsiGF(p2)[X], for random cepsiGF(p2), as an irreducibility problem for a third-degree polynomial of the form P(c,X)=X3+(cp+c)X2+(cp+1+cp+c-3)X+c2p+c2+2-2cp-2c, and testing the third-degree polynomial for irreducibility over GF(p). Testing the third-degree polynomial comprises eliminating the coefficient of X2 from P(c,X) to generate the polynomial P(c,X-(cp+c)/3)=X3+ƒ1X+ƒ0, and computing a discriminant DELTA=ƒ02+4ƒ13/27epsiGF(p) by considering a polynomial of the form X2+ƒ0X-(ƒ1/3)3. If the discriminant DELTA is not a quadratic residue in GF(p), a trace over GF(p) of r1p-1 as 1 $s=2\frac{f_0^2+\Delta }{f_0^2-\Delta },$ wherein r1=-ƒ0/2+{square root}{square root over (DELTA)}/2, and atrace z over GF(p) of (r1p-1)(p+1)/3 is computed. If the trace z is not 2, P(c,X) is irreducible over GF(p).