Fast Modular Exponentiation Algorithm如何处理递归调用？

huangapple
go评论81阅读模式
英文:

How does the Fast Modular Exponentiation Algorithm handle recursive calls?

问题

以下是翻译好的部分：

我已经学习了下面显示的快速模指数算法。

  1. FastExponentiation(a, p, n):
  2.   if p = 0 then
  3.     return 1
  4.   if p is even then
  5.     t <- FastExponentiation(a, p/2, n)
  6.     return t^2 mod n
  7.   t <- FastExponentiation(a, (p-1)/2, n)
  8.   return a(t^2 mod n) mod n

第二和第三个return语句如何在运行这个程序时被执行？在这两个语句之前有一个递归调用，所以程序肯定会进入递归循环吗？

英文:

I have been taught the Fast Modular Exponentiation Algorithm as shown below.

  1. FastExponentiation(a, p, n):
  2.   if p = 0 then
  3.     return 1
  4.   if p is even then
  5.     t <- FastExponentiation(a, p/2, n)
  6.     return t^2 mod n
  7.   t <- FastExponentiation(a, (p-1)/2, n)
  8.   return a(t^2 mod n) mod n

How do the second and third return statements ever get reached when running this program? There is a recursive call before these two statements so surely the program would just enter a recursive loop?

答案1

得分: 2

以下是翻译好的部分：

这个片段可以说明当进一步进入递归时，p 如何减小，直到变为 1。在下一次递归调用中，它变为零：(1-1)/2 → 0。

  1. function fastExp (a, p, n, level = 0, pExpr = '') {
  2.     if (level == 0) {
  3.         console.log(`快速幂运算: ${a} ^ ${p} mod ${n}`);
  4.     }
  5.     console.log(`${'  '.repeat(level)}> p = ${pExpr}${p}`);
  6.     let res;
  7.     if (p == 0) {
  8.         res = 1;
  9.     }
  10.     else if ((p & 1) == 0) {
  11.         let t = fastExp(a, p/2, n, level+1, `${p}/2 = `);
  12.         res = (t*t) % n;
  13.     }
  14.     else {
  15.         let t = fastExp(a, (p-1)/2, n, level+1, `(${p}-1)/2 = `);
  16.         res = (a * ((t*t) % n)) % n;
  17.     }
  18.     console.log(`${'  '.repeat(level)}> ${a} ^ ${p} mod ${n} = ${res}`);
  19.     return res;
  20. }
  22. function rand () { return Math.floor(Math.random() * 50) + 50; }
  23. fastExp(rand(), rand(), rand());
英文:

The snippet below can illustrate you how p decreases while going deeper into the recursion, until it becomes 1. On the next recursive call it becomes zero: (1-1)/2 → 0.

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

  1. function fastExp (a, p, n, level = 0, pExpr = &#39;&#39;) {
  2.     if (level == 0) {
  3.         console.log(`Fast exponentiation: ${a} ^ ${p} mod ${n}`);
  4.     }
  5.     console.log(`${&#39;  &#39;.repeat(level)}&gt; p = ${pExpr}${p}`);
  6.     let res;
  7.     if (p == 0) {
  8.         res = 1;
  9.     }
  10.     else if ((p &amp; 1) == 0) {
  11.         let t = fastExp(a, p/2, n, level+1, `${p}/2 = `);
  12.         res = (t*t) % n;
  13.     }
  14.     else {
  15.         let t = fastExp(a, (p-1)/2, n, level+1, `(${p}-1)/2 = `);
  16.         res = (a * ((t*t) % n)) % n;
  17.     }
  18.     console.log(`${&#39;  &#39;.repeat(level)}&gt; ${a} ^ ${p} mod ${n} = ${res}`);
  19.     return res;
  20. }
  22. function rand () { return Math.floor(Math.random() * 50) + 50; }
  23. fastExp(rand(), rand(), rand());

<!-- end snippet -->

huangapple
  • 本文由 发表于 2023年6月1日 22:37:50
  • 转载请务必保留本文链接：https://go.coder-hub.com/76383060.html
  • algorithm
  • number-theory
  • recursion
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定