求教关于超大数的幂模运算怎么做?

软件和网站开发以及相关技术探讨
回复
rlophous
帖子: 1
注册时间: 2010-06-20 13:28

求教关于超大数的幂模运算怎么做?

#1

帖子 rlophous » 2010-06-20 13:30

三个正整数a,n,p,

a<=10000,n<=10^10000,p<=100000000 。求a^n mod p。

这数的范围有点太大了。。特别是指数。。。 :em06
头像
meteormatt
帖子: 693
注册时间: 2008-02-24 14:15
系统: Ubuntu
来自: 江苏
联系:

Re: 求教关于超大数的幂模运算怎么做?

#2

帖子 meteormatt » 2010-06-21 16:59

rlophous 写了:三个正整数a,n,p,

a<=10000,n<=10^10000,p<=100000000 。求a^n mod p。

这数的范围有点太大了。。特别是指数。。。 :em06
用那个Long行吗?

一直到2147483647.

再长我就不会了.

怀念以前的老台式机。可惜现在租的地方没条件用了。目前只能用笔记本和手机了。
头像
HuntXu
帖子: 5776
注册时间: 2007-09-29 3:09

Re: 求教关于超大数的幂模运算怎么做?

#3

帖子 HuntXu » 2010-06-21 17:38

欧拉定理,不解释...
HUNT Unfortunately No Talent...
头像
BigSnake.NET
帖子: 12522
注册时间: 2006-07-02 11:16
来自: 廣州
联系:

Re: 求教关于超大数的幂模运算怎么做?

#4

帖子 BigSnake.NET » 2010-07-01 21:14

a^n = (a^(n/2))^2 (n 是偶数)

a^n = a * a^(n-1) (n 是基数)

算法复杂度 O(logn)
^_^ ~~~
要理解递归,首先要理解递归。

地球人都知道,理论上,理论跟实际是没有差别的,但实际上,理论跟实际的差别是相当大滴。
dshbusiness
帖子: 1831
注册时间: 2009-04-03 15:10

Re: 求教关于超大数的幂模运算怎么做?

#5

帖子 dshbusiness » 2010-07-01 21:20

查数论书,关于模的运算可以化简,不过我忘了……可惜
水妖上邪
帖子: 14
注册时间: 2007-05-25 5:59
来自: Danmark
联系:

Re: 求教关于超大数的幂模运算怎么做?

#6

帖子 水妖上邪 » 2010-07-02 0:17

如果你用的是特定数(10,100,100...)你完全可以自己设计一个算法针对特定数字做,如果你是做随机整数,你可以用循环

long x=1;
for(int m=1;m<n;m++){
x=a*x;
y=mod(a,p); //求a^1与p的模
x=y; //只保留模
}

这个算法很容易证明
changys04
帖子: 286
注册时间: 2006-11-08 16:33

Re: 求教关于超大数的幂模运算怎么做?

#7

帖子 changys04 » 2010-07-02 2:23

HuntXu 写了:欧拉定理,不解释...
哇,3楼好厉害,佩服佩服
哈哈,我给他解释,首先a和p都不大,所以可以因式分解对吧?a很小,所以因式分解出来也不复杂是吧?因此可以只考虑a是素数的情形。也就是说我们假定a,p互素。然后存在最小正整数d使得a^d=1(mod p),记为o(a),是a的阶。如果你能求出这个d,肯定就能化简了吧?ok,退一步,实际上你不需要这个d是最小的对吧,差不多就行了。d取\phi{p},即从1到p中与p互诉的整数个数,既然你已经把p因式分解了也就容易求得了吧?最后附上参考网页
http://zh.wikipedia.org/zh-hans/%E6%AC% ... 8%AE%BA%29
afphoenix
帖子: 153
注册时间: 2009-01-07 15:19

Re: 求教关于超大数的幂模运算怎么做?

#8

帖子 afphoenix » 2010-07-02 9:01

这点东西都要祭出欧拉兄?欧老都要累死了....


4楼说的对,快速幂不解释。 :em05
大家好,我是计算机系大学生,玩电脑也 7.8 年了吧,可是这个系统为什么XXX,就不能XXX,连我这种XXX都XXX,怎么能够推广,看来XXX路还很长XXX,搞不懂你们这些XXX,再见了XXX
changys04
帖子: 286
注册时间: 2006-11-08 16:33

Re: 求教关于超大数的幂模运算怎么做?

#9

帖子 changys04 » 2010-07-03 8:08

afphoenix 写了:这点东西都要祭出欧拉兄?欧老都要累死了....


4楼说的对,快速幂不解释。 :em05
很有道理, 毕竟用欧拉公式,最后两大数除法求余数也是要死人的, 由于n是已经k进制展开的所以快速幂一定很快
回复