tft每日頭條

 > 生活

 > 計算器中怎樣計算一個數的n次方

計算器中怎樣計算一個數的n次方

生活 更新时间:2024-08-08 07:14:44

計算器中怎樣計算一個數的n次方?在密碼學中我們經常會看到 這樣的計算(如RSA, Diffie Hellman key exchange), 而且往往這個n次幂很大. 如何快速對一個數的n 次方求mod, 很可能決定一個加密算法的性能. 下面我們會一步步引導大家來思考這個問題,我來為大家講解一下關于計算器中怎樣計算一個數的n次方?跟着小編一起來看一看吧!

計算器中怎樣計算一個數的n次方(快速計算一個數n次方mod)1

計算器中怎樣計算一個數的n次方

在密碼學中我們經常會看到 這樣的計算(如RSA, Diffie Hellman key exchange), 而且往往這個n次幂很大. 如何快速對一個數的n 次方求mod, 很可能決定一個加密算法的性能. 下面我們會一步步引導大家來思考這個問題

  1. 快速求

舉例 如果要計算 5^128 我們可以 1 5^2 2 5^4 3 5^8 4 5^16 5 5^32 6 5^64 7 5^128 如果需要計算5^129 我們隻需要 5^128 * 5

2 快速求

先來看一個定理 對左邊式子做分解很容易得到右邊的式子

有了上面的定理結合快速求幂的方法我們再來看

舉例我們要計算2^512 mod 31 首先找到大于31的2整次幂 2^5 2^5 == 31 1 所以 2^512 可以改寫 (31 1)^102 * 4 mod 31 == 1^102 * 4 mod 31 == 4 我們再看一個例子 3^480 mod 10 首先找到大于10 的3整次幂3^3 3^3 == 2*10 7 所以3^480 可以改寫7^160 mod 10 同理可以改寫9^80 同理可以改寫1^40 == 1

後續博主可能會連續寫一些關于密碼學, 同态加密方面的文章 希望大家關注

,

更多精彩资讯请关注tft每日頭條,我们将持续为您更新最新资讯!

查看全部

相关生活资讯推荐

热门生活资讯推荐

网友关注

Copyright 2023-2024 - www.tftnews.com All Rights Reserved