In the previous standard, the deterministic was not included. It is already in the current standard. What is the reason for this? Can I use both function?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
The probabilistic algorithm has (at least part) of it's runtime that follows an approximately geometric distribution. So it can sometime take a long time. In some applications, that's an issue: for excellent reasons, there's almost always some finite timeout to any process, often determined experimentally. Geometric distribution of execution time is a tried and tested method for field failures. I've seen this in more than one Smart Card production line at the RSA key generation step.
I have not analyzed the deterministic algorithm in detail, but it's maximum run time for a given parameter size can be strictly bounded, and is I guess lower than for the probabilistic algorithm in some sizable fraction of cases (perhaps, often; or even to the point of being faster on average). Also, if an implementation is made strictly constant-time, that's one less area of worries against side-channel leakage.
answered May 6, 2021 at 18:58
-
2$\begingroup$ Actually, the deterministic algorithm looks to be faster in all cases; it just consists of a few integer multiples, divides and a square-root. $\endgroup$– ponchoMay 6, 2021 at 19:38