CMWC (дополнительный умноженный с переносом) Matlab

Question

Цитировать Мистер.Марсалья о генерации большего количества параметров для PRWG CMWC:

"Тем, кто хочет еще больше пар 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. Стоит ли использовать другое программное обеспечение?

Answer 1

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

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