Алгоритмы генерации магических квадратов

1

Введение

Актуальность проблемы. Выполнять построение магических квадратов необходимо при решении задач криптографии, т.к. при минимальных затратах времени и ресурсов достигается высокий уровень устойчивости кода к расшифровке. И это только при использовании самих алгоритмов магических квадратов. В сочетании с другими системами шифрования получаем устойчивую систему шифрования.

Поэтому актуальной является задача программной реализации алгоритма заполнения магического квадрата.

Цель выпускной квалификационной работы состоит в анализе основных известных алгоритмов заполнения магических квадратов.

Для достижения поставленной цели в выпускной квалификационной работе решаются следующие задачи:

1) Рассмотреть все известные виды магических квадратов.

2) Ознакомиться с различными алгоритмами заполнения магических квадратов.

3) Проанализировать компьютерную реализацию магических квадратов.

4) Реализовать некоторые алгоритмы заполнения магических квадратов на языке программирования высокого уровня.

Методы исследования опираются на использование численных методов, прикладной информатики, математического моделирования.

Научная новизна выпускной квалификационной работы заключается в анализе и сравнении известных способов заполнения магических квадратов.

Практическая ценность выпускной квалификационной работы заключается в прикладном характере алгоритмов генерации магических квадратов - использовании алгоритмов магических квадратов на многопроцессорных компьютерах для выполнения задач криптографии.

Структура и объём работы. Выпускная квалификационная работа состоит из введения, 3 глав основного раздела и списка литературы. Содержание работы изложено на 42 страницах, включая список литературы из 15 наименований.

Глава 1. Обзор магических фигур

1.1 История магических фигур

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

Мы не знаем страну, в которой были придуманы магические квадраты, не знаем век (и даже тысячелетие!), в котором они были впервые составлены. Известно только, что они появились задолго до эры вульгарис, и их родиной был Древний Восток. Существует китайская легенда, в которой говорится, что во времена правления императора Юй (около 2200 г. до н.э.) из вод Хуанхэ всплыла черепаха, у которой на панцире были начертаны таинственные иероглифы, эти знаки известны под названием ло-шу и равносильны магическому квадрату. Сравните рис. 1 с квадратом из первого примера п.1. [6]

Первый магический квадрат с тремя клетками в основании был описан в арабском манускрипте конца восьмого века, где упоминался его автор - греческий философ-неопифагореец Аполлоний Тианский (инвоцированный, кстати, Элиафасом Леви!), живший в начале эры вульгарис. Однако не он был создателем этого древнейшего из всех магических квадратов. Аполлоний лишь вновь открыл то, что было известно за много веков до него.



Рис.1

В XI в. магические квадраты появились в Индии, а затем в Японии, где в XVI в. им была посвящена обширная литература. По-видимому, первое сочинение о магических квадратах, дошедшее до наших дней, было написано византийским грамматистом и лексикографом Мануэлем Мосхопулосом (примерно 1300 г). Он опубликовал многие построенные им МК с разным числом клеток в основании.

За работой Мосхопулоса последовали труды сотен математиков, в том числе крупнейших ученых, основоположников современной науки (Гаусс, Эйлер, Ферма).

В начале XVI в. магический квадрат появился в искусстве.

Великий немецкий художник Альбрехт Дюрер выпустил в 1514 г. гравюру, названную им «Меланхолия». На её заднем плане помещен магический квадрат 4 Ч 4, два средних числа его нижней строки (15 и 14) образуют дату создания гравюры.

С глубокой древности и до времени Дюрера сохранилось учение о том, что люди разного темперамента находятся под влиянием разных планет. Сангвиникам покровительствуют планеты Юпитер и Венера, холерики находятся под влиянием Марса, флегматики направляются Луной, а меланхолики - Сатурном. Почему для защиты Меланхолии Дюрер изобразил магический квадрат именно 4-го порядка, а не 5-го, например? Ответ мы находим в работе Корнелия Агриппы «Об оккультной философии». Агриппа пользовался древней космогонией Птолемея: в центре мира - Земля; вокруг нее небесные сферы, вложенные друг в друга, как старинные китайские резные шары из слоновой кости. Каждая сфера содержит орбиту одной планеты. На внутренней - Луна. Далее - Меркурий, Венера, Солнце, Марс, Юпитер и на внешней - Сатурн. Планеты Юпитер и Сатурн враждуют друг с другом, как и их божественные прототипы, Кронос и победивший его Зевс. (Кстати, в своем сочинении Агриппа описал семь магических квадратов, имеющих в основании от 3 до 9 клеток. Он назвал их «планетными таблицами», связав с каждой из семи планет).

