0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • 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$
    – poncho
    May 6 at 19:38

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.