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是一个数组列表的数组列表，它包含1到素数1之间的所有数字排列。它只适用于像7或11这样的小素数。我增加了堆大小，但没有效果。

Answer 1

Try wikipedia找到算法。

在 Java 中，计算 a^b mod n 的快速方法是使用 BigInteger，因为它安全且快速。

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