java - 素数の原始根が必要ですか?

Question

素数の原始根が必要です.このコードを書きましたが、ヒープサイズエラーがあり、101のような大きな数では機能しません.原始根を計算するための他のアイデアはありません.もしあれば助けてください.素数の原始根を計算するための他のアルゴリズムはありますか?

static ArrayList<ArrayList<Integer>> list1=new  ArrayList<ArrayList<Integer>>();

private static int primitiveRoot(int prim){

        ArrayList<ArrayList<Integer>>  number=new ArrayList<ArrayList<Integer>>();// this has all sequence numbers of x power of 0 to prime-1
        ArrayList<Integer> sublist=new ArrayList<Integer>();

        for (int x=2;x<prim;x++ ){
            sublist = new ArrayList<Integer>();
            for (int power=0;power<prim-1;power++){
                int i=(int)((Math.pow(x, power))%prim);
                sublist.add(i);     
            }

            number.add(sublist);

        }

        for (int j=0;j<number.size();j++){
                for (int m=0;m<list1.size();m++){
                    if(number.get(j).equals(list1.get(m)) ){// element of number arraylist compare to list1,equality means that we find one of primitive root
                        a=j+2;
                         break;
                    }
                }

        }

        return a;// this is primitive root

    }

list1 は arraylists の arraylist です。1 から素数 1 までの数値のすべての順列が含まれています。7 や 11 などの小さな素数に対してのみ機能します。ヒープ サイズを増やしましたが、効果はありませんでした。

Answer 1

ウィキペディアでアルゴリズムを見つけてみてください。

Java では、安全で高速なため、高速に計算するa^b mod nには を使用します。BigInteger

BigInteger a = new BigInteger("101");
BigInteger res = a.modPow(b, n);

Answer 2

import java.math.BigInteger;
import java.util.*;

public class PrimitiveRoot {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int p = in.nextInt();
        int m = p;
        if (isPrime(p)) {
            m = p - 1;
        }
        int primeRoot = 0;
        Map<Integer, Integer> primeFactor = getPrimeFactor(m);
        for (Map.Entry<Integer, Integer> map : primeFactor.entrySet()) {
            primeFactor.put(map.getKey(), m / map.getKey());
        }
        for (int i = 2; i <= m; i++) {
            boolean notPrimeRoot = false;
            Set<Integer> reminder = new HashSet<>();
            for (Map.Entry<Integer, Integer> map : primeFactor.entrySet()) {
                if(BigInteger.valueOf(i).modPow(BigInteger.valueOf(map.getValue()), BigInteger.valueOf(p)).equals(BigInteger.ONE))
                    notPrimeRoot = true;
            }
            if (!notPrimeRoot) {
                primeRoot = i;
                break;
            }
        }
        System.out.println("Prime Root is: " + primeRoot);
    }

    private static boolean isPrime(int p) {
        for (int i = 2; i <= Math.sqrt(p); i++) {
            if (p % i == 0) {
                return false;
            }
        }
        return true;
    }

    private static Map<Integer, Integer> getPrimeFactor(int p) {
        Map<Integer, Integer> map = new HashMap<>();
        while (p % 2 == 0) {
            insertToMap(2, map);
            p /= 2;
        }

        for (int i = 3; i <= Math.sqrt(p); i += 2) {
            while (p % i == 0) {
                insertToMap(i, map);
                p /= i;
            }
        }

        if (p > 2)
            insertToMap(p, map);
        return map;
    }

    private static void insertToMap(int i, Map<Integer, Integer> map) {
        if (map.get(i) != null) {
            map.put(i, map.get(i) + 1);
        } else {
            map.put(i, 1);
        }
    }
}