R中优化的算术方法

Question

openssl包实现了一个bignum类,该类具有相应的算术和比较方法,可以对任意大小的整数执行计算.

在密码学中,模块化指数 有一个共同的特殊情况,x^p %% m例如rsa使用.对于大型p计算,计算x^p是不可行的,但x^p %% m可以有效地计算OpenSSL实现的计算BN_mod_exp().

R是否提供了实现^.bignum和%%.bignum方法的任何机制, 以便在评估时x^y %% z我们可以调用这种特殊情况而不是实际计算x^p？

Answer 1

虽然迟到了，但是，这绝对是可能的，并且它\xe2\x80\x99是某些语言中相当常见的编程技术，例如 C++，其中该技术称为表达式模板。

\n\n

R 是弱类型的，无法在相同程度上充分利用该模式。但 \xe2\x80\x9clight\xe2\x80\x9d 版本仍然是可能的。

\n\n

简而言之，您定义^.bignum运算符，以便它返回一个代表 \xe2\x80\x9c 求幂运算 \xe2\x80\x9d 的代理对象，而不是立即计算结果。该代理对象有一个专门重写的%%方法，该方法调用 ExpMod 实现（例如BM_mod_exp）。它还定义了一个方法，bignum通过评估实际x ^ y操作将其强制为 a。

\n\n

在代码中，这可能如下所示：

\n\n

# Vectorisation left as an exercise for the reader.\n\n`^.bignum` = function (x, y)\n    structure(c(x, y), class = \'bignum_mod_exp_proxy\')\n\neval_exp = function (x)\n    call_actual_exp(x[1], x[2])\n\nas.bignum = function (x)\n    if (inherits(x, \'bignum_mod_exp_proxy\'))\n        eval_exp(x)\n    else\n        # \xe2\x80\xa6 implement other coercions to bignum, e.g. from `numeric`.\n\n`%%.bignum_mod_exp_proxy` = function (x, y)\n    call_BN_mod_exp(x[1], x[2], y)\n\n# Pretend that a `bignum_mod_exp_proxy` in all other contexts. E.g.:\n\nprint.bignum_mod_exp_proxy = function (x, ...)\n    print(eval_exp(x))\n\n# \xe2\x80\xa6 etc., for the rest of the `bignum` operations.\n

\n\n

事实上，您甚至可以覆盖=.bignum_mod_exp_proxy, <-.bignum_mod_exp_proxyand assign.bignum_mod_exp_proxy（转换assign为 S3 泛型），以便z = x ^ y将赋值立即评估为bignum. 然而，这可能有点矫枉过正，并且会为每次分配带来开销。

\n