FieldElement represents an element of the field GF(2^255 - 19). 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.
func FeAdd(dst, a, b *FieldElement)
func FeCMove(f, g *FieldElement, b int32)
func FeCombine(h *FieldElement, h0, h1, h2, h3, h4, h5, h6, h7, h8, h9 int64)
func FeCopy(dst, src *FieldElement)
func FeFromBytes(dst *FieldElement, src *[32]byte)
func FeInvert(out, z *FieldElement)
func FeIsNegative(f *FieldElement) byte
func FeIsNonZero(f *FieldElement) int32
func FeMul(h, f, g *FieldElement)
func FeNeg(h, f *FieldElement)
func FeOne(fe *FieldElement)
func FeSquare(h, f *FieldElement)
func FeSquare2(h, f *FieldElement)
func FeSub(dst, a, b *FieldElement)
func FeToBytes(s *[32]byte, h *FieldElement)
func FeZero(fe *FieldElement)
func fePow22523(out, z *FieldElement)
func feSquare(f *FieldElement) (h0, h1, h2, h3, h4, h5, h6, h7, h8, h9 int64)
var A
var SqrtM1
var d
var d2
var zero
FeMul calculates h = f * g
Can overlap h with f or g.
Preconditions:
|f| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
|g| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
Postconditions:
|h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*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.
FeNeg sets h = -f
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.
FeSquare calculates h = f*f. Can overlap h with f.
Preconditions:
|f| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
Postconditions:
|h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
FeSquare2 sets 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 fe_mul.c for discussion of implementation strategy.
FeToBytes marshals h to s.
Preconditions:
|h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
Write p=2^255-19; q=floor(h/p).
Basic claim: q = floor(2^(-255)(h + 19 2^(-25)h9 + 2^(-1))).
Proof:
Have |h|<=p so |q|<=1 so |19^2 2^(-255) q|<1/4.
Also have |h-2^230 h9|<2^230 so |19 2^(-255)(h-2^230 h9)|<1/4.
Write y=2^(-1)-19^2 2^(-255)q-19 2^(-255)(h-2^230 h9).
Then 0<y<1.
Write r=h-pq.
Have 0<=r<=p-1=2^255-20.
Thus 0<=r+19(2^-255)r<r+19(2^-255)2^255<=2^255-1.
Write x=r+19(2^-255)r+y.
Then 0<x<2^255 so floor(2^(-255)x) = 0 so floor(q+2^(-255)x) = q.
Have q+2^(-255)x = 2^(-255)(h + 19 2^(-25) h9 + 2^(-1))
so floor(2^(-255)(h + 19 2^(-25) h9 + 2^(-1))) = q.
GeDoubleScalarMultVartime sets r = a*A + b*B
where a = a[0]+256*a[1]+...+256^31 a[31].
and b = b[0]+256*b[1]+...+256^31 b[31].
B is the Ed25519 base point (x,4/5) with x positive.
GeScalarMultBase computes h = a*B, where
a = a[0]+256*a[1]+...+256^31 a[31]
B is the Ed25519 base point (x,4/5) with x positive.
Preconditions:
a[31] <= 127
ScMinimal returns true if the given scalar is less than the order of the
curve.
Input:
a[0]+256*a[1]+...+256^31*a[31] = a
b[0]+256*b[1]+...+256^31*b[31] = b
c[0]+256*c[1]+...+256^31*c[31] = c
Output:
s[0]+256*s[1]+...+256^31*s[31] = (ab+c) mod l
where l = 2^252 + 27742317777372353535851937790883648493.
Input:
s[0]+256*s[1]+...+256^63*s[63] = s
Output:
s[0]+256*s[1]+...+256^31*s[31] = s mod l
where l = 2^252 + 27742317777372353535851937790883648493.
equal returns 1 if b == c and 0 otherwise, assuming that b and c are
non-negative.
The pages are generated with Goldsv0.3.2. (GOOS=linux GOARCH=amd64)
Golds is a Go 101 project developed by Tapir Liu.
PR and bug reports are welcome and can be submitted to the issue list.
Please follow @Go100and1 (reachable from the left QR code) to get the latest news of Golds.
