Блог

Процитировать мистера Марсалья о генерации дополнительных параметров для CMWC PRNG:

«Тем, кто хочет получить еще больше пар r, a, нужно будет найти простые числа вида p = ab ^ r 1, для которых b = 2 ^ 32-1 является примитивным корнем».

Мой вопрос заключается в методе, который я должен использовать для этого. Особенно с очень большими простыми числами. Это то, что я написал в MATLAB:

 isPrimitiveRoot = 0;
goodParameters = zeros(1,vectorSize);
nextFreeSpace = 1;
r = 1;
b = 2^32-1;
for a=0:2^32-1
  isPrimitiveRoot = 0;
  number = a*b^r 1;
  if(isprime(number))
    p = number;
    phi_p = p - 1;
    factors = factor(phi_p);
    isPrimitiveRoot = 1;
    for i=1:length(factors)
      if(isprime(factors(i)))
        if(mod(b^(phi_p/factors(i)),p)==1)
          isPrimitiveRoot = 0;
        end
      end
    end
  end
  if(isPrimitiveRoot)
    goodParameters(nextFreeSpace) = a;
    disp([nextFreeSpace a]);
    nextFreeSpace = nextFreeSpace   1;
  end
end
  

Я делаю это, потому что шаги по поиску хороших a параметров для определенного r запаздывания следующие:

1. Докажите, что p = a*b^r 1 является простым
2. Докажите, что b это примитивный корень из p . Для этого вам нужно оценить простые множители p-1 и проверить это b^((p-1)/p_i) =/= 1 (mod(p)) для всех p_i простых множителей p-1 .

Теперь довольно очевидно, почему скрипт не работает. Я выбрал b = 2^32 -1 и задержку r = 1 , чтобы упростить задачу. Но оценка b^(phi_p/factors(i)) приводит к слишком большим числам ( Inf ).

1. Что я должен делать вместо этого?
2. Должен ли я использовать другое программное обеспечение?
3. Существует ли другой алгоритм для проверки примитивных корней?

Ну, всегда можно использовать мой набор инструментов vpi в matlab. Хотя я не предоставил инструмент для явной генерации / тестирования примитивного корня, vpi обладает способностью работать с произвольно большими целыми числами, а также функцией powermod для выполнения большей части работы.

Однако я укажу, что выполнение простого цикла перебора через 2 ^ 32 элемента займет некоторое время, независимо от инструмента.