rsa算法中,e的逆元怎么求
时间: 2024-05-13 10:14:44 浏览: 20
在 RSA 算法中,e 的逆元指的是一个整数 d,满足 $d \cdot e \equiv 1 \pmod{\varphi(n)}$,其中 $n$ 是 RSA 算法中的模数,$\varphi$ 是 Euler Totient 函数。
求 e 的逆元可以使用扩展欧几里得算法来实现。假设我们要求 $e^{-1} \pmod{\varphi(n)}$,我们可以执行以下步骤:
1. 对 $\varphi(n)$ 和 $e$ 进行扩展欧几里得算法,求出 $\gcd(\varphi(n), e)$ 和对应的 Bézout 系数 $x$ 和 $y$。
2. 如果 $\gcd(\varphi(n), e) \neq 1$,则 $e$ 没有逆元。否则,$x$ 就是 $e$ 的模 $\varphi(n)$ 的逆元,即 $e^{-1} \equiv x \pmod{\varphi(n)}$。
例如,假设我们要求 $e = 17$ 在模 $\varphi(n) = 240$ 下的逆元。我们可以执行以下步骤:
1. 对 $\varphi(n) = 240$ 和 $e = 17$ 进行扩展欧几里得算法:
```
240 = 17 * 14 + 2
17 = 2 * 8 + 1
2 = 1 * 2 + 0
```
因此,$\gcd(\varphi(n), e) = 1$,并且我们有:
```
1 = 17 - 2 * 8
= 17 - 2 * (240 - 17 * 14)
= 29 * 17 - 2 * 240
```
因此,$e^{-1} \equiv 29 \pmod{\varphi(n)}$,即 $17^{-1} \equiv 29 \pmod{240}$。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)