数学研发论坛

 找回密码
 欢迎注册
查看: 207|回复: 4

[求助] Pari/GP 有类似 powermod(),计算 a^k (mod p) 的方法吗?

[复制链接]
发表于 2021-2-25 22:12:05 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
找了半天, 就是找不到用来计算 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() 取得最小剩余,但这种方式个人觉得绕的弯弯太多了,一点也不直接。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-2-26 03:06:39 | 显示全部楼层
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

点评

发现这也有好处,比如求 x^2≡-1(mod p),可以直接使用 Mod(-1, p)^(1/2),真爽!  发表于 2021-2-26 06:54

评分

参与人数 1威望 +2 金币 +2 贡献 +2 经验 +2 鲜花 +2 收起 理由
uk702 + 2 + 2 + 2 + 2 + 2 赞一个!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-2-26 09:04:50 | 显示全部楼层
  1. PowerMod[-1, 1/2, 97]
复制代码

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

评分

参与人数 1威望 +2 金币 +2 贡献 +2 经验 +2 鲜花 +2 收起 理由
uk702 + 2 + 2 + 2 + 2 + 2 赞一个!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-2-26 09:07:08 | 显示全部楼层
.·.·. 发表于 2021-2-26 03:06
Mod(a,p)^k
我写信问过
这是唯一方法

奇怪,我没写信。但是我知道这个用法,不知道怎么知道的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2021-4-16 18:12 , Processed in 0.073289 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表