BatchinvertinCurve25519dalek

```rustpub struct Scalar {/// `bytes` is a little-endian byte encoding of an integer representing a scalar modulo the /// group order. /// /// # Invariant /// /// The integer representing this scalar must be bounded above by \\(2\^{255}\\), or /// equivalently the high bit of `bytes[31]` must be zero. /// /// This ensures that there is room for a carry bit when computing a NAF representation. // // XXX This is pub(crate) so we can write literal constants. If const fns were stable, we could // make the Scalar constructors const fns and use those instead. pub(crate) bytes: [u8; 32],}```


```rust pub fn batch_invert(inputs: &mut [Scalar]) -> Scalar { // This code is essentially identical to the FieldElement // implementation, and is documented there. Unfortunately, // it&＃39;s not easy to write it generically, since here we want // to use `UnpackedScalar`s internally, and `Scalar`s // externally, but there&＃39;s no corresponding distinction for // field elements.
use zeroize::Zeroizing;
let n = inputs.len(); let one: UnpackedScalar = Scalar::one().unpack().to_montgomery();
// Place scratch storage in a Zeroizing wrapper to wipe it when // we pass out of scope. let scratch_vec = vec![one; n]; let mut scratch = Zeroizing::new(scratch_vec);
// Keep an accumulator of all of the previous products let mut acc = Scalar::one().unpack().to_montgomery();
// Pass through the input vector, recording the previous // products in the scratch space //----------1---------- for (input, scratch) in inputs.iter_mut().zip(scratch.iter_mut()) { *scratch = acc;
// Avoid unnecessary Montgomery multiplication in second pass by // keeping inputs in Montgomery form let tmp = input.unpack().to_montgomery(); *input = tmp.pack(); acc = UnpackedScalar::montgomery_mul(&acc, &tmp); } //-----------2------------ // acc is nonzero iff all inputs are nonzero debug_assert!(acc.pack() != Scalar::zero());
// Compute the inverse of all products //----------3-------------- acc = acc.montgomery_invert().from_montgomery();
// We need to return the product of all inverses later let ret = acc.pack();
// Pass through the vector backwards to compute the inverses // in place //---------------4--------------- for (input, scratch) in inputs.iter_mut().rev().zip(scratch.iter().rev()) { let tmp = UnpackedScalar::montgomery_mul(&acc, &input.unpack()); *input = UnpackedScalar::montgomery_mul(&acc, &scratch).pack(); acc = tmp; } ret }```

- i=0 ： - Inputs: $[d,c,b,a]$ -----> $inputs[0]=acc*scratch[0]=(abcd)^{-1}*abc=d^{-1}$ ---> inputs: $[d^{-1},c,b,a]$ - Scratch: $[abc,ab,a,1]$ - $acc=(abcd)^{-1}$ ----> $acc=acc*inputs[0]$ -----> $acc=(abc)^{-1}$
- i=1 ： - Inputs: $[d^{-1},c,b,a]$ -----> $inputs[1]=acc*scratch[1]=(abc)^{-1}*ab=c^{-1}$ ---> inputs: $[d^{-1},c^{-1},b,a]$ - Scratch: $[abc,ab,a,1]$ - $acc=(abc)^{-1}$ ----> $acc=acc*inputs[1]$ -----> $acc=(ab)^{-1}$
- i=2 ： - Inputs: $[d^{-1},c^{-1},b,a]$ -----> $inputs[2]=acc*scratch[2]=(ab)^{-1}*a=b^{-1}$ ---> inputs: $[d^{-1},c^{-1},b^{-1},a]$ - Scratch: $[abc,ab,a,1]$ - $acc=(ab)^{-1}$ ----> $acc=acc*inputs[2]$ -----> $acc=(a)^{-1}$
- i=3： - Inputs: $[d^{-1},c^{-1},b^{-1},a]$ -----> $inputs[3]=acc*scratch[3]=(a)^{-1}*1=a^{-1}$ ---> inputs: $[d^{-1},c^{-1},b^{-1},a^{-1}]$ - Scratch: $[abc,ab,a,1]$  - $acc=(a)^{-1}$ ----> $acc=acc*inputs[3]$ -----> $acc=1$

| #scalar | BatchInvert | Total/us | Average/us || ------- | ----------- | -------- | ---------- || 1 | False | 11.234 | 11.234 || 1 | True | 11.865 | 11.865 || 2 | True | 12.269 | 6.1345 || 4 | True | 12.676 | 3.169 || 8 | True | 13.445 | 1.6806 || 16 | True | 15.484 | 0.96775 |