转载metal-fan Modular Exponentiation

LJ posted @ Jun 06, 2010 07:56:42 PM in algorithm with tags Algorithm , 1969 阅读

 

  计算大整数的模幂比如 $b^n\,mod\,m$时 $b^n$会非常大，直接去计算不是好的方法。

 

可以把n用二进制展开式表示 n = $\left(a_{k-1}a_{k-2}...a_1a_0\right)_2$

那么问题就变成了$b^n = b^{a_{k-1} \cdot 2^{k-1}+\cdots+a_1\cdot2+a_0} = b^{a_{k-1} \cdot 2^{k-1}}{\cdots}b^{a_1^2}{\cdot}b^{a_0}$

所以要计算$b^n$，就要先算出$b, b^2, (b^2)^2=b^4, (b^4)^2=b^8,\cdots, b^{2^{k-1}}$

再把这些当$a_j = 1$时的$b^{2^j}$的项乘起来。

根据公式$ab\,mood \,m = ((a\,mod\,m)(b\,mod\,m))mod\,m$

所以只需把$a_j = 1$的各项$b^{2^j}$ mod m乘起来再除以m取余就能得到结果了。

算法伪码如下：

procedure modular exponentiation(b: integer, n = $\left(a_{k-1}a_{k-2}...a_1a_0\right)_2$, m: positive integer)

x := 1

power := b mod m

for i := 0 to k-1

begin

          if $a_i$ = 1 then x := (x * power) mod m

          power := (power * power) mod m

end

 

 针对上面的算法来举个例子

 

计算a的b次方对9907取模的值。

输入

第一行有一个正整数T，表示有T组测试数据。

接下来T行，每行有一组测试数据，包含两个整数a和b。

其中T<10000,0<a,b<2^31。

样例输入

3

1 2

2 3

3 4

样例输出

1

8

81

 十进制转二进制函数

int DToB (unsigned long int decimal,int *binary)

{

　　if(binary==NULL)

　　　　　return -1;

　　int i = 0;

　　while(decimal>0)

　　{

　　　　　binary[i] = decimal%2;

　　　　  decimal = decimal/2;

　　　　　i++;

　　}

　　return i;

}

主函数代码如下：

 int main()

{

　　int T,i;

　　unsigned long int a,b;

　　int res;

　　int binary[32];

　　scanf("%d",&T);

　　if(T>100000||T<0)

　　　　　return -1;

　　for (i=0;i<T;i++)

　　{

　　　　scanf("%lu %lu",&a,&b);

　　　　if(a>=214783648||a<0)

　　　　　　　return -1;

　　　　if(b>=214783648||b<0)

　　　　　　　return -1;


　　　　res = DToB(b,binary);

　　　　if(res==-1)

　　　　　　　return -1;

　　　　int p = 1;

　　　　for(;res>=0;res--)

　　　　{

　　　　　　p = (p*p)%9907;

　　　　　　if(binary[res]==1)

　　　　　　p = (p*a)%9907;

　　　　}

　　　　printf("%d\n",p);

　　}

　　return 0;

 }

这个例子中的算法在实现上和上面说的稍微有点出入，一个是从低位到高位计算幂取模，另外一个则是从高位到低位来计算

个人感觉还是从低到高的算法比较容易理解，但两种都收集下。

Small_feed 评论 (6)
1
[回复]
deep cleaning abu dh 说:
Nov 02, 2019 03:19:08 PM

Though it may not be that obvious, a clear home reliefs anxiety reduction. Deep cleaning your property, even only if every half a year or thus, helps detox your liveable space and supplies a more pacific cycles and strenuous environment. By reducing your residence of airborne dirt and dust, clutter, dander, and trash it is possible to experience an improved home. Not almost all commercial washing companies inside Dubai offer the sort of quality program that you’ll locate executed simply by SpringCleaning™

2
[回复]
Macys Credit Card Lo 说:
Aug 26, 2022 12:57:54 PM

Macy's Credit Card. Want to pay your bill online? Sign in to access your account and make a one-time payment, Macys Credit Card Login or set up monthly auto-payments for hassle-free. Explore Entertainment Access ... If your Macy's Credit Card Account is closed by you or us, or you fail to make a qualifying purchase on your Macy's Credit Card 2021.Macy's Credit Card. Want to pay your bill online? Sign in to access your account and make a one-time payment.

3
[回复]
NCERT Urdu Question 说:
Sep 29, 2022 12:46:58 PM

Urdu Language was constitutionally given national status. Now Urdu is our national language, but provincialism and ethnicism are out to kill the national language. Like past heritage and traditions, language plays a very important role in national awakening and national integration. Urdu is ideally suited for expression and instructions in art, science, and commerce up to the university level.NCERT Urdu Question Paper Class 9 Urdu Language was constitutionally given national status. Now Urdu is our national language, but provincialism and ethnicism are out to kill the national language. Like past heritage and traditions.

4
[回复]
whatsapp status verz 说:
Jul 26, 2023 12:04:30 AM

Mit WhatsApp Status können Sie Bilder und Videos an andere Benutzer der Messaging-App senden, die sich zu einer beliebten Social-Networking-Plattform in Indien entwickelt hat. whatsapp status verzeichnis WhatsApp war früher einfach eine Messaging-App. WhatsApp Status ist eine Option, mit der Sie Statusaktualisierungen senden können, die nach einem Tag gelöscht werden. Sie können Bilder, Videos, Text, Links und animierte GIFs senden.

5
[回复]
Arunachal Pradesh 8 说:
Aug 26, 2023 07:31:17 PM

Arunachal Pradesh 8th Question Paper 2024 All the Online PDF format Question Papers Provided by Board of Secondary Education Arunachal Pradesh,Arunachal Pradesh Model Question Paper 2024 are Arunachal Pradesh 8th Model Paper 2024 Prepared as per the updated Board of Education in the Arunachal Pradesh State Syllabus to help Students in their exam Preparations, which Aims to build both the Practical knowledge as well as analytical Skills for Arunachal Pradesh Every Student,Arunachal Pradesh Question Paper 2024 are Prepared as per the updated Arunachal Pradesh Syllabus & Exam Pattern to help Students in their Exam Preparations.Arunachal Pradesh Previous Question Paper 2024 will help a lot to the Students.

6
[回复]
boardmodelpaper.com 说:
Jan 20, 2024 08:14:27 PM

Board Model Papers 2024 provide all states of 6th to 10th text books 2024 Candidates who are Searching for 6th to 10th and 11th to 12th text books and syllabus, sample questions, exam pattern, and Co-Curricular Subject textbooks can refer to this entire article. boardmodelpaper.com and question papers for following the website and Arts, Science, Commerce Stream Subject Wise Solved Question Bank for Hindi & English Medium Students with Exam Pattern & Blueprint and subject Wise with 11th & 12th Question Bank 2024 for General & Vocational Course. Here, we have gathered all subjects of Board textbooks for all Class along with the direct download links.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter