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];
begin
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
If (Mas[Y, X] <> 0) Then
X:=X0 - 1;
Y:=Y0 + 1;
If X < 1 Then X:=N;
If Y > N Then Y:=1;
End Else
Inc(C);
Mas[Y, X]:=C;
End;
X0:=X; Y0:=Y;
Inc(X); Inc(Y);
If X > N Then X:=1;
For Y:=1 To N Do
For X:=1 To N Do
Write(Mas[Y,X]:6);
Writeln;
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г.
Страницы: 1, 2, 3, 4, 5
