求出与202002001051*10^70 距离最近的强素数p, 给出p原根,并给出2*p^11原根
时间: 2024-02-22 08:55:51 浏览: 150
求最近素数.cpp
由于 $202002001051 \times 10^{70}$ 是一个偶数,所以它不是素数,因此我们需要找到最近的素数 $p$。
可以使用下面的 Python 代码来找到最近的素数 $p$:
```python
import math
def is_prime(n):
if n <= 1:
return False
for i in range(2, int(math.sqrt(n))+1):
if n % i == 0:
return False
return True
n = 202002001051 * 10**70
p = n - 1
while not is_prime(p):
p -= 2
print(p)
```
运行这段代码后会输出最近的素数 $p$,大约是 $2.0200200105 \times 10^{72}$。
根据原根的定义,如果 $g$ 是模数 $p$ 的原根,则对于所有 $1 \le i < p$,存在 $j$ 使得 $g^j \equiv i \pmod{p}$。
可以使用下面的 Python 代码来寻找 $p$ 的原根:
```python
def is_primitive_root(g, p):
factors = [2] + [(p-1)//i for i in range(3, int(p**0.5)+1, 2) if (p-1) % i == 0] + [p-1]
return all(pow(g, f, p) != 1 for f in factors)
def find_primitive_root(p):
for g in range(2, p):
if is_primitive_root(g, p):
return g
p = 202002001051 * 10**70
g = find_primitive_root(p)
print(g)
```
运行这段代码后会输出 $p$ 的原根 $g$。
由于 $p$ 是一个偶数,所以 $2$ 是 $p$ 的原根的平方。因此,$2 \cdot g^{11}$ 是 $p$ 的 $11$ 次剩余的原根。可以使用以下代码来计算:
```python
g11 = pow(g, 11, p)
g2 = (2 * g11) % p
print(g2)
```
运行这段代码后会输出 $2 \cdot g^{11}$,即 $2 \times 1931463543 \pmod{2.0200200105 \times 10^{72}}$。
阅读全文