1
$\begingroup$

I am currently trying to understand and implement the design of post quantum algorithm signature algorithm Dilithium. I have read the document several times and they have just used uniform random sampling for s1 and s2 and they have not provided any algorithm regarding its calculation. Viewing the reference code, doesn't help because I am still unable to understand why have they:

  1. used 205 for multiplication
  2. right shift by 10
  3. multiplication by 5
  4. and subtraction from t0.

If this is some known algorithm, then just providing the name of the algorithm is good enough otherwise any help regarding this would be very helpful for my research. The code snippet is also attached as reference.enter image description here

$\endgroup$

1 Answer 1

0
$\begingroup$

This is simply a means to compute $t_0\mod 5$ written by someone much more interested in computational speed than code readability.

Note that $205\approx\frac{1024}5$ so that for small $x$ we have $[x/5]=[205x/1024]$. It follows that for small $x$ we have $x\mod 5=x-[x/5]*5=x-[205x/1024]*5$.

They could have used the (potentially faster) computation

t0 = t0 - (13*t0>>6)*5

but I feel no need to point this out to them and encourage such behaviour.

$\endgroup$
1
  • $\begingroup$ Understood! Thank you Sir. $\endgroup$ Aug 30, 2023 at 9:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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