小数字的快速幂优化算法

无心人

对于小于16的正整数n，大数p>2^64，大数m>2^64
如何更快速的计算
$n^p % m$
有没有办法得到比传统快速幂算法更好的结果

nyy

穷举检索？

.·.·.

目前最好的工作大约在prime95里面
prime95的最好成绩是，给出了一个证明n^p%m=c的证据，通过证据可以快速进行验证
所以，目前来说没有

无心人

目前想到的优化是
1、x = n; while (x < m) x *= n;  n1 = x%m; 让底数变成大数
2、x = n; while (x < m) x *= x;  n1 = x%m; 同样，但是快速平方，相对更少计算

ShuXueZhenMiHu

请问百分号是什么意思？

gxqcn

无心人 发表于 2023-10-23 09:55
目前想到的优化是
1、x = n; while (x < m) x *= n;  n1 = x%m; 让底数变成大数
2、x = n; while (x < m) x ...

一般的快速模幂算法, 也适用于楼主的底数为小数字情形; 反之不然.
所以, 底数变大数, 是一种信息损失, 只会更慢.

因为乘法取模中, 若乘数有小整数, 积可能更大概率不大于模, 可不用修正;
底数变大, 指数变小, 但后者的bit数减少有限, 并不划算.

无心人

gxqcn 发表于 2023-10-24 17:55
一般的快速模幂算法, 也适用于楼主的底数为小数字情形; 反之不然.
所以, 底数变大数, 是一种信息损失, 只 ...

确实，p次快速幂常规乘法次数是p的二进制长度和二进制表示中1的个数的和
换成大数后，p减少后，二进制长度和二进制表示中1的个数的和并没有少多少
加上附加运算，可能不划算了

所以，这个方法不通了

为啥想做这个，是因为最近万年不更新的GMP更新了6.3.0
其中一个改进就是
New special code for base = 2 in mpz_powm reduces the average time for the functions that test primality.
所以我才考虑这个问题

gxqcn

base=2, 乘法可优化成移位, 可能仅仅是这个缘故吧.