Именно поэтому Дюрер для защиты своего крылатого Гения от судьбоносного Сатурна (3) изобразил магический квадрат Юпитера (4). Юпитер должен был вновь победить Сатурна. (Однако, судя по выражению лица персонажа, этого не произошло)

Дюрер, как и любой настоящий художник, и учёный, занимался оккультизмом, о чём свидетельствует его колода Таро (см. рисунок).[5]

Рис.2

В конце XVII в. были опубликованы сочинения о магических квадратах французских математиков Арно, Озанама и Симона де Лялюбера.

Сочинения академика Бернара Френикля де Бесси были впервые напечатаны в результате хлопот математика Лягира только в 1693 г, спустя 18 лет после смерти Френикля. Не будь Лягира, неизвестно, сколько еще лет лежали бы работы Френикля в архивах Королевской академии.

В «Общей таблице магических квадратов в четыре» Френикль привёл все 880 магических квадратов четвёртого порядка. Таблица занимает 43 страницы книги. Трудно представить себе, сколько времени заняла у Френикля эта работа.

В 1705 г. в Париже было издано сочинение уже упомянутого ранее Филиппа де Лягира «Новые начертания и соображения о магических квадратах с их демонстрацией. Начертания магических квадратов при четном числе клеток в основании». Эта работа особенно интересна тем, что в ней Лягир впервые рассмотрел и описал особый тип магического квадрата, который он назвал «панмагическим». В нем содержится наибольшее число равных сумм чисел. В дальнейшем квадраты этого типа называли, также, «дьявольскими», «сатанинскими», «чертовскими».

Дьявольский магический квадрат -- магический квадрат, в котором с константой совпадают также суммы чисел по ломаным диагоналям в обоих направлениях.

Ломаной диагональю называется диагональ, которая, дойдя до границы квадрата, продолжается параллельно первому отрезку от противоположного края (на рисунке такую диагональ образуют закрашенные клетки). [1]

Рис.3

Существует всего три дьявольских квадрата 4Ч4:

Современные математики называют подобные квадраты «совершенными». Стало быть, «совершенный» и «дьявольский» для современных математиков - синонимы!

Но есть еще один МК не менее интересный, чем дьявольский. Выдающийся американский масон, ученый, общественный деятель и дипломат Бенджамин Франклин составил квадрат 16Ч16 (см. рис. 4), который помимо наличия постоянной суммы 2056 во всех строках, столбцах и диагоналях имел еще одно дополнительное свойство. Если вырезать из листа бумаги квадрат 4Ч4 и уложить этот лист на большой квадрат так, чтобы 16 клеток большего квадрата попали в эту прорезь, то сумма чисел, появившихся в этой прорези, куда бы мы ее не положили, будет одна и та же - 2056.

Рис. 4

Этот квадрат является самым магически-магическим из всех МК, составленных когда-либо каким-либо магом.

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

После перевода с арабского языка, выяснилось, что документ содержит магический квадрат 3-его порядка и полумагический квадрат 4-ого порядка. В квадрате 4 Ч 4 числа повторяются, и суммы диагоналей не совпадают с константой:

Затем следовал список заклинаний, имён богов и демонов, который профессор просто оторвал и уничтожил.[2]

Традиционной сферой применения МК являются талисманы. (Полный список планетных талисманов можно найти в монографии А.Санарова «Магия талисманов. Практическое пособие»).

К примеру, талисман Луны обладает определенными свойствами: предохраняет от кораблекрушения и болезней, делает человека любезным, способствует предотвращению дурного намерения, а так же укрепляет здоровье. Его гравируют на серебре в день и час Луны, когда Солнце или Луна находится в первых десяти градусах Рака. Магический квадрат 9-ого порядка вписывается в девятиугольник (9 - число Луны, см. ниже) и окружается специальными символами.

Однако, существуют и МК для стихий и знаков Зодиака. Найти порядок нужного МК поможет Liber 777 Алистера Кроули, которая устанавливает следующие соответствия:

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	Сатурн,Стихия Земли

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

Поскольку в древнееврейском языке числа записывались буквами (это и есть причина зарождения численных методов Каббалы), магические квадраты становились буквенными и использовались для получения сигилл духов. Буквы имени духа соединялись, образуя специальный знак, который так же выполнял функцию аттрактора по отношению к духу. В случае если буква имени имела большее значение, чем числа расположенные в квадрате, она заменялась на букву в 10 раз меньшую по гематрическому значению. Например, буква Рейш имеет числовое значение 200, оно может быть сокращено до 20, что составит букву Каф, если же в МК нет и такого числа, то оно может быть сокращено еще в десять раз, что составит число 2, букву Бет.

