Преобразование теста Baillie – PSW из Python в Java - PullRequest
Новая
       27

Преобразование теста Baillie – PSW из Python в Java

0 голосов
/ 10 марта 2019

Я пытаюсь преобразовать реализацию теста примитивности Baillie – PSW из Python в Java. Я думаю, что я сделал это в основном правильно, но есть часть, где ответы начинают отклоняться, и в результате весь алгоритм не может обнаружить простые числа. Это отклонение начинает возникать, когда алгоритм начинает использовать критерий Лукаса.

Вот оригинальный код для части этого теста (часть этого репо ): 

def U_V_subscript(k, n, U, V, P, Q, D):
k, n, U, V, P, Q, D = map(int, (k, n, U, V, P, Q, D))
digits = list(map(int, str(bin(k))[2:]))
subscript = 1

for digit in digits[1:]:

    U, V = U*V % n, (pow(V, 2, n) - 2*pow(Q, subscript, n)) % n

    subscript *= 2
    if digit == 1:

        if not (P*U + V) & 1:
            if not (D*U + P*V) & 1:

                U, V = (P*U + V) >> 1, (D*U + P*V) >> 1
            else:
                U, V = (P*U + V) >> 1, (D*U + P*V + n) >> 1
        elif not (D*U + P*V) & 1:
            U, V = (P*U + V + n) >> 1, (D*U + P*V) >> 1
        else:
            U, V = (P*U + V + n) >> 1, (D*U + P*V + n) >> 1
        subscript += 1
        U, V = U % n, V % n

return U, V

А вот мой аналог Java: 

static long[] UVSubscript(long k, long n, long U, long V, long P, long Q, long D){
    BitSet bitDigits = convert(k);
    long subscript = 1;
    for (int i = bitDigits.length()-2; i >= 0; i--) {
        U = U*V % n;
        V = (powerModulus(V, 2, n) - 2*powerModulus(Q, subscript, n)) % n;

        subscript *= 2; 

        if (bitDigits.get(i)){


            if (((P * U + V) & 1) == 0){
                if (((D*U + P*V) & 1) == 0){

                     U = (P*U + V) >> 1;
                     V = (D*U + P*V) >> 1;
                }else{
                     U = (P*U + V) >> 1;
                     V = (D*U + P*V + n) >> 1;
                }
            } else if (((D * U + P * V) & 1) == 0){
                U = (P*U + V + n) >> 1;
                V = (D*U + P*V) >> 1;
            }else{
                U = (P*U + V + n) >> 1;
                V = (D*U + P*V + n) >> 1;
            }

            subscript += 1;
            U = U % n;
            V = V % n; 

        }
    }
    return new long[]{U, V};
}

Может кто-нибудь помочь мне? Вот исполняемая версия всего скрипта Python , если кому-то интересно. И вот вставка всего моего перевода на Java .

PS Если кто-нибудь знает о готовой Java-реализации теста примитивности Baillie – PSW, я мог бы просто использовать это!

Ответы [ 2 ]

0 голосов
/ 15 июня 2019

Если вы заметили, что в цикле многократно используются значения P * U + V и D * U + P * V, есть место для улучшения.Вам вообще не нужна переменная oldU, упомянутая в принятом ответе.Просто вычислите эти два в начале цикла и используйте их позже как для условных выражений, так и для вычислений новых значений U и V.Вы выигрываете по обоим показателям: использование отдельного значения гарантирует, что назначения больше не будут параллельными, и вы сохраняете пару ненужных пересчетов: 

if (k.testBit(i)) {
  val PU_V = P * U + V
  val DU_PV = D * U + P * V

  if (IsEven(PU_V)) {
    if (IsEven(DU_PV)) {
      U = PU_V shr 1
      V = DU_PV shr 1
    }
    else {
      U = PU_V shr 1
      V = (DU_PV + n) shr 1
    }
  }
  else if (IsEven(DU_PV)) {
    U = (PU_V + n) shr 1
    V = DU_PV shr 1
  }
  else {
    U = (PU_V + n) shr 1
    V = (DU_PV + n) shr 1
  }

  subscript++
  U %= n
  V %= n
}

(это происходит в Котлине, а не в Java, но это нене имеет никакого значения.)

0 голосов
/ 10 марта 2019

Я вижу, как происходят отклонения в вашем переводе этой строки и трех подобных: 

U, V = (P*U + V + n) >> 1, (D*U + P*V + n) >> 1

Это параллельные присваивания в Python, то есть V вычисляется со значением old U до выражения. Но в вашем переводе: 

U = (P*U + V + n) >> 1;
V = (D*U + P*V + n) >> 1;

V рассчитывается с использованием нового значения U. Лучший перевод может быть следующим: 

long old_U = U;
U = (P*U + V + n) >> 1;
V = (D*old_U + P*V + n) >> 1;

И снова, это также необходимо сделать для других параллельных назначений.

...