ТОП авторов и книг ИСКАТЬ КНИГУ В БИБЛИОТЕКЕ
Через некоторое время Уоте
рхаузу начинает казаться, что они и впрямь едут бесконечно.
Цепь сваливается, когда велосипед достигает состояния ( Q = 0,
C = 0). В свете вышесказанного это происходит, когда l
(которое просто означает число оборотов, совершенных задним колес
ом) достигает некоего гипотетического значения, при котором in
mod l = 0, или, говоря по-человечески, когда некое число, кра
тное п (такое, как, например, 2 n , 3 n , 395
n или 109 948 368 443 n ), оказывается в то же время кратным
l . Вообще-то это может быть любое из так называемых общих крат
ных, но с практической точки зрения важно только первое Ч наименьшее об
щее кратное, или НОК, поскольку именно оно будет достигнуто первым и вызо
вет падение цепи.
Если, скажем, у звездочки двадцать зубцов ( n = 20), а в цепи сто зв
еньев ( l = 100), то после первого поворота колеса мы имеем
С = 20, после двух поворотов С = 40, потом 60, 80 и 100. Однако поско
льку мы ищем остаток от деления на 100, значение надо изменить на ноль. Таким
образом, после пяти оборотов колеса мы достигли состояния ( Q
= 0, С = 0) и цепь Тьюринга сваливается. За пять оборотов колеса
он проезжает всего десять метров, поэтому при таких значениях l
и n велосипед практически бесполезен. Разумеется, все
это верно лишь в том случае, если Тьюринг такой дурак, чтобы начать движен
ие из состояния спадения цепи. Если же он начинает крутить педали, когда в
елосипед находится в состоянии ( Q = 0, С = 1), то
С принимает значения 21, 41, 61, 81, 1, 21, ... и так до бесконечности, и цепь н
е свалится никогда. Однако это вырожденное состояние, где «вырожденное»
для математика означает «невыносимо скучное». В теории, если Тьюринг буд
ет всякий раз выставлять нужное состояние, прежде чем бросить велосипед
на улице, никто не сможет его украсть Ч цепь свалится через первые же дес
ять метров.
Если же в цепи Тьюринга сто одно звено ( l = 101), то после пяти обо
ротов мы имеем С = 100, а после шести С = 19, тогда
С = 39, 59,
79, 99, 18, 38, 58, 78, 98, 17, 37, 57, 77, 97, 16, 36, 56, 76, 96, 15, 35, 55, 75, 95, 14, 34, 54, 74, 94, 13, 33, 53, 73, 93, 12, 32, 52, 72, 92, 11, 31, 51, 71, 91, 10, 30, 50, 70, 90, 9, 29, 49, 69, 89, 8, 28, 48, 68, 88, 7, 27, 47, 67, 87, 6, 26, 46,
66, 86, 5, 25, 45, 65, 85, 4, 24, 44, 64, 84, 3, 23, 43, 63, 83, 2, 22, 42, 62, 82, 1, 21, 41, 61, 81, 0.
Так что состояние ( Q = 0, С = 0) не будет достигнуто
и цепь не свалится, пока колесо не совершит сто один оборот. За сто один об
орот велосипед Тьюринга успевает проехать по дороге пятую часть киломе
тра, что совсем не так плохо. Значит, велосипед работающий. Однако в отличи
е от вырожденного случая его нельзя привести в такое состо
яние, чтобы цепь не спадала совсем. Это легко доказать, просмотрев привед
енный список значений С и убедившись, что все возможные зна
чения Ч все числа от одного до ста Ч в нем присутствуют. Это означает, чт
о с какого бы значения С Тьюринг ни начал крутить педали, ра
но или поздно он придет к фатальному С = 0 и цепь свалится.
Разница между вырожденным и невырожденным случаем заключена в свойств
ах использованных чисел. Комбинация ( п = 20, l = 101) п
ринципиально отличается от комбинации ( п = 20, l =
100). Главная разница в том, что 20 и 101 Ч «взаимно простые», т. е. у них нет общих д
елителей. Это означает, что их наименьшее общее кратное, их НОК Ч большое
число и равняется собственно l x n , т. е. 20 x 101 = 2020. А в
от НОК ста и двадцати Ч всего 100. У велосипеда с l = 101 длинный
период Ч он проходит через множество различных состояний,
прежде чем вернуться к исходному, а у велосипеда с l = 100 Ч кор
откий, всего из нескольких состояний. Предположим, что велосипед Тьюринг
а Ч шифромашина, основанная на алфавитной замене, т. е. заменяет каждую и
з двадцати шести букв английского алфавита какой-то другой буквой. А отк
рытого текста может стать Т шифртекста, В Ч F, С Ч М и так дальше до Z. Сам по
себе такой шифр до смешного прост, взломать его Ч детская забава. Однако
предположим, что схема замены меняется от буквы к букве. Пер
вая буква открытого текста шифруется с помощью одного алфавита замены, в
торая Ч с помощью другого, третья Ч с помощью третьего и так далее. Это н
азывается полиалфавитный шифр.
Предположим, что велосипед Тьюринга генерирует свой алфавит для каждог
о из состояний. Тогда состоянию ( Q = 0, С = 0) будет с
оответствовать, например, такой алфавит замены:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Q G U W В I Y T F K V N D O H E P X L Z R C A S J M
а состоянию ( Q = 180, С = 15) Ч такой:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
B O R I X V G Y P F J M T C Q N H A Z U K L D S E W
Никакие две буквы не будут зашифрованы одним и тем же алфавитом за
мены, пока велосипед не вернется в исходное состояние (
Q = 0, С = 0) и цикл не пойдет с начала. То есть это
периодическая полиалфавитная система. Теперь, если период
у машины короткий, она часто повторяет саму себя и в качестве шифровальн
ой системы тоже годится исключительно для детской забавы. Чем длиннее пе
риод (чем больше взаимно простых чисел в него встроено), тем реже использу
ется один и тот же алфавит замены и тем выше устойчивость шифра.
Трехдисковая «Энигма» Ч система именно такого типа (то есть периодичес
кая полиалфавитная). Ее барабаны подобно приводу в велосипеде Тьюринга з
аключают в себе циклы в циклах. Ее период равен 17 576, то есть алфавит замены,
которым зашифрована первая буква сообщения, не повторится до 17 577-й буквы.
Однако в «Акуле» немцы добавили четвертый барабан, увеличив период до 456
976. В начале каждого сообщения диски ставятся в различные, случайным образ
ом выбранные исходные положения. Поскольку ни в одном немецком сообщени
и нет 450 000 знаков, «Энигма» никогда не повторяет один и тот же алфавит замен
ы в пределах отдельного сообщения.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 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 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 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 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168
рхаузу начинает казаться, что они и впрямь едут бесконечно.
Цепь сваливается, когда велосипед достигает состояния ( Q = 0,
C = 0). В свете вышесказанного это происходит, когда l
(которое просто означает число оборотов, совершенных задним колес
ом) достигает некоего гипотетического значения, при котором in
mod l = 0, или, говоря по-человечески, когда некое число, кра
тное п (такое, как, например, 2 n , 3 n , 395
n или 109 948 368 443 n ), оказывается в то же время кратным
l . Вообще-то это может быть любое из так называемых общих крат
ных, но с практической точки зрения важно только первое Ч наименьшее об
щее кратное, или НОК, поскольку именно оно будет достигнуто первым и вызо
вет падение цепи.
Если, скажем, у звездочки двадцать зубцов ( n = 20), а в цепи сто зв
еньев ( l = 100), то после первого поворота колеса мы имеем
С = 20, после двух поворотов С = 40, потом 60, 80 и 100. Однако поско
льку мы ищем остаток от деления на 100, значение надо изменить на ноль. Таким
образом, после пяти оборотов колеса мы достигли состояния ( Q
= 0, С = 0) и цепь Тьюринга сваливается. За пять оборотов колеса
он проезжает всего десять метров, поэтому при таких значениях l
и n велосипед практически бесполезен. Разумеется, все
это верно лишь в том случае, если Тьюринг такой дурак, чтобы начать движен
ие из состояния спадения цепи. Если же он начинает крутить педали, когда в
елосипед находится в состоянии ( Q = 0, С = 1), то
С принимает значения 21, 41, 61, 81, 1, 21, ... и так до бесконечности, и цепь н
е свалится никогда. Однако это вырожденное состояние, где «вырожденное»
для математика означает «невыносимо скучное». В теории, если Тьюринг буд
ет всякий раз выставлять нужное состояние, прежде чем бросить велосипед
на улице, никто не сможет его украсть Ч цепь свалится через первые же дес
ять метров.
Если же в цепи Тьюринга сто одно звено ( l = 101), то после пяти обо
ротов мы имеем С = 100, а после шести С = 19, тогда
С = 39, 59,
79, 99, 18, 38, 58, 78, 98, 17, 37, 57, 77, 97, 16, 36, 56, 76, 96, 15, 35, 55, 75, 95, 14, 34, 54, 74, 94, 13, 33, 53, 73, 93, 12, 32, 52, 72, 92, 11, 31, 51, 71, 91, 10, 30, 50, 70, 90, 9, 29, 49, 69, 89, 8, 28, 48, 68, 88, 7, 27, 47, 67, 87, 6, 26, 46,
66, 86, 5, 25, 45, 65, 85, 4, 24, 44, 64, 84, 3, 23, 43, 63, 83, 2, 22, 42, 62, 82, 1, 21, 41, 61, 81, 0.
Так что состояние ( Q = 0, С = 0) не будет достигнуто
и цепь не свалится, пока колесо не совершит сто один оборот. За сто один об
орот велосипед Тьюринга успевает проехать по дороге пятую часть киломе
тра, что совсем не так плохо. Значит, велосипед работающий. Однако в отличи
е от вырожденного случая его нельзя привести в такое состо
яние, чтобы цепь не спадала совсем. Это легко доказать, просмотрев привед
енный список значений С и убедившись, что все возможные зна
чения Ч все числа от одного до ста Ч в нем присутствуют. Это означает, чт
о с какого бы значения С Тьюринг ни начал крутить педали, ра
но или поздно он придет к фатальному С = 0 и цепь свалится.
Разница между вырожденным и невырожденным случаем заключена в свойств
ах использованных чисел. Комбинация ( п = 20, l = 101) п
ринципиально отличается от комбинации ( п = 20, l =
100). Главная разница в том, что 20 и 101 Ч «взаимно простые», т. е. у них нет общих д
елителей. Это означает, что их наименьшее общее кратное, их НОК Ч большое
число и равняется собственно l x n , т. е. 20 x 101 = 2020. А в
от НОК ста и двадцати Ч всего 100. У велосипеда с l = 101 длинный
период Ч он проходит через множество различных состояний,
прежде чем вернуться к исходному, а у велосипеда с l = 100 Ч кор
откий, всего из нескольких состояний. Предположим, что велосипед Тьюринг
а Ч шифромашина, основанная на алфавитной замене, т. е. заменяет каждую и
з двадцати шести букв английского алфавита какой-то другой буквой. А отк
рытого текста может стать Т шифртекста, В Ч F, С Ч М и так дальше до Z. Сам по
себе такой шифр до смешного прост, взломать его Ч детская забава. Однако
предположим, что схема замены меняется от буквы к букве. Пер
вая буква открытого текста шифруется с помощью одного алфавита замены, в
торая Ч с помощью другого, третья Ч с помощью третьего и так далее. Это н
азывается полиалфавитный шифр.
Предположим, что велосипед Тьюринга генерирует свой алфавит для каждог
о из состояний. Тогда состоянию ( Q = 0, С = 0) будет с
оответствовать, например, такой алфавит замены:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Q G U W В I Y T F K V N D O H E P X L Z R C A S J M
а состоянию ( Q = 180, С = 15) Ч такой:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
B O R I X V G Y P F J M T C Q N H A Z U K L D S E W
Никакие две буквы не будут зашифрованы одним и тем же алфавитом за
мены, пока велосипед не вернется в исходное состояние (
Q = 0, С = 0) и цикл не пойдет с начала. То есть это
периодическая полиалфавитная система. Теперь, если период
у машины короткий, она часто повторяет саму себя и в качестве шифровальн
ой системы тоже годится исключительно для детской забавы. Чем длиннее пе
риод (чем больше взаимно простых чисел в него встроено), тем реже использу
ется один и тот же алфавит замены и тем выше устойчивость шифра.
Трехдисковая «Энигма» Ч система именно такого типа (то есть периодичес
кая полиалфавитная). Ее барабаны подобно приводу в велосипеде Тьюринга з
аключают в себе циклы в циклах. Ее период равен 17 576, то есть алфавит замены,
которым зашифрована первая буква сообщения, не повторится до 17 577-й буквы.
Однако в «Акуле» немцы добавили четвертый барабан, увеличив период до 456
976. В начале каждого сообщения диски ставятся в различные, случайным образ
ом выбранные исходные положения. Поскольку ни в одном немецком сообщени
и нет 450 000 знаков, «Энигма» никогда не повторяет один и тот же алфавит замен
ы в пределах отдельного сообщения.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 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 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 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 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168