如何计算a ^ b ^ c mod p? [英] How to compute a^b^c mod p?

问题描述

我正在尝试为一些正整数a，b，c，p计算a ^ b ^ c mod p.一种可能的(并且很明显的)方法是使用将在O(log(b^c))=clog(b)中运行的快速模块化幂运算.尽管我不介意这里的效率，但是此方法的明显缺点是您需要显式的b^c二进制表示形式，该形式本身已经是指数级的.

I am trying to compute a^b^c mod p for some positive integers a,b,c,p. One possible (and obvious) way is to use fast modular exponentiation which will run in O(log(b^c))=clog(b). While I don't mind the efficiency here, the obvious downfall of this method is that you need an explicit binary representation of b^c which in itself is already exponential.

所以对我来说，问题是，如果我不能将b^c表示为二进制表示形式，是否可以通过a,b, and c的二进制表示形式计算a^b^c mod p?

So the question for me is, if I can not represent b^c as a binary representation, is there a way I can compute a^b^c mod p from the binary representations of a,b, and c?

推荐答案

(a^b^c) mod p = (((a^b) mod p)^c) mod p

所以你可以做

modpow(modpow(a,b,p),c,p);

所有操作数的结果和子结果均为常规整数.作为modpow，您可以通过对模p求平方来使用功率，如下所示:

Where all operands results and subresults are normal ints. As modpow you can use power by squaring in modulo p like here:

• 模块化算术和NTT(有限域DFT)优化

请注意，利用特定选择的p的属性对这些内容进行了一些优化，因此您需要更改类似

beware those are a bit optimized taking advantage of the properties of specific selected p so you need to change lines like

if (DWORD(d)>=DWORD(p)) d-=p;

进入

d%=p;

[示例]

(2^3^5) % 6 = 
(8  ^5) % 6 =
  32768 % 6 = 2

(((2^3)%6)^5) % 6 = 
((   8 %6)^5) % 6 = 
(    2    ^5) % 6 =
    32        % 6 = 2

这篇关于如何计算a ^ b ^ c mod p?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！