RSA, Dickson, LUC and Williams: a study on four polynomial-type public-key cryptosystems
In the work at hand we regard the public-key cryptosystems RSA, Dickson, LUC and Williams. The Dickson and LUC systems are, for parameter $$P=a=1$$
 , identical, except for the fact that the LUC system reduces the degrees of the decryption functions by employing ciphertext-dependent decryption parameters. We show that also for the Dickson system with parameter $$a=-1$$
 the degrees of the decryption functions can be reduced. Furthermore, we emphasize on the implementability of the systems and apply for Dickson and LUC a seemingly rather unknown algorithm proposed by Montgomery to evaluate recurrences of the form $$X_{m+n}=f(X_m,X_n,X_{m-n})$$
 . It turns out that this algorithm reduces the computational efforts of Dickson and LUC compared to commonly applied binary algorithms by about $$10\,\%$$
 . For the Williams system we propose an algorithm which reduces its computational effort to almost one half compared to other proposed algorithms. Finally, we evaluate the computational efforts of the cryptosystems and show that the improvements proposed in this paper reduce the performance gaps between RSA and Dickson, LUC and Williams considerably.