0
$\begingroup$

Since the prime for bls12-381 is not of a form to allow easy modular reduction , is the best approach to use the Montgomery multiplication + reduction algorithm?

(q = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab)

If I do this, can I convert the affine point coordinates into jacobian projected and then into their Montgomery form at the very start, so all modulo multiplications inside the point double / add algorithms use the Montgomery algorithm? Then only convert out of Montgomery form and then back to affine coordinates at the very end.

$\endgroup$
  • $\begingroup$ Unless there's some special structure you can exploit in $q$ (and if there is, it's not obvious to me), Montgomery form is a reasonable choice, with a Barrett reduction to kick it off. $\endgroup$ – Squeamish Ossifrage May 22 at 14:12
0
$\begingroup$

I figured this out, the best approach is to use either Montgomery or Barrets algorithm for modulo reduction, Barrets requires a slightly higher bit multiplication but not pre-transformation, while Montgomery has a pre-transformation but multiplications are slightly faster.

And if you use Montgomery you can do the entire point double/add in Montgomery form using jacobian coordinates and just convert back at the end.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.