BigIntegers к власти BigIntegers

Question

Я пытаюсь реализовать в Java алгоритм Ферма, Миллера-Рабина или AKS с использованием класса BigInteger.

Я думаю, что у меня реализован тест Ферма , за исключением того, что класс BigInteger не позволяет привести BigIntegers к силе BigIntegers (можно взять только BigIntegers к силе примитивных целых). Есть ли способ обойти это?

Проблемная строка обозначена в моем коде:

public static boolean fermatPrimalityTest(BigInteger n)
{
    BigInteger a;
    Random rand = new Random();
    int maxIterations = 100000;

    for (int i = 0; i < maxIterations; i++) {
        a = new BigInteger(2048, rand);

        // PROBLEM WITH a.pow(n) BECAUSE n IS NOT A BigInteger
        boolean test = ((a.pow(n)).minus(BigInteger.ONE)).equals((BigInteger.ONE).mod(n));

        if (!test)
            return false;
    }

    return true;
}

Answer 1

Я думаю BigInteger.modPow может быть то, что вы ищете.Обратите внимание на «мод m» в тесте Ферма.

Answer 2

Один из тестов простоты встроен в BigInteger.isProbablePrime().Не уверен, какой из них вам нужно посмотреть на источник.

Кроме того, вы можете увеличить число до степени, умножив.Например: 2^100 = 2^50 * 2^50.Так что вытаскивайте кусочки вашего BigInteger питания и петли, пока вы не израсходуете его.Но вы уверены, что не хотите использовать BigInteger.modPow(), что занимает BigInteger с?Похоже, что вы, на основании вашего теста.

Answer 3

Вы должны будете реализовать свой собственный метод pow (). Посмотрите на источники BigInteger.pow () в качестве отправной точки.