Class Ed25519FieldElement
- All Implemented Interfaces:
Serializable
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:
-
Field Summary
Modifier and TypeFieldDescription(package private) final int[]
Variable is package private for encoding.Fields inherited from class net.i2p.crypto.eddsa.math.FieldElement
f
-
Constructor Summary
-
Method Summary
Modifier and TypeMethodDescriptionadd
(FieldElement val) $h = f + g$cmov
(FieldElement val, int b) Constant-time conditional move.boolean
int
hashCode()
invert()
Invert this field element.boolean
Gets a value indicating whether or not the field element is non-zero.multiply
(FieldElement val) $h = f * g$negate()
$h = -f$pow22523()
Gets this field element to the power of $(2^{252} - 3)$.square()
$h = f * f$$h = 2 * f * f$subtract
(FieldElement val) $h = f - g$toString()
Methods inherited from class net.i2p.crypto.eddsa.math.FieldElement
addOne, divide, isNegative, subtractOne, toByteArray
-
Field Details
-
t
final int[] tVariable is package private for encoding.
-
-
Constructor Details
-
Ed25519FieldElement
Creates a field element.- Parameters:
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.
-
-
Method Details
-
isNonZero
public boolean isNonZero()Gets a value indicating whether or not the field element is non-zero.- Specified by:
isNonZero
in classFieldElement
- Returns:
- 1 if it is non-zero, 0 otherwise.
-
add
$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 classFieldElement
- Parameters:
val
- The field element to add.- Returns:
- The field element this + val.
-
subtract
$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 classFieldElement
- Parameters:
val
- The field element to subtract.- Returns:
- The field element this - val.
-
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 classFieldElement
- Returns:
- The field element (-1) * this.
-
multiply
$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 classFieldElement
- Parameters:
val
- The field element to multiply.- Returns:
- The (reasonably reduced) field element this * val.
-
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 classFieldElement
- Returns:
- The (reasonably reduced) square of this field element.
-
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 classFieldElement
- Returns:
- The (reasonably reduced) square of this field element times 2.
-
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 classFieldElement
- Returns:
- The inverse of this field element.
-
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 classFieldElement
- Returns:
- This field element to the power of $(2^{252} - 3)$.
-
cmov
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 classFieldElement
- 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() -
equals
-
toString
-