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)=X?3-cX2+cp¿X-1⊂GF(p2)[X], for random c ⊂GF(p2), as an irreducibility problem for a third-degree polynomial of the form P(c,X)=X?3+(cp+c)X2+(cp+1+cp¿+c-3)X+c?2p+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+f1X+f0, and computing a discriminant Δ=f02+4f13/27⊂GF(p) by considering a polynomial of the form X2+f0X-(f1/3)3. If the discriminant Δ is not a quadratic residue in GF(p), a trace over GF(p) of r¿1?p-1 as s=2(f¿0?2+Δ/f¿0?2-Δ), wherein r¿1?=-f0/2+∑Δ/2, and a trace z over GF(p) of (r1?p-1)(p+1)/3¿ is computed. If the trace z is not 2, P(c,X) is irreducible over GF(p).