编写计算原根的Java代码
时间: 2024-02-06 12:13:08 浏览: 28
以下是一个简单的 Java 代码,用于计算一个大素数的原根:
```java
import java.util.*;
public class PrimitiveRoot {
public static int power(int a, int b, int mod) {
int result = 1;
while (b > 0) {
if ((b & 1) == 1) {
result = (result * a) % mod;
}
a = (a * a) % mod;
b >>= 1;
}
return result;
}
public static int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
public static boolean isPrimitiveRoot(int a, int p) {
int phi = p - 1;
for (int i = 2; i <= Math.sqrt(phi); i++) {
if (phi % i == 0) {
if (power(a, i, p) == 1 || power(a, phi / i, p) == 1) {
return false;
}
}
}
return true;
}
public static int findPrimitiveRoot(int p) {
if (p == 2) {
return 1;
}
ArrayList<Integer> factors = new ArrayList<Integer>();
int phi = p - 1, n = phi;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
factors.add(i);
while (n % i == 0) {
n /= i;
}
}
}
if (n > 1) {
factors.add(n);
}
for (int res = 2; res <= p; res++) {
boolean ok = true;
for (int factor : factors) {
if (power(res, phi / factor, p) == 1) {
ok = false;
break;
}
}
if (ok) {
return res;
}
}
return -1;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("请输入一个大素数p:");
int p = scanner.nextInt();
int root = findPrimitiveRoot(p);
if (root != -1) {
System.out.println("模" + p + "的原根是:" + root);
} else {
System.out.println("找不到模" + p + "的原根!");
}
}
}
```
运行代码后,输入一个大素数 p,程序将计算并输出该大素数的原根。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)