Тест на первичность Миллера-Рабина в Java

В настоящее время я работаю над Project Euler и думаю, что это может быть более интересным (и лучшим опытом обучения), если вы не просто перебортете все вопросы. На вопросе 3 он задает простые множители числа, и мое решение будет состоять в том, чтобы умножить число (используя другой алгоритм факторинга), а затем проверить факторы для простоты. Я придумал этот код для теста Miller-Rabin Primality (после тщательного исследования теста на соответствие), и он возвращает true для всего сложного нечетного числа, которое я вложил. Может ли кто-нибудь помочь мне разобраться, почему? Я думал, что правильно закодировал алгоритм.Тест на первичность Миллера-Рабина в Java

public static boolean isPrime(long num) 
{ 
if(num % 2 == 0) 
    return false; 
else 
{ 
    double d; 
    int r=0; 
    while((num-1) % Math.pow(2,r+1) == 0) 
     r++; 
    d = (num-1) % Math.pow(2,r); 
    int[] a = {2,3,5,7,11,13,17,23,31,62,73,1662803}; 
    boolean primality = true; 
    for(int k = 0; k < a.length; k++) 
    { 
     if((Math.pow(a[k],d)-1) % num != 0) 
     { 
      for(int s = 0; s < r-1; s++) 
      { 
       if((Math.pow(a[k],Math.pow(2,s)*d)+1) % num != 0) 
        primality = false; 

      } 
     } 
    } 
    return primality; 
}

источник

2013-06-13 Juan Sebastian Lozano

Вы пробовали отслеживать код? –

Это не относится к вашему коду, и я не претендую на большой опыт, но «факторинг числа (с использованием другого алгоритма факторинга)» - это более сложная проблема, чем определение простых чисел. Вы можете избежать грубого форсирования факторизации, получив список простых чисел. Самый простой способ получить список простых чисел (как и при тестировании) - использовать сито. – maybeWeCouldStealAVan

'Math.pow (a [k], d) -1)% num' - я бы сказал, что ваши удваиваются в диапазоне, где они могут представлять каждое целое число в этом диапазоне. –

Учитывая num > 3, вы хотите: d, r s.t. pow(2,r) * d = num - 1, where d is odd.

Вы эффективно считаете конечные нули от num - 1, чтобы устранить факторы 2. Однако после этого цикла вы знаете, что pow(2,r) является фактором num - 1. Следовательно:

d = (num-1) % Math.pow(2,r);

всегда будет давать: d = 0. Я подозреваю, что вы хотели заменить % (mod) с / (div) здесь; в противном случае Math.pow(a[k],d)-1 всегда будет давать (0), и внутренний цикл никогда не будет выполнен.

Как указывали другие, некоторые простые утверждения или утверждения трассировки нашли бы эти ошибки. Я думаю, у вас есть другие проблемы, такие как переполнение целого числа. Цикл для тестирования против a[] кандидатов (тест a-SPRP) выглядит совершенно неправильно для меня.

Возможно, у вас есть алгоритм от Wikipedia, я предпочитаю более подробную ссылку в The Handbook of Applied Cryptography: 4.2.3: Миллер-Рабина тест, алгоритм: 4,24.

источник

2013-06-13 11:41:34

Спасибо за этот очень информативный ответ :) Я рассмотрю предоставленные вами ресурсы, поскольку они кажутся чрезвычайно полезными, и в следующий раз будет более осторожным использование операторов трассировки (теперь, когда я знаю, что это такое). –

@ JuanSebastianLozanoMuñoz - поскольку вы сталкиваетесь с проблемами Project Euler, я думал, что вы можете найти эффективный тест Миллера-Рабина, поэтому у меня есть фрагмент для вас [здесь] (http://pastebin.com/8GJC5s61). –

Вау, большое вам спасибо :) Это определенно поможет мне на пути через проблемы с PE. –

Тест на первичность Миллера-Рабина в Java

ответ

Смежные вопросы