Цитируя А.Санарова, рассмотрим пример. Создадим символ имени Михаель, ангела солнца, в МК солнца. Квадрат состоит из чисел от 1 до 36, а заглавная буква Мем имеет числовое значение равное 40, поэтому 40 сокращаем до 4, по отношению к остальным буквам имени числовые эквиваленты в квадрате имеются

Существует огромное множество различных МК одного и того же порядка. В уже упоминавшейся работе Френикля приведены 880 различных квадратов 4-ого порядка. В случае, если вам нужно выбрать один из нескольких, как поступить? Давайте научимся строить лимб, портрет МК.[8]

Рассмотрим квадрат 3-его порядка:

4	9	2
3	5	7
8	1	6

Расположив его числа в ряд, мы получим таблицу:

1	2	3	4	5	6	7	8	9
4	9	2	3	5	7	8	1	6

Расположив 9 точек по кругу, пронумеровав их и проведя линии из 1 в 4, из 2 в 9 и т.д., мы получим лимб данного квадрата:

В работах Меркурианского плана (8 - число Меркурия), связанных с информацией, знанием, коммуникациями и т.п., следует предпочесть первый квадрат. В работах Юпитерианского плана (4 - число Юпитера), связанных с планированием, благотворительностью, финансами и т.п., следует предпочесть второй квадрат.

Но в любом случае, его порядок - 3, поэтому основная направленность - Сатурн.

Вот ещё одна вариация идеи магического квадрата, магическая плоскость 4-ого порядка:

Перемещая по ней контур 4х4, внутри него мы всегда получим магический квадрат 4-ого порядка. [4]

Магическим квадратом (МК) порядка n называется числовая таблица размером клеток, заполненная натуральными числами от 1 до n2, которые размещены таким образом, что суммы чисел любого столбца, строки или главных диагоналей (см. ниже) имеют одно и то же значение. Это значение называется константой квадрата и равно S = n(n2 + 1)/2. Две диагонали, проходящие через центр квадрата, называются главными диагоналями.

Пример 1. МК 3-го порядка из 9-ти первых натуральных чисел (известный в Китае как талисман ло-шу) представляется следующей матрицей 3x3:

4	9	2
3	5	7
8	1	6

Константа этого квадрата равна 15.

Этот квадрат можно встретить на палубах больших пассажирских судов - площадка для игры в палубный шаффлборд размечена в виде магического квадрата третьего порядка.[8]

(Шаффлборд - игра, в которой монеты или диски ударом биты перемещают по расчерченной на девять клеток площадке).

Пример 2. МК 4-го порядка, известный еще в Древней Индии, представляется следующей матрицей 4x4:

1	14	15	4
12	7	6	9
8	11	10	5
13	2	3	16

Константа "индийского" квадрата равна 34.

Далее мы обсудим методы построения, отличия друг от друга и практическое применение МК.

1.2 Квадраты азиатского происхождения

Изображение Ло Шу в книге эпохи Мин

Ло Шу (кит.трад., упрощ., пиньинь luт shы) Единственный нормальный магический квадрат 3Ч3. Был известен ещё в Древнем Китае, первое изображение на черепаховом панцире датируется 2200 до н.э.

4	9	2
3	5	7
8	1	6

Квадрат, найденный в Кхаджурахо (Индия)

Самый ранний уникальный магический квадрат обнаружен в надписи XI века в индийском городе Кхаджурахо:

7	12	1	14
2	13	8	11
16	3	10	5
9	6	15	4

Это первый магический квадрат, относящийся к разновидности так называемых дьявольских квадратов.

Магический квадрат Ян Хуэя (Китай)

В 13 в. математик Ян Хуэй занялся проблемой методов построения магических квадратов. Его исследования были потом продолжены другими китайскими математиками. Ян Хуэй рассматривал магические квадраты не только третьего, но и больших порядков. Некоторые из его квадратов были достаточно сложны, однако он всегда давал правила для их построения. Он сумел построить магический квадрат шестого порядка, причем последний оказался почти ассоциативным (в нем только две пары центрально противолежащих чисел не дают сумму 37)[2]

1.3 Квадраты европейского происхождения

Квадрат Альбрехта Дюрера

Фрагмент гравюры Дюрера «Меланхолия»

