1

我试图实现一种算法来计算以 m 为模的电力塔。下面的程序塔应该计算 2^3^...^14^15 (mod m)，而 tower2 应该计算 15^14^...^3^2 (mod m)。但是对于 m = 163 ， tower2 会产生错误的答案。我发现立即结果为 0，并且程序没有得到这个。任何人都可以修复错误吗？

程序 powmod 已实现并且运行良好：

powmod(basis,exponent,modul)={if(exponent==0,hilf=1);if(exponent>0,bin=binary(exponent);hilf=basis;hilf=hilf-truncate(hilf/modul)*modul;for(stelle=2,length(bin),hilf=hilf^2;if(bin[stelle]==1,hilf=hilf*basis);hilf=hilf-truncate(hilf/modul)*modul));hilf}

? tower

%19 = (p,q,r)->if(q==0,hilf=1);if(q==1,hilf=p);if(q==2,hilf=powmod(p,p,r));if(q>
2,x=[];for(j=1,q,x=concat(x,r);r=eulerphi(r));hilf=14^15;forstep(j=13,2,-1,r=x[j
-1];if(r>=2,hilf=powmod(j,hilf,r);w=factorint(r);w=component(w,2);while(hilf<vec
max(w),hilf=hilf+r))));component(Mod(hilf,r),2)

? tower2

%20 = (p,q,r)->if(q==0,hilf=1);if(q==1,hilf=p);if(q==2,hilf=powmod(p,p,r));if(q>
2,x=[];for(j=1,q,x=concat(x,r);r=eulerphi(r));hilf=3^2;forstep(j=13,2,-1,r=x[j-1
];if(r>=2,hilf=powmod(17-j,hilf,r);w=factorint(r);w=component(w,2);while(hilf<ve
cmax(w),hilf=hilf+r))));component(Mod(hilf,r),2)
?
4

1 回答 1

0

您的代码不起作用的原因是您（递归地）将 x^n (mod r) 计算为 x^(n mod phi(r))，除非 gcd(x,r) = 1，否则这是不正确的。

此外，您不需要 powmod，因为Mod(basis,modul)^expo它是内置的。这是一个普遍的可能性：

\\ x[1]^(x[2]^( ...^ x[#x])) mod m, assuming x[i] > 1 for all i
tower(x, m) =
{ my(f = factor(m), P = f[,1], E = f[,2]);
  chinese(vector(#P, i, towerp(x, P[i], E[i])));
}

towerp(x, p, e) =
{ my(q = p^e, i, t, v);

  if (#x == 0, return (Mod(1, q)));
  if (#x == 1, return (Mod(x[1], q)));
  if (v = valuation(x[1], p),
    t = x[#x]; i = #x;
    while (i > 1,
      if (t >= e, return (Mod(0, q)));
      t = x[i]^t; i--);
    if (t * v >= e, return (Mod(0, q)));
    return (Mod(x[1], q)^t);
  );
  Mod(x[1], q)^lift(tower(x[2..#x], (p-1)*p^e));
}

? tower([2..15], 163)
%1 = Mod(162, 163)
? tower(Vecrev([2..15]), 163)
%2 = Mod(16, 163)
于 2021-11-04T01:09:25.800 回答