why the specific bits split_len works within fixed_scalar_mul_le function?

[PayneJoe]

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 is q

Still not clear why the lower range [0, G::Base::NUM_BITS - 2) of scalar k would make sure that point Acc and point P are constrained within safe distance, namely to say point Acc is [2, q - 1) times point P or point P is [2, q - 1) times point Acc? 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 over F_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!

[Pratyush]

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.