Магический квадрат 4Ч4, изображённый на гравюре Альбрехта Дюрера«Меланхолия I», считается самым ранним в европейском искусстве. Два средних числа в нижнем ряду указывают дату создания картины (1514).

Сумма чисел на любой горизонтали, вертикали и диагонали равна 34. Эта сумма также встречается во всех угловых квадратах 2Ч2, в центральном квадрате (10+11+6+7), в квадрате из угловых клеток (16+13+4+1), в квадратах, построенных «ходом коня» (2+8+9+15 и 3+5+12+14), в прямоугольниках, образованных парами средних клеток на противоположных сторонах (3+2+15+14 и 5+8+9+12). Большинство дополнительных симметрий связано с тем, что сумма любых двух центрально симметрично расположенных чисел равна 17.

Квадраты Генри Э. Дьюдени и Аллана У. Джонсона -мл.

Если в квадратную матрицу n Ч n заносится не строго натуральный ряд чисел, то данный магический квадрат - нетрадиционный. Ниже представлены два таких магических квадрата, заполненные в основном простым числами. Первый имеет порядок n=3 (квадрат Дьюдени); второй (размером 4x4) - квадрат Джонсона. Оба они были разработаны в начале двадцатого столетия

Есть еще несколько подобных примеров:

Последний квадрат примечателен тем, что он составлен из 143 последовательных простых чисел за исключением двух моментов: привлечена единица, которая не является простым числом, и не использовано единственное чётное простое число 2.

1.4 Дьявольский магический квадрат

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

Такие квадраты называются ещё пандиагональными.Существует 48 дьявольских магических квадратов 4Ч4 с точностью до поворотов и отражений. Если принять во внимание еще и их дополнительную симметрию -- торические параллельные переносы, то останется только 3 существенно различных квадрата:

Однако было доказано, что из последнего третьего варианта простейшими перестановками чисел получаются первые два квадрата. То есть третий вариант -- это базовый дьявольский квадрат, из которого различными преобразованиями можно построить все остальные.

Пандиагональные квадраты существуют для нечётного порядка n>3, для любого порядка двойной чётности n=4k (k=1,2,3…) и не существуют для порядка одинарной чётности n = 4k + 2 ().

Пандиагональные квадраты четвёртого порядка обладают рядом дополнительных свойств, за которые их называют совершенными. Совершенных квадратов нечётного порядка не существует. Среди пандиагональных квадратов двойной чётности выше 4 имеются совершенные.[2]

Пандиагональных квадратов пятого порядка 3600. С учётом торических параллельных переносов имеется 144 различных пандиагональных квадратов. Один из них показан ниже.

Разломанные диагонали пандиагонального квадрата

Если пандиагональный квадрат еще и ассоциативный, то он носит название идеальный. Пример идеального магического квадрата:

Известно, что не существует идеальных магических квадратов порядка n = 4k+2 и квадрата порядка n = 4. В то же время, существуют идеальные квадраты порядка n = 8. Методом построения составных квадратов можно построить на базе данного квадрата восьмого порядка идеальные квадраты порядка n = 8k, k=5,7,9...и порядка n = 8^p, p=2,3,4... В 2008 г. разработан комбинаторный метод построения идеальных квадратов порядка n = 4k , k = 2, 3, 4,...

1.5 Выводы

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

Глава 2. Механизмы генерации магических фигур

2.1 Составление магических квадратов нечетного порядка

Наибольший практический интерес представляют универсальные методы, которые не зависят от порядка магического квадрата. Такие методы известны для магических квадратов нечетного порядка. Наиболее наглядный из них удобно рассмотреть на примере составления магического квадрата 5-го порядка из натуральных чисел от 1 до 25. Алгоритм этого метода включает следующие шаги. [9]

1. Сначала исходный пустой квадрат достраивается до симметричной ступенчатой ромбовидной фигуры как показано на следующем рисунке, где ячейки для элементов квадрата обозначены символом #, а достроенные ячейки - символом $.

2. Полученная на шаге 1 фигура заполняется по косым рядам сверху-вниз-направо целыми числами от 1 до 25 в натуральном порядке. Результат заполнения показан на следующем рисунке:

3. Каждое число, расположенное в фигуре шага 2 вне исходного квадрата, переносится по вертикали или горизонтали внутрь исходного квадрата на число позиций, равное порядку квадрата. В рассматриваемом примере перенос осуществляется на 5 позиций. Таблица переносов имеет следующий вид:

