嘿，我来帮你梳理下RSA计算里的问题，顺便讲讲高效的模幂方法！

首先先核对你已有的计算：

• 你算的n = p*q = 89*101 = 8989完全正确，φ(n) = (89-1)*(101-1) = 88*100 = 8800也没问题。
• 不过求私钥d的时候出错啦！你用的d = (1 + k*φ(n))/e思路是对的，但选的k不符合要求。我们需要让1 + k*φ(n)能被e=7整除：
  • 先算φ(n) mod 7：8800除以7得1257余1，所以8800 ≡1 mod7
  • 那1 + k*1 ≡0 mod7，很明显k=6（1+6=7，刚好能被7整除）
  • 代入得d=(1+6*8800)/7=(1+52800)/7=52801/7=7543
  • 验证下：7*7543=52801，52801 mod8800=52801-6*8800=1，完美符合de≡1 modφ(n)的要求！你之前算的1257，7*1257=8799，8799 mod8800=-1，并不满足条件，用它解密肯定出问题。

接下来重点讲高效计算模幂的核心方法——快速幂（平方乘算法），不管是加密c = m^e modn还是解密m = c^d modn，都不用硬算超大数，通过逐步平方+取模就能轻松搞定：

一、高效计算加密值c = 100^7 mod8989 #

把指数7转换成二进制是111，对应2² + 2¹ + 2⁰，分步计算：

1. 先算各个2的幂次对应的模结果：
   • 100^1 mod8989 = 100
   • 100^2 mod8989 = 10000 - 8989 = 1011（直接平方后减n取模）
   • 100^4 mod8989 = (1011)^2 mod8989 = 1022121 - 113*8989 = 1022121 - 1015757 = 6364（先平方，再用n的倍数去减，得到小于n的结果）
2. 把二进制位为1的幂次相乘再取模：
   • 100^7 = 100^4 * 100^2 * 100^1
   • 先算6364 * 1011 mod8989：6364*1011=6364000+69994=6433994，6433994 - 715*8989=6433994-6427135=6859
   • 再算6859 * 100 mod8989=685900 -76*8989=685900-683164=2736
     所以正确的加密值c=2736（你之前直接算100^7得到的7170是因为没分步取模，中间超大数计算出错啦）

二、高效解密m = c^d modn =2736^7543 mod8989 #

同样用快速幂，步骤如下：

1. 把指数7543转换成二进制（可以用除法取余法：7543÷2=3771余1，3771÷2=1885余1，依此类推，得到二进制111011000111）
2. 初始化结果res=1，当前底数base=2736 mod8989=2736
3. 从二进制的最低位到最高位遍历：
   • 如果当前位是1，就更新res = (res * base) mod8989
   • 不管当前位是0还是1，都更新base = (base * base) mod8989（平方后取模）
4. 遍历完所有位后，res就是解密后的明文，理论上应该等于100，刚好验证整个流程的正确性

举个简单例子帮你理解：比如算x^5 modn，5的二进制是101：

• 初始res=1，base=x
• 最低位是1：res=1*x=x，base=x²
• 中间位是0：res不变，base=(x²)²=x⁴
• 最高位是1：res=x*x⁴=x⁵，base=(x⁴)²=x⁸
• 最后res就是x^5 modn，全程没算过大数

这种方法的时间复杂度是O(log₂指数)，哪怕指数是几千几万，计算量都很小，完全不用处理天文数字。

备注：内容来源于stack exchange，提问作者exploring the web