net.i2p.crypto.eddsa.math.ed25519

## Class Ed25519FieldElement

- java.lang.Object
- - net.i2p.crypto.eddsa.math.FieldElement
  - - net.i2p.crypto.eddsa.math.ed25519.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] \dots t[9]$, represents the integer $t[0]+2^{26} t[1]+2^{51} t[2]+2^{77} t[3]+2^{102} t[4]+\dots+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 Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `(package private) int[]` | `t` Variable is package private for encoding.

    - ### Fields inherited from class net.i2p.crypto.eddsa.math.FieldElement

      `f`

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `Ed25519FieldElement(Field f, int[] t)` Creates a field element.

  - ### Method Summary

    All Methods Instance Methods Concrete Methods
    Modifier and Type | Method and Description
    --- | ---
    `FieldElement` | `add(FieldElement val)` $h = f + g$
    `FieldElement` | `cmov(FieldElement val, int b)` Constant-time conditional move.
    `boolean` | `equals(Object obj)`
    `int` | `hashCode()`
    `FieldElement` | `invert()` Invert this field element.
    `boolean` | `isNonZero()` Gets a value indicating whether or not the field element is non-zero.
    `FieldElement` | `multiply(FieldElement val)` $h = f * g$
    `FieldElement` | `negate()` $h = -f$
    `FieldElement` | `pow22523()` Gets this field element to the power of $(2^{252} - 3)$.
    `FieldElement` | `square()` $h = f * f$
    `FieldElement` | `squareAndDouble()` $h = 2 * f * f$
    `FieldElement` | `subtract(FieldElement val)` $h = f - g$
    `String` | `toString()`

    - ### Methods inherited from class net.i2p.crypto.eddsa.math.FieldElement

      `addOne, divide, isNegative, subtractOne, toByteArray`

    - ### Methods inherited from class java.lang.Object

      `clone, finalize, getClass, notify, notifyAll, wait, wait, wait`

- - ### 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

    - #### 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.

    - #### 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$.

    - #### equals

          public boolean equals(Object obj)

      Overrides:
        `equals` in class `Object`

    - #### hashCode

          public int hashCode()

      Overrides:
        `hashCode` in class `Object`

    - #### invert

          public FieldElement invert()

      Invert this field element.

      The inverse is found via Fermat's little theorem:
      $a^p \cong a \mod p$ and therefore $a^{(p-2)} \cong a^{-1} \mod p$

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

    - #### 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.

    - #### 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.

    - #### 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.

    - #### 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)$.

    - #### 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.

    - #### 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.

    - #### toString

          public String toString()

      Overrides:
        `toString` in class `Object`