Open PayneJoe opened 1 year ago
If G::ScalarField = 2^n + 1
, then G::ScalarField - 1
will fit in G::ScalarField::NUM_BITS - 1
bits. If we perform the "safe" part of the scalar multiplication with this, we'll end up with -Acc
as the result, which requires special handling in the add_mixed
.
In your example, the test case fits within the paradigm, no? [0, 4) is safe because G::ScalarField::NUM_BITS - 2 = 4.
Hi,
It seems like you split the scalar bits into two parts at the specific index
G::Base::NUM_BITS - 2
, after that the first part is safe to apply addition upon affine coordinates, while the second one have to use addition formula upon projective coordinates.The question is why the specific index works?
Suppose that addition is defined like
Acc = Acc + P
, prime modular isq
Still not clear why the lower range
[0, G::Base::NUM_BITS - 2)
of scalar k would make sure that pointAcc
and pointP
are constrained within safe distance, namely to say pointAcc
is[2, q - 1)
times pointP
or pointP
is[2, q - 1)
times pointAcc
? How about the other ranges such as[0, G::Base::NUM_BITS - 1)
or[0, G::Base::NUM_BITS - 3)
or ...?I run a test using curve
y^2 = x^3 + 4x + 20
overF_29
(5 bits length), while its order is 37(6 bits length). It turns out that the edge cases(Acc == P or Acc == -P)
always appears in the highest bit(k = 36 or 37). Indeed it's safe within bits[0, 3)
, but it's also safe within bits[0, 4)
.Appreciated if you guys give some hits about this!