public class Ed25519LittleEndianEncoding extends Encoding
Reviewed/commented by Bloody Rookie (nemproject@gmx.de)
Constructor and Description |
---|
Ed25519LittleEndianEncoding() |
Modifier and Type | Method and Description |
---|---|
FieldElement |
decode(byte[] in)
Decodes a given field element in its 10 byte 2^25.5 representation.
|
byte[] |
encode(FieldElement x)
Encodes a given field element in its 32 byte representation.
|
boolean |
isNegative(FieldElement x)
Is the FieldElement negative in this encoding?
|
(package private) static int |
load_3(byte[] in,
int offset) |
(package private) static long |
load_4(byte[] in,
int offset) |
public byte[] encode(FieldElement x)
The idea for the modulo p reduction algorithm is as follows:
Assumption:
Then q = [2^-255 * (h + 19 * 2^-25 * h9 + 1/2)] where [x] = floor(x).
Proof:
We begin with some very raw estimation for the bounds of some expressions:
|h| < 2^230 * 2^30 = 2^260 ==> |r + q * p| < 2^260 ==> |q| < 2^10. ==> -1/4 <= a := 19^2 * 2^-255 * q < 1/4. |h - 2^230 * h9| = |h0 + ... + 2^204 * h8| < 2^204 * 2^30 = 2^234. ==> -1/4 <= b := 19 * 2^-255 * (h - 2^230 * h9) < 1/4Therefore 0 < 1/2 - a - b < 1.
Set x := r + 19 * 2^-255 * r + 1/2 - a - b then 0 <= x < 255 - 20 + 19 + 1 = 2^255 ==> 0 <= 2^-255 * x < 1. Since q is an integer we have
[q + 2^-255 * x] = q (1)
Have a closer look at x:
x = h - q * (2^255 - 19) + 19 * 2^-255 * (h - q * (2^255 - 19)) + 1/2 - 19^2 * 2^-255 * q - 19 * 2^-255 * (h - 2^230 * h9) = h - q * 2^255 + 19 * q + 19 * 2^-255 * h - 19 * q + 19^2 * 2^-255 * q + 1/2 - 19^2 * 2^-255 * q - 19 * 2^-255 * h + 19 * 2^-25 * h9 = h + 19 * 2^-25 * h9 + 1/2 - q^255.
Inserting the expression for x into (1) we get the desired expression for q.
static int load_3(byte[] in, int offset)
static long load_4(byte[] in, int offset)
public FieldElement decode(byte[] in)
public boolean isNegative(FieldElement x)
Return true if x is in {1,3,5,...,q-2}
Return false if x is in {0,2,4,...,q-1}
Preconditions:
isNegative
in class Encoding