Class Ed25519FieldElement

  • All Implemented Interfaces:
    Serializable

    public class Ed25519FieldElement
    extends FieldElement
    Class to represent a field element of the finite field p=2^255-19 elements.

    An element t, entries t[0]...t[9], represents the integer t[0]+2^26 t[1]+2^51 t[2]+2^77 t[3]+2^102 t[4]+...+2^230 t[9]. Bounds on each t[i] vary depending on context.

    Reviewed/commented by Bloody Rookie (nemproject@gmx.de)

    See Also:
    Serialized Form
    • Field Detail

      • t

        final int[] t
        Variable is package private for encoding.
    • Constructor Detail

      • Ed25519FieldElement

        public Ed25519FieldElement​(Field f,
                                   int[] t)
        Creates a field element.
        Parameters:
        f - The underlying field, must be the finite field with p = 2^255 - 19 elements
        t - The 2^25.5 bit representation of the field element.
    • Method Detail

      • isNonZero

        public boolean isNonZero()
        Gets a value indicating whether or not the field element is non-zero.
        Specified by:
        isNonZero in class FieldElement
        Returns:
        1 if it is non-zero, 0 otherwise.
      • add

        public FieldElement add​(FieldElement val)
        h = f + g

        TODO-CR BR: h is allocated via new, probably not a good idea. Do we need the copying into temp variables if we do that?

        Preconditions:

        • |f| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
        • |g| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.

        Postconditions:

        • |h| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
        Specified by:
        add in class FieldElement
        Parameters:
        val - The field element to add.
        Returns:
        The field element this + val.
      • subtract

        public FieldElement subtract​(FieldElement val)
        h = f - g

        Can overlap h with f or g.

        TODO-CR BR: See above.

        Preconditions:

        • |f| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
        • |g| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.

        Postconditions:

        • |h| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
        Specified by:
        subtract in class FieldElement
        Parameters:
        val - The field element to subtract.
        Returns:
        The field element this - val.
      • negate

        public FieldElement negate()
        h = -f

        TODO-CR BR: see above.

        Preconditions:

        • |f| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.

        Postconditions:

        • |h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
        Specified by:
        negate in class FieldElement
        Returns:
        The field element (-1) * this.
      • multiply

        public FieldElement multiply​(FieldElement val)
        h = f * g

        Can overlap h with f or g.

        Preconditions:

        • |f| bounded by 1.65*2^26,1.65*2^25,1.65*2^26,1.65*2^25,etc.
        • |g| bounded by 1.65*2^26,1.65*2^25,1.65*2^26,1.65*2^25,etc.

        Postconditions:

        • |h| bounded by 1.01*2^25,1.01*2^24,1.01*2^25,1.01*2^24,etc.

        Notes on implementation strategy:

        Using schoolbook multiplication. Karatsuba would save a little in some cost models.

        Most multiplications by 2 and 19 are 32-bit precomputations; cheaper than 64-bit postcomputations.

        There is one remaining multiplication by 19 in the carry chain; one *19 precomputation can be merged into this, but the resulting data flow is considerably less clean.

        There are 12 carries below. 10 of them are 2-way parallelizable and vectorizable. Can get away with 11 carries, but then data flow is much deeper.

        With tighter constraints on inputs can squeeze carries into int32.

        Specified by:
        multiply in class FieldElement
        Parameters:
        val - The field element to multiply.
        Returns:
        The (reasonably reduced) field element this * val.
      • square

        public FieldElement square()
        h = f * f

        Can overlap h with f.

        Preconditions:

        • |f| bounded by 1.65*2^26,1.65*2^25,1.65*2^26,1.65*2^25,etc.

        Postconditions:

        • |h| bounded by 1.01*2^25,1.01*2^24,1.01*2^25,1.01*2^24,etc.

        See multiply(FieldElement) for discussion of implementation strategy.

        Specified by:
        square in class FieldElement
        Returns:
        The (reasonably reduced) square of this field element.
      • squareAndDouble

        public FieldElement squareAndDouble()
        h = 2 * f * f

        Can overlap h with f.

        Preconditions:

        • |f| bounded by 1.65*2^26,1.65*2^25,1.65*2^26,1.65*2^25,etc.

        Postconditions:

        • |h| bounded by 1.01*2^25,1.01*2^24,1.01*2^25,1.01*2^24,etc.

        See multiply(FieldElement) for discussion of implementation strategy.

        Specified by:
        squareAndDouble in class FieldElement
        Returns:
        The (reasonably reduced) square of this field element times 2.
      • invert

        public FieldElement invert()
        Invert this field element.

        The inverse is found via Fermat's little theorem:
        a^p congruent a mod p and therefore a^(p-2) congruent a^-1 mod p

        Specified by:
        invert in class FieldElement
        Returns:
        The inverse of this field element.
      • pow22523

        public FieldElement pow22523()
        Gets this field element to the power of (2^252 - 3). This is a helper function for calculating the square root.

        TODO-CR BR: I think it makes sense to have a sqrt function.

        Specified by:
        pow22523 in class FieldElement
        Returns:
        This field element to the power of (2^252 - 3).
      • cmov

        public FieldElement cmov​(FieldElement val,
                                 int b)
        Constant-time conditional move. Well, actually it is a conditional copy. Logic is inspired by the SUPERCOP implementation at: https://github.com/floodyberry/supercop/blob/master/crypto_sign/ed25519/ref10/fe_cmov.c
        Specified by:
        cmov in class FieldElement
        Parameters:
        val - the other field element.
        b - must be 0 or 1, otherwise results are undefined.
        Returns:
        a copy of this if b == 0, or a copy of val if b == 1.
        Since:
        0.9.36
      • hashCode

        public int hashCode()
        Overrides:
        hashCode in class Object