Pari/GP 有类似 powermod()，计算 a^k (mod p) 的方法吗？

uk702

找了半天， 就是找不到用来计算 a^k (mod p) 的方法，如果真是这样，个人觉得实在太不可思议了，这和 Pari/GP 以数论专长的定位似并不相符。
故请教大家，gp 中有类似的 powermod() 方法吗？

比如计算 n = 10^100+949, m = (n-1)/4, 计算 2^m (mod n)，2^m % n 、divrem(2^m, n)，Mod(2^m, n) 均出错。
现在找到唯一可用的，似只有 Mod(2, m)^n，然后再用 lift() 取得最小剩余，但这种方式个人觉得绕的弯弯太多了，一点也不直接。

.·.·.

Mod(a,p)^k
我写信问过
这是唯一方法


On Wed, Jul 18, 2018 at 04:07:01AM +0800, （email）@（删掉最好） wrote:
> Package: pari
> Version: 2.10.0
>
> When I tried executing Mod(2^2305843009213693951,23), pari returns a
> stack overflow error which cancel the calculation.

This is normal. You are asking PARI to compute
2^2305843009213693951 which is a number with 694127911065419641 digits,
and then to send it to Z/23Z.

What you should do is to sent 2 to Z/23Z and take the power of the
image:

? Mod(2,23)^2305843009213693951
%14 = Mod(2,23)

Cheers,
Bill

mathematica

1. PowerMod[-1, 1/2, 97]

复制代码

结果是22
表示22^2+1=485是97的倍数485/97=5

mathematica

.·.·. 发表于 2021-2-26 03:06
Mod(a,p)^k
我写信问过
这是唯一方法

奇怪，我没写信。但是我知道这个用法，不知道怎么知道的