1 - вниз под 13;	2 - вниз под 14;	6 - вниз под 18;
21 - вправо за 13;	22 - вправо за 14;	16 - вправо за 8;
5 - влево перед 13;	4 - влево перед 12;	10 - влево перед 18;
25 - вверх над 13;	24 - вверх над12;	20 - вверх над 8.

Освобождающиеся ячейки, достроенные к исходному квадрату заполняются символом $.

4. После преобразований переноса на шаге 3 освободившиеся ячейки (заполненные символом $) должны быть исключены. Оставшиеся (внутренние) ячейки (заполненные натуральными числами) образуют магический квадрат, представленный следующей матрицей 5x5:

11	24	7	20	3
4	12	25	8	16
17	5	13	21	9
10	18	1	14	22
23	6	19	2	15

константа которого равна 65, что может быть проверено вычислением суммы элементов для столбцов, строк и главных диагоналей.

Рассмотренный метод составления нечетных магических квадратов не является единственным. Не менее известным и не более сложным является следующий алгоритм, предложенный С. Лубером. Правила алгоритма Лубера удобно иллюстрировать на примере магического квадрата порядка 7 из натуральных чисел от 1 до 49, матрица 7x7 которого показана на следующем рисунке:

28	19	10	01	48	39	30
29	27	18	09	07	47	38
37	35	26	17	08	06	46
45	36	34	25	16	14	05
04	44	42	33	24	15	13
12	03	43	41	32	23	21
20	11	02	49	40	31	22

В основе алгоритма Лубера лежит заполнение ячеек квадрата в направлении вверх и влево по диагонали последовательными числами выбранной арифметической прогрессии. Заполнение начинается со среднего элемента верхней строки (01). Если следующая левая диагональная ячейка уже занята числом (ячейка 01 уже занята в момент заполнения ячейки 07), нужно перейти к нижнему соседу (08) текущей заполненной ячейки (07) и продолжить движение по диагонали. Чтобы избежать возможности выхода за границы квадрата при диагональном движении его надо мысленно превратить в тор, соединив верхнюю горизонталь с нижней, а затем соединить основания полученного цилиндра. После свертки строки, столбцы и диагонали квадрата превращаются в замкнутые кривые на поверхности тора и выход за границы квадрата становится невозможным. Превращение квадрата в тор в данном случае обеспечивает возможность диагонального перехода, например, из ячейки 01 в ячейку 02 или из ячейки 45 в ячейку 46.

2.2 Составление магических квадратов четного порядка

Универсальные методы составления магических квадратов произвольного четного порядка пока неизвестны. Однако, разработаны индивидуальные подходы для различных частных случаев. Ниже рассмотрен метод составления магических квадратов, порядок которых является экспонентой 2. Этот метод удобно рассмотреть на примере магического квадрата 8-го порядка из натуральных чисел от 1 до 64. Метод включает следующую последовательность шагов. [9]

