Странные мысли иногда приходят ... Пусть есть последовательность бит заданная выражением: X[n+k] = A[k-1]*X[n+k-1] xor ... xor A[1]*X[n+1] xor X[n] (A[k-1]...A[1] могут принимать значения 0 или 1, A[k] = A[0] = 1) а также заданы значения её первых k элементов: X[k-1] ... X[0] Так как у нас X принимает только значения 0 и 1, то справедливо равенство X^z = X. Возведём все X в i-ю степень приняв n=0: X[k]^k = A[k-1]*X[k-1]^(k-1) xor ... xor A[1]*X[1]^1 xor X[0]^0 Если возвести это выражение в квадрат, то получим: X[k]^2k = A[k-1]*X[k-1]^(2k-2) xor ... xor A[1]*X[1]^2 xor X[0]^0 (так как A принимат значения 0 или 1, то A*A = A; а все элементы произведения вида A*X^i*A[j]*X[j]^j=A[j]*X[j]^j*A*X^i при i<>j сокращаются, так как A*B xor B*A = 0) Используя соотношение X^z=X вернёмся к индексам: X[2k] = A[k-1]*X[2k-2] xor ... xor A[1]*X[2] xor X[0] (здесь по идее должны быть X[k],X[k-1] и так далее, но этот набор X имеет точно такие же решения что и исходный) Данное выражение позволяет нам находить четные элементы последовательности не используя нечётные элементы (это же выражение может быть использовано для нахождения нечётных элементов последовательности без использования чётных). Если не переходить назад к индексам, а еще раз возвести в квадрат, то можно избавиться от элементов, номера которых не делятся на 4. Продолжая данную операцию можно сделать так, чтобы остались только элементы со степенью кратной 8,16,32 и так далее. Пример X4 = 1*X3 xor 0*X2 xor 0*X1 xor X0 = X3 xor X0 X0 = 1 X1 = 0 X2 = 0 X3 = 0 X4 = X3 xor X0 = 0 xor 1 = 1 X5 = X4 xor X1 = 1 xor 0 = 1 X6 = X5 xor X2 = 1 xor 0 = 1 X7 = X6 xor X3 = 1 xor 0 = 1 X8 = X7 xor X4 = 1 xor 1 = 0 X9 = X8 xor X5 = 0 xor 1 = 1 X10 = X9 xor X6 = 1 xor 1 = 0 X11 = X10 xor X7 = 0 xor 1 = 1 X12 = X11 xor X8 = 1 xor 0 = 1 X13 = X12 xor X9 = 1 xor 1 = 0 X14 = X13 xor X10 = 0 xor 0 = 0 X15 = X14 xor X11 = 0 xor 1 = 1 = X0 X16 = X15 xor X12 = 1 xor 1 = 0 = X1 X17 = X16 xor X13 = 0 xor 0 = 0 = X2 X18 = X17 xor X14 = 0 xor 0 = 0 = X6 У нас получилась последовательность длиной в 15 элементов: 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 А начиная с X15 данная последовательность повторяется. Возведём уравнение последовательности в 8 степень: (X[4]^4)^8 = (X[3]^3 xor X[0]^0)^8 X32 = X24 xor X0 То есть, чтобы получить 32й элемент, нужно проXORить 24й и 0й элементы. Запишем первые 32 элемента последовательности (по 8 штук в байте): Код (Text): 1 0 0 0 1 1 1 1 (0) 0 1 0 1 1 0 0.1 (1) 0 0 0 1 1 1 1 0 (2) 1 0 1 1 0 0.1 0 (3) Делая операцию XOR над строками найдем продолжение: 0 0 1 1 1 1 0 1 (4) = (0) xor (3) 0 1 1 0 0.1 0 0 (5) = (1) xor (4) 0 1 1 1 1 0 1 0 (6) = (2) xor (5) 1 1 0 0.1 0 0 0 (7) = (3) xor (6) ... PS: Возможно что в рассуждениях есть баги, но судя по примеру и нескольким последовательностям проверенным программой, данный метод работает.
Black_mirror Интересное наблюдение, к нему еще бы какое-нибудь красивое доказательство В твоих выкладках меня смущает следующее: 1) Почему здесь можно степень перенести в индекс? Обоснование по меньшей мере неочевидно. 2) В таких случаях обычно пишут определение нулевой степени, тем более, когда оно не каноническое (как в твоем случае). По-видимому у тебя x^0 = x^1 для всех x \in {0,1} Кстати, если не ошибаюсь, твое наблюдение будет справедливо и для общего случая конечного поля, например если брать сложение и умножение mod 3. А тогда рассуждение уже не пройдет В общем надо искать доказательство... P.S. Некоторые товарищи в свое время помнится активно выступали за увеличение количества математических тем. Вот, пожалуйста
Stiver Попробую пойти другим путём: X[n] = XOR[i=1..k](A*X[n-i]) A,X могут принимать значения 0 или 1 A[k]=1 Выпишим выражения для X[n],...,X[n-k]: (для наглядности коэффициенты A я писать не буду, но нужно иметь ввиду что присутствие X[n-1],...,X[n-k+1] не обязательно) 0. X[n] xor X[n-1] xor ... xor X[n-k+1] xor X[n-k] = 0 1. X[n-1] xor X[n-1-1] xor ... xor X[n-1-k+1] xor X[n-1-k] = 0 .... k-1. X[n-k+1] xor X[n-k+1-1] xor ... xor X[n-k+1-k+1] xor X[n-k+1-k] = 0 k. X[n-k] xor X[n-k-1] xor ... xor X[n-k-k+1] xor X[n-k-k] = 0 Если проXORить все эти выражения, то останутся только элементы на главной диагонали: X[n] xor X[n-1-1] xor ... xor X[n-k+1-k+1] xor X[n-k-k] = 0 или X[n] = X[n-1*2] xor ... xor X[n-k*2+1*2] xor X[n-k*2] В общем виде: X[n] = XOR[i=1..k](A*X[n-2i]) Проведя такую операцию еще раз получим: X[n] = XOR[i=1..k](A*X[n-4i]) Можно записать что: X[n] = XOR[i=1..k](A*X[n-i*2^s]) Можно ли умножать i на что либо не кратное степени 2 я не знаю, но мне кажется что нет.
То, что ты привел, называется рекуррентным соотношением. Про них много чего известно (я имею в виду, может быть твое наблюдение имеет под собой строгий математический контекст).
Даже больше скажу - это типичный регистр сдвига с простейшей функцией обратной связи (сумма по модулю 2 значений, снимаемых с некоторых ячеек). Про них много известно (начиная с Голомба), они активно используются в криптографии и не только.
Black_mirror Не совсем понимаю, давай посмотрим на примере. Возьмем k=2, A[1]=0, A[2]=1 - то есть X[n]=X[n-2]. X[n]+X[n-2]=0 X[n-1]+X[n-3]=0 X[n-2]+X[n-4]=0 Вместо XOR я пишу + и подразумеваю сложение по mod 2. Сложив эти равенства получим X[n]+X[n-1]+X[n-3]+X[n-4]=0 то есть не только главную диагональ. Просто ты приравнял все A единице и поэтому упустил из виду, что коэффициенты одинаковых элементов X[n-i] в разных строках будут разными. crypto Обязательно имеет, проблема только в его нахождении и "красивой" записи. По-видимому нужно как-то аргументировать через производящую функцию (надеюсь правильный термин), но не соображу пока как
Black_mirror Продолжение (благо обеденный перерыв ): Идея со сложением правильная, только нужно каждую строку сначала на A умножить. Пусть X[n] = SUM_{i=1..k}(A*X[n-i]), A[0]=1 (зачем нужно условие A[k]=1 я не понял) Тогда SUM_{i=0..k}(A*X[n-i]) = 0 и соответственно SUM_{m=0...k}(A[m]*SUM_{i=0..k}(A*X[n-m-i])) = 0 Теперь собираем все X с одинаковым индексом SUM_{m=0...2k}(X[n-m]*SUM_{0<=i,j и (m-k)<=i,j и i+j=m}(A*A[j])) = 0 Так как SUM_{0<=i,j и (m-k)<=i,j и i+j=m}(A*A[j]) принимает значения A[m/2] для четных m и 0 для нечетных, можно упростить SUM_{m=0...k}(X[n-2*m]*A[m]) = 0 Что и требовалось доказать. Теперь все то же самое для общего случая
