Fast irreducibility and subgroup membership testing in XTR

We describe a new general method to perform part of the setup stage of the XTR system introduced at Crypto 2000 (see Lenstra, A.K. and Verheul, E.R., Proc. Crypto 2000, Lect. Notes in Comp. Science, vol.1880, p.1-19, 2000), namely finding the trace of a generator of the XTR group. Our method is substantially faster than the general method presented at Asiacrypt 2000 (see Lenstra and Verheul, Proc. Asiacrypt 2000, Lect. Notes in Comp. Science, vol.1976, p.220-33, 2000). As a side result, we obtain an efficient method to test subgroup membership when using XTR (ECSTR-efficient compact subgroup trace representation