1. Исходный квадрат делится на соответствующее число квадратов порядка 4. В данном случае таких квадратов будет 4. В каждом подквадрате отмечаются диагональные элементы (например, символом #). Остальные элементы построчно заполняются порядковыми целыми числами в направлении слева-направо и сверху-вниз. Числа, приходящиеся на выделенные диагональные элементы должны быть пропущены. Результат заполнения недиагональных элементов квадрата 8-го порядка показан на следующем рисунке:

#	2	3	#	#	6	7	#
9	#	#	12	13	#	#	16
17	#	#	20	21	#	#	24
#	26	27	#	#	30	31	#
#	34	35	#	#	38	39	#
41	#	#	44	45	#	#	48
49	#	#	52	53	#	#	56
#	58	59	#	#	62	63	#

2. Отмеченные на шаге 1 диагональные элементы квадрата заполняют пропущенными целыми числами в порядке возрастания в направлении справа-налево и снизу-вверх. Недиагональные элементы в каждом подквадрате должны быть отмечены (например, символом $), а числа, приходящиеся на них должны быть пропущены. Результат заполнения диагональных элементов для квадрата 8-го порядка показан на следующем рисунке:

64	$	$	61	60	$	$	57
$	55	54	$	$	51	50	$
$	47	46	$	$	43	42	$
40	$	$	37	36	$	$	33
32	$	$	29	28	$	$	25
$	23	22	$	$	19	18	$
$	15	14	$	$	11	10	$
8	$	$	5	4	$	$	1

3. Квадраты с пропусками диагональных и недиагональных элементов, полученные на шагах 1 и 2, объединяются в общий квадрат, где целочисленные элементы подавляют метки # или $. Результат объединения для квадрата 8-го порядка показан на следующем рисунке:

64	02	03	61	60	06	07	57
09	55	54	12	13	51	50	16
17	47	46	20	21	43	42	24
40	26	27	37	36	30	31	33
32	34	35	29	28	38	39	25
41	23	22	44	45	19	18	48
49	15	14	52	53	11	10	56
8	58	59	5	4	62	63	1

Константа этого магического квадрата равна 260, что подтверждается вычислением контрольных сумм элементов по строкам, столбцам и главным диагоналям.

2.3 Выводы

Существование общего алгоритма построения магических квадратов невозможно. Однако существуют частные алгоритмы, которые с увеличением порядка дают стремящееся к бесконечности число магических квадратов. Это частные методы составления магических квадратов, порядок которых является экспонентой 2 и квадратов нечетного порядка.

Глава 3. Программная реализация магических квадратов

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

3.1 Программная реализация квадратов нечетного порядка

Магические квадраты нечетного порядка можно построить с помощью метода французского геометра 17 в. А.де ла Лубера. Рассмотрим этот метод на примере квадрата 5-го порядка (рис. 3.1). Число 1 помещается в центральную клетку верхней строки. Все натуральные числа располагаются в естественном порядке циклически снизу вверх в клетках диагоналей справа налево. Дойдя до верхнего края квадрата (как в случае числа 1), продолжаем заполнять диагональ, начинающуюся от нижней клетки следующего столбца. Дойдя до правого края квадрата (число 3), продолжаем заполнять диагональ, идущую от левой клетки строкой выше. Дойдя до заполненной клетки (число 5) или угла (число 15), траектория спускается на одну клетку вниз, после чего процесс заполнения продолжается.[10]

Рис. 3.1

Ниже рассмотрим листинг программы, которая реализует данный квадрат на языке Паскаль.

progam algMR;

uses crt;

const n=5;

type mr:array[1..n,1..n]of integer;

var a:mr; b,i,j:integer;

begin

clrscr;

for i:=1 to n do

for j:=1 to n do

a[i,j]:=0;

i:=1;j:=(n div 2)+1;b:=1;

repeat

if i=n+1 then i:=1;if i=0 then i:=n;

if j=n+1 then j:=1;

if a[i,j]=0 then begin a[i,j]:=b;i:=i-1;j:=j+1;b:=b+1; end

else begin i:=i+1;a[i,j]:=b; b:=b+1;i:=i-1;j:=j+1;end;

until b=n;

for i:=1 to n do

begin

for j:=1 to n do

write(' ',a[i,j]);

writeln;

end;

end.

В программе использовался конечный массив элементов магического квадрата, что позволяет реализовать демонстрацию данного магического квадрата на уроках информатики в школе или ВУЗах.

3.2 Программная реализация квадратов четного порядка

Метод Ф.де ла Ира (1640-1718) основан на двух первоначальных квадратах. На рис. 2 показано, как с помощью этого метода строится квадрат 5-го порядка. В клетку первого квадрата вписываются числа от 1 до 5 так, что число 3 повторяется в клетках главной диагонали, идущей вправо вверх, и ни одно число не встречается дважды в одной строке или в одном столбце. То же самое мы проделываем с числами 0, 5, 10, 15, 20 с той лишь разницей, что число 10 теперь повторяется в клетках главной диагонали, идущей сверху вниз (рис. 2,б). Поклеточная сумма этих двух квадратов (рис. 2,в) образует магический квадрат. Этот метод используется и при построении квадратов четного порядка.[10]

Рис. 2

Ниже рассмотрим листинг программы, которая реализует данный квадрат на языке Паскаль.

progam algMR;

uses crt;

const n=5;

type mr:array[1..n,1..n]of integer;

var a,d,c:mr; b,i,j,z,k:integer;

begin

clrscr;

for i:=1 to n do

for j:=1 to n do

a[i,j]:=0;i:=1;j:=1;b:=1;

for k:= 1 to n do

repeat

if i=n+1 then i:=1;if i=0 then i:=n;

if j=n+1 then j:=1;

if a[i,j]=0 then begin a[i,j]:=b;i:=i+1;j:=j-1; end

else begin b:=b+1; i:=i+2;a[i,j]:=b; i:=i+1;j:=j-1;end;

until b=n+1;

i:=1;j:=2;b:=0;z:=-5;

for k:= 1 to n do

begin z:=z+5;

repeat

if i=n+1 then i:=1;if i=0 then i:=n;

if j=n+1 then j:=1;

if d[i,j]=0 then begin d[i,j]:=z;i:=i+1;j:=j-1;b:=b+1 end

else begin b:=b+1; i:=i+2;d[i,j]:=z; i:=i+1;j:=j-1;end;

until b=n*n;

for i:=1 to n do

for j:=1 to n do

c[i,j]:=a[i,j]+b[i,j];

for i:=1 to n do

begin

for j:=1 to n do

write(' ',c[i,j]);

writeln;

end;

end.

В программе использовалось уже три массива, и добавочные переменные. Это связано с облегчением задачи построения исходных матриц с последующим сложением оных. Также есть несколько иная программная реализация магических квадратов.

Uses Crt;

Const N = 127;

Var Mas : Array[1..N, 1..N] Of Word;

X, Y, X0, Y0 : Integer;

C : Longint;

Begin

ClrScr;

Assign(Output,'127x127.txt');

Rewrite(Output);

X:=(N - 1) Div 2 + 1;

Y:=X + 1;

X0:=X - 1;

Y0:=Y - 1;

While C < N*N Do

Begin

If (Mas[Y, X] <> 0) Then

Begin

X:=X0 - 1;

Y:=Y0 + 1;

If X < 1 Then X:=N;

If Y > N Then Y:=1;

End Else

Begin

Inc(C);

Mas[Y, X]:=C;

End;

X0:=X; Y0:=Y;

Inc(X); Inc(Y);

If Y > N Then Y:=1;

If X > N Then X:=1;

End;

For Y:=1 To N Do

Begin

For X:=1 To N Do

Write(Mas[Y,X]:6);

Writeln;

End;

Close(Output);

End.

Данный программный код будет работать быстрее, чем указанные выше, т.к. условие заполнения клетки оптимизировано.

3.3 Выводы

Алгоритмы генерации магических квадратов можно реализовать даже на самых простейших языках, например Pascal. Однако самый перспективный метод для распараллеливания это метод Ф. де ла Ира. Две матрицы можно заполнять по диагоналям сразу несколькими процессорами. Также можно выполнять поклеточное сложение. Метод Ф. де ла Ира работает как для квадратов четного, так и для квадратов нечетного порядка.

Заключение

Основные результаты выпускной квалификационной работы заключаются в следующем.

1. Рассмотрены все известные на данный момент виды магических квадратов. Также было выполнено ознакомление с историей магических квадратов.

2. Разобраны основные алгоритмы заполнения магических квадратов.

3. Проанализирована компьютерная реализация магических квадратов.

4. Сконструированы программы для основных методов заполнения магических квадратов. Выявлены наиболее подходящие алгоритмы для выполнения задач криптографии на многопроцессорных компьютерах.

Научная новизна результатов выпускной квалификационной работы заключается в следующем.

1. Рассмотрены все известные на данный момент алгоритмы заполнения магических квадратов.

2. Выявлен наиболее универсальный алгоритм заполнения магических квадратов- метод Ф. де ла Ира. Также этот метод может быть подвергнут преобразованиям для реализации его на многопроцессорных компьютерах.

3. Построены программные коды для основных алгоритмов генерации магических квадратов. Найден универсальный способ заполнения магических квадратов, подходящий для решения задач криптографии.

Приложение

Шифрующие таблицы

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

* размер таблицы;

* слово или фраза, задающие перестановку;

* особенности структуры таблицы.

Одним из самых примитивных табличных шифров перестановки является простая перестановка, для которой ключом служит размер таблицы. Этот метод шифрования сходен с шифром скитала. Например, сообщение

ТЕРМИНАТОР ПРИБЫВАЕТ СЕДЬМОГО В ПОЛНОЧЬ

записывается в таблицу поочередно по столбцам. Результат заполнения таблицы из 5 строк и 7 столбцов показан на рисунке ниже. После заполнения таблицы текстом сообщения по столбцам для формирования шифртекста считывают содержимое таблицы по строкам.

Т	Н	П	В	Е	Г	Л
Е	А	Р	А	Д	О	Н
Р	Т	И	Е	Ь	В	О
М	О	Б	Т	М	П	Ч
И	Р	Ы	С	О	О	Ь

Заполнение таблицы из 5 строк и 7 столбцов

Если шифртекст записывать группами по пять букв, получается такое шифрованное сообщение:

ТНПВЕ ГЛЕАР АДОНР ТИЕЬВ ОМОБТ МПЧИР ЫСООЬ

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

Применим в качестве ключа, например, слово ПЕЛИКАН,

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

ГНВЕП ЛТООА ДРНЕВ ТЕЬИО РПОТМ БЧМОР СОЫЬИ

Для обеспечения дополнительной скрытности можно повторно зашифровать сообщение, которое уже прошло шифрование. Такой метод шифрования называется двойной перестановкой. В случае двойной перестановки столбцов и строк таблицы перестановки определяются отдельно для столбцов и отдельно для строк. Сначала в таблицу записывается текст сообщения, а потом поочередно переставляются столбцы, а затем строки. При расшифровании порядок перестановок должен быть обратным. Пример выполнения шифрования методом двойной перестановки показан на рисунке ниже. Если считывать шифртекст из правой таблицы построчно блоками по четыре буквы, то получится следующее:

ТЮАЕ ООГМ РЛИП ОЬСВ

Ключом к шифру двойной перестановки служит последовательность номеров столбцов и номеров строк исходной таблицы (в нашем примере последовательности 4132 и 3142 соответственно).

Пример выполнения шифрования методом двойной перестановки

Число вариантов двойной перестановки быстро возрастает при увеличении размера таблицы:

* для таблицы 3х3 36 вариантов;

* для таблицы 4х4 576 вариантов;

* для таблицы 5х5 14400 вариантов.

Однако двойная перестановка не отличается высокой стойкостью и сравнительно просто "взламывается" при любом размере таблицы шифрования.

Применение магических квадратов

В средние века для шифрования перестановкой применялись и магические квадраты. Магическими квадратами называют квадратные таблицы с вписанными в их клетки последовательными натуральными числами, начиная от 1, которые дают в сумме по каждому столбцу, каждой строке и каждой диагонали одно и то же число. Шифруемый текст вписывали в магические квадраты в соответствии с нумерацией их клеток. Если затем выписать содержимое такой таблицы по строкам, то получится шифртекст, сформированный благодаря перестановке букв исходного сообщения. В те времена считалось, что созданные с помощью магических квадратов шифртексты охраняет не только ключ, но и магическая сила. Пример магического квадрата и его заполнения сообщением

ПРИЛЕТАЮ ВОСЬМОГО

показан на рисунке ниже.

Пример магического квадрата 4х4 и его заполнения сообщением

ПРИЛЕТАЮ ВОСЬМОГО

Шифртекст, получаемый при считывании содержимого правой таблицы по строкам, имеет вполне загадочный вид:

ОИРМ ЕОСЮ ВТАЬ ЛГОП

Число магических квадратов быстро возрастает с увеличением размера квадрата. Существует только один магический квадрат размером 3х3 (если не учитывать его повороты). Количество магических квадратов 4х4 составляет уже 880, а количество магических квадратов 5х5 - около 250000.

Список литературы

1. Болл У., Коксетер Г. «Математические эссе и развлечения» - М.: Мир, 1986 г.

2. Гуревич Е.Я. «Тайна древнего талисмана» - М.: Наука, 1969 г.

3. Кроули А. «777. Каббала Алистера Кроули» - М.: ОДДИ-Стиль, 2003 г.

4. Оре О. «Приглашение в теорию чисел» - М.: Наука, 1980 г.

5. Петровец Т.Г., Ю.В.Садомова «Энциклопедия мировой живописи» - М.: ОЛМА-ПРЕСС, 2000 г.

6. Постников M.М. «Магические квадраты» - М.: Наука, 1964 г.

7. Санаров А.В. «Магия талисманов. Практическое пособие» - М.: Велигор, 2002 г.

8. Abe G. «Unsolved Problems on Magic Squares» Disc. Math. 127, 1994 г.

9. Frйnicle de Bessy, B. «Des quarrez ou tables magiques. Avec table generale des quarrez magiques de quatre de costй.» В Divers Ouvrages de Mathйmatique et de Physique, par Messieurs de l'Acadйmie Royale des Sciences (Ред. P. de la Hire). Paris: De l'imprimerie Royale par Jean Anisson, 1693 г.

10. Gardner, M. «Magic Squares and Cubes» Гл. 17 в Time Travel and Other Mathematical Bewilderments. New York: W. H. Freeman, 1988 г.

11. W.W.Rouse Ball, mathematical recneations and esays, revised by H.M.Coxeter (New york:macmillan,1939.chaapter 7).

12. Морозов В.В. Математические головоломки - М.: Первое сентября, 2001г.

13. М. Гарднер. Математические головоломки и развлечения, - М., Мир,1971г.

14. Б. А. Кордемский. Математическая смекалка, - М.: ТТЛ, 1957г.

15. Д. Кнут Искусство программирования для ЭВМ т.1 Основные алгоритмы - М., Мир, 1976г.