net.i2p.crypto.eddsa.math.ed25519
Class Ed25519FieldElement

java.lang.Object
  extended by net.i2p.crypto.eddsa.math.FieldElement
      extended by 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]...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 Summary
(package private)  int[] t
          Variable is package private for encoding.
 
Fields inherited from class net.i2p.crypto.eddsa.math.FieldElement
f
 
Constructor Summary
Ed25519FieldElement(Field f, int[] t)
          Creates a field element.
 
Method Summary
 FieldElement add(FieldElement val)
          h = f + g
 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

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:

Postconditions:


subtract

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

Can overlap h with f or g.

TODO-CR BR: See above.

Preconditions:

Postconditions:


negate

public FieldElement negate()
h = -f

TODO-CR BR: see above.

Preconditions:

Postconditions:


multiply

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

Can overlap h with f or g.

Preconditions:

Postconditions:

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:

Postconditions:

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:

Postconditions:

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

hashCode

public int hashCode()
Overrides:
hashCode in class Object

equals

public boolean equals(Object obj)
Overrides:
equals in class Object

toString

public String toString()
Overrides:
toString in class Object