Порядок роста теста Fermat в SICP

Question

Процедура fermat-test, представленная Структура и интерпретация компьютерных программ имеет порядковый номер роста, который был проверен мной и многими другими людьми эксперименты.

Что меня смущает примитивная процедура random в ее определении. Означает ли это, что порядок роста random составляет не более тета log (n)? После некоторой работы по поиску я все еще не уверен, можно ли написать генератор псевдослучайных чисел, порядок роста которого не больше, чем theta log (n).

Вот код:

(define (fermat-test n) 
    (define (try-it a) 
    (= (expmod a n n) a)) 
    ; Wait a second! What's the order of growth of `random`? 
    (try-it (+ 1 (random (- n 1))))) 

, где expmod имеет тета-из-журнала (п) порядок роста:

(define (expmod base exp m) 
    (cond ((= exp 0) 1) 
     ((even? exp) 
     (remainder (square (expmod base (/ exp 2) m)) 
        m)) 
     (else 
     (remainder (* base (expmod base (- exp 1) m)) 
        m)))) 

Не могли бы вы объяснить мне это?

• Если такой генератор псевдослучайных чисел существует, пожалуйста, покажите мне, как это работает.
• Если такой генератор псевдослучайных чисел не существует, скажите, пожалуйста, как fermat-test по-прежнему имеет порядок роста (т).

Answer 1

Маленькая теорема Ферма гласит:

Если п простое число и любое положительное целое число меньше п, то возведенное в NTH мощность соответствует a modulo n.

Так что идея здесь в том, что дано некоторое число п, мы выбираем любое число таким образом, что < п, а затем вычислим Выражение в ^п% п == , Если это выражение возвращает false, то знает, что n не является простым. Однако, если это выражение возвращает true, то есть хороший шанс, что n является простым.

Из этой теоремы, мы можем получить функцию, что вы, перечисленных выше:

(define (fermat-test n) 
    (define (try-it a) 
    (= (expmod a n n) a)) 
    (try-it (+ 1 (random (- n 1))))) 

В вашем посте, вы дали понять, что вы понимаете Q (Л.Г. п) рост & Асимптотическая временная сложность получается из функции expmod, поэтому нам просто нужно понять, как random работает на Схеме, чтобы узнать, является ли ее порядок роста постоянным или нет.

На схеме вы можете generate pseudorandom numbers using the random function.Из документации схемы, мы знаем, что

Текущая реализация является «вычитать-с-нести» генератор случайных чисел, основанный на алгоритме из нового класса генераторов случайных чисел, Джордж Marsaglia и Ариф Zaman, Летопись прикладной вероятности, т. 1, № 3, 1991

Если вы заинтересованы в чтении больше об этой конкретной реализации, you're more than welcome to read more about them, но важная часть здесь, чтобы понять, что мы в состоянии генерировать псевдослучайные числа в постоянном времени с постоянной поэтому, таким образом, порядок роста не изменяется при этом вызове функции.

Как быстро отвлечься, если вы искренне заинтересованы в том, чтобы больше узнать о генераторах псевдослучайных чисел, в частности, в документации по Схему есть точка, указывающая на то, что есть, вероятно, более эффективные и эффективные генераторы, помимо его текущего алгоритма общего назначения - так что вы можете также проверить другие алгоритмы генератора.