5^18 mod 47?
时间: 2023-11-24 10:07:42 浏览: 32
可以使用快速幂算法来计算。首先将指数18转换为二进制形式,即18=10010。然后,从右到左依次考虑每一位上的数字,如果是1,则将底数5乘以当前的幂次后取模,如果是0,则将底数5的当前幂次取模。具体步骤如下:
1. 5^1 mod 47 = 5
2. 5^2 mod 47 = 25
3. 5^4 mod 47 = (5^2)^2 mod 47 = 25^2 mod 47 = 36
4. 5^8 mod 47 = (5^4)^2 mod 47 = 36^2 mod 47 = 29
5. 5^16 mod 47 = (5^8)^2 mod 47 = 29^2 mod 47 = 20
6. 5^18 mod 47 = 5^(16+2) mod 47 = (5^16)*(5^2) mod 47 = 20*25 mod 47 = 30
因此,5^18 mod 47 = 30。
相关问题
5^8 mod 47?
首先,我们可以使用费马小定理来简化计算。因为 47 是质数,所以根据费马小定理,如果 p 是质数且 a 不是 p 的倍数,则 a^(p-1) ≡ 1 (mod p)。因此,我们可以得到 5^46 ≡ 1 (mod 47)。
接下来,我们可以使用指数的二进制表示方法来快速计算 5^8 mod 47。将指数 8 转换为二进制为 1000,因此:
5^8 = 5^(2^3) = (5^2)^4 = 25^4
现在,我们可以使用平方乘法算法来计算 25^4 mod 47。将 4 转换为二进制为 100,因此:
25^2 = 625 ≡ 18 (mod 47)
25^4 = (25^2)^2 ≡ 18^2 ≡ 324 ≡ 27 (mod 47)
因此,5^8 ≡ 27 (mod 47)。
Given that 5 is a primitive element modulo 47, solve 10 ≡ 5 a mod 47 by using Shank’s algorithm
Shank's algorithm is an algorithm for solving the discrete logarithm problem. In this case, we want to solve the equation 10 ≡ 5^a (mod 47).
First, we need to find the order of 5 modulo 47. Since 47 is a prime number, we know that any integer a such that 1 ≤ a ≤ 46 is a primitive element modulo 47 if and only if gcd(a,47)=1 and a^(46) ≡ 1 (mod 47). Since 5 is a primitive element modulo 47, we know that the order of 5 modulo 47 is 46.
Next, we need to compute the values of 5^0, 5^1, 5^2, ..., 5^22 mod 47 and store them in a table. We can use the repeated squaring method to compute these values efficiently. For example:
5^0 ≡ 1 (mod 47)
5^1 ≡ 5 (mod 47)
5^2 ≡ 25 (mod 47)
5^3 ≡ 43 (mod 47)
5^4 ≡ 38 (mod 47)
5^5 ≡ 6 (mod 47)
5^6 ≡ 30 (mod 47)
5^7 ≡ 41 (mod 47)
5^8 ≡ 19 (mod 47)
5^9 ≡ 24 (mod 47)
5^10 ≡ 37 (mod 47)
5^11 ≡ 45 (mod 47)
5^12 ≡ 7 (mod 47)
5^13 ≡ 35 (mod 47)
5^14 ≡ 31 (mod 47)
5^15 ≡ 18 (mod 47)
5^16 ≡ 33 (mod 47)
5^17 ≡ 44 (mod 47)
5^18 ≡ 3 (mod 47)
5^19 ≡ 15 (mod 47)
5^20 ≡ 32 (mod 47)
5^21 ≡ 14 (mod 47)
5^22 ≡ 42 (mod 47)
Now, we can use Shank's algorithm to solve the equation 10 ≡ 5^a (mod 47). We can rewrite this equation as 5^a ≡ 10 (mod 47). We want to find a such that 0 ≤ a ≤ 45.
We start by dividing the range [0, 45] into two equal parts: [0, 22] and [23, 45]. We compute 10 × 5^-0 ≡ 10 (mod 47) and 5^0, 5^1, 5^2, ..., 5^22 mod 47 using the table. We find that 10 ≡ 10 (mod 47) and 10 ≢ 1, 5, 25, 43, 38, 6, 30, 41, 19, 24, 37, 45, 7, 35, 31, 18, 33, 44, 3, 15, 32, 14, 42 (mod 47). Therefore, 10 is not in the first half of the table.
Next, we compute 10 × 5^-23 ≡ 39 (mod 47) and 5^23, 5^24, 5^25, ..., 5^45 mod 47 using the table. We find that 39 ≢ 1, 5, 25, 43, 38, 6, 30, 41, 19, 24, 37, 45, 7, 35, 31, 18, 33, 44, 3, 15, 32, 14, 42 (mod 47). Therefore, 10 is not in the second half of the table.
Since we have exhausted all the possibilities, we conclude that there is no solution to the equation 10 ≡ 5^a (mod 47).
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://img-home.csdnimg.cn/images/20210720083646.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)
![](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)