Факторизация Брента-Полларда: Каковы правильные индексы черепахи и зайца в алгоритме нахождения цикла Брента? - PullRequest
Новая
       43

Факторизация Брента-Полларда: Каковы правильные индексы черепахи и зайца в алгоритме нахождения цикла Брента?

1 голос
/ 09 мая 2019

Некоторое время назад я перенес эту реализацию Python алгоритма Полларда-Брента на Clojure.Это работает, и работает быстро тоже;это не проблема.И когда ему даны одинаковые неслучайные начальные значения и пошаговые функции, он точно воспроизводит позиции зайца и черепахи в коде Python.

Но пока я работал над этим, я не мог не заметить, что черепахаи заяц двигался не совсем так, как я ожидал, основываясь на описании алгоритма в статье Брента (или в Википедии, или в любой другой ссылке на выбор).

В частности, после того, как черепаха телепортировалась вположение зайца, заяц шагает вперед на distance количество шагов, а затем шагов на дополнительное distance количество шагов.Кроме того, в алгоритме Брента-Полларда также важны промежуточные значения;однако этот код сохраняет только шаги второго «пути» зайца.

Вот строки 6-18 кода Python с моими комментариями: 

    while g==1:    

        # Tortoise (x) moves to hare (y)         
        x = y 

        # Hare (y) moves ahead by r steps
        for i in range(r):
            y = ((y*y)%N+c)%N

        k = 0

        # Hare (y) moves ahead by another r steps, 
        # with checkpoints at every m steps (the checkpoints are 
        # for the factorization; not part of Brent's cycle-finding algo proper)
        while (k<r and g==1):
            ys = y
            for i in range(min(m,r-k)):
                y = ((y*y)%N+c)%N
                q = q*(abs(x-y))%N
            g = gcd(q,N)
            k = k + m

Сегодня я возвращался к своему коду и решил проверить его наверняка, выполнив макет упрощенного кода.Версия для показа индексов.Это индексы, заданные текущим кодом:

Текущая версия : 

Distance: 1
Tortoise at: 1
Hare starts at: 2
Hare path: [3]
Distance: 2
Tortoise at: 3
Hare starts at: 5
Hare path: [6 7]
Distance: 4
Tortoise at: 7
Hare starts at: 11
Hare path: [12 13 14 15]
Distance: 8
Tortoise at: 15
Hare starts at: 23
Hare path: [24 25 26 27 28 29 30 31]
Distance: 16
Tortoise at: 31
Hare starts at: 47
Hare path: [48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63]
Distance: 32
Tortoise at: 63
Hare starts at: 95
Hare path: [96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127]

Между тем, я ожидаю, что алгоритм сделает:

Ожидаемый результат : 

Distance: 1
Tortoise at: 1
Hare path: [2]
Distance: 2
Tortoise at: 2
Hare path: [3 4]
Distance: 4
Tortoise at: 4
Hare path: [5 6 7 8]
Distance: 8
Tortoise at: 8
Hare path: [9 10 11 12 13 14 15 16]
Distance: 16
Tortoise at: 16
Hare path: [17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32]
Distance: 32
Tortoise at: 32
Hare path: [33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64]

Несмотря на то, что «ожидаемая» версия лучше читается в Clojure при включении в алгоритм, она в среднем вдвое дольше (что имеет смысл,глядя на индексы).

Мои вопросы:

  1. Является ли мой ожидаемый вывод "канонической" версией алгоритма Брента?
  2. Является ли текущая версия вернойреализация алгоритма Брента?
  3. Почему текущая версия работает, хотя путь зайца не содержит полностью последовательных индексов?
...