Computational Algebra Seminar
We present some theoretic and heuristic estimates for the number of elliptic curves with low embedding which is essential for their applicability in pairing based cryptography. We also give estimates for the number of fields over which such curves may exist. The main ideas behind the proofs will be explained as well. Finally, we give a heuristic analysis of the so-called MNT algorithm and show that it produces a rather "thin" sequence of curves.
Marsaglia recently introduced a class of “xorshift” random number generators (RNGs) with periods 2n – 1 for n = 32,64, etc. We describe a generalisation of Marsaglia's xorshift generators in order to obtain fast and high-quality RNGs with extremely long periods.
RNGs based on primitive trinomials may be unsatisfactory because a trinomial has very small weight (number of nonzero terms). In contrast, our generators can be chosen so that their minimal polynomials have large weight. A search using Magma has found good generators for n a power of two up to 4096. These have been implemented in a free software package xorgens. Aspects of the search using Magma, and a connection with Fermat numbers, will be mentioned.