public class Ed25519FieldElement extends FieldElement
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)
f| Constructor and Description |
|---|
Ed25519FieldElement(Field f,
int[] t)
Creates a field element.
|
| 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() |
addOne, divide, isNegative, subtractOne, toByteArraypublic Ed25519FieldElement(Field f, int[] t)
f - The underlying field, must be the finite field with $p = 2^{255} - 19$ elementst - The $2^{25.5}$ bit representation of the field element.public boolean isNonZero()
isNonZero in class FieldElementpublic FieldElement add(FieldElement val)
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:
add in class FieldElementval - The field element to add.public FieldElement subtract(FieldElement val)
Can overlap $h$ with $f$ or $g$.
TODO-CR BR: See above.
Preconditions:
Postconditions:
subtract in class FieldElementval - The field element to subtract.public FieldElement negate()
TODO-CR BR: see above.
Preconditions:
Postconditions:
negate in class FieldElementpublic FieldElement multiply(FieldElement val)
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.
multiply in class FieldElementval - The field element to multiply.public FieldElement square()
Can overlap $h$ with $f$.
Preconditions:
Postconditions:
See multiply(FieldElement) for discussion
of implementation strategy.
square in class FieldElementpublic FieldElement squareAndDouble()
Can overlap $h$ with $f$.
Preconditions:
Postconditions:
See multiply(FieldElement) for discussion
of implementation strategy.
squareAndDouble in class FieldElementpublic FieldElement invert()
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$
invert in class FieldElementpublic FieldElement pow22523()
TODO-CR BR: I think it makes sense to have a sqrt function.
pow22523 in class FieldElementpublic FieldElement cmov(FieldElement val, int b)
cmov in class FieldElementval - the other field element.b - must be 0 or 1, otherwise results are undefined.Copyright © 2019. All rights reserved.