Русская Википедия:Латинский квадрат

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Лати́нский квадра́т n-го порядка — таблица L=(l_ij) размеров n × n, заполненная n элементами множества M таким образом, что в каждой строке и в каждом столбце таблицы каждый элемент из M встречается в точности один раз. Пример латинского квадрата 3-го порядка:

<math>

\begin{bmatrix} A & B & C \\ C & A & B \\ B & C & A \\ \end{bmatrix}

</math>

который может быть представлен в виде {(1,1,A), (1,2,B), (1,3,C), (2,1,C), (2,2,A), (2,3,B), (3,1,B), (3,2,C), (3,3,A)}, где первый и второй элемент — позиция элемента в матрице, а третий — значение.

В настоящее время в качестве множества M обычно берётся множество натуральных чисел {1,2,…,n} или множество {0,1,…,n-1}, однако Леонард Эйлер использовал буквы латинского алфавита, откуда латинские квадраты и получили своё название.

Латинские квадраты существуют для любого n, достаточно взять таблицу Кэли группы порядка n, например, <math>l_{ij}= (i+j-1) \pmod{n}</math>.

История исследований латинских квадратов

Файл:Fisher-stainedglass-gonville-caius.jpg

Окно в честь Фишера с латинским квадратом 7-го порядка. Кембридж

Впервые латинские квадраты (4-го порядка) были опубликованы в книге «Шамс аль-Маариф» («Книга о Солнце Гнозиса»), написанной Ахмадом аль-Буни в Египте приблизительно в 1200 году.

В 1700 году латинские квадраты были описаны корейским математиком Чхве Сок Чон, где он сформулировал «задачу о шестиугольной черепахе», полностью эквивалентную «задаче о 36 офицерах», которая будет вновь сформулирована Эйлером через 67 лет.

Пары ортогональных латинских квадратов были упомянуты Жаком Озанамом в 1725 году. В книге, представляющей собой сборник задач по физике и математике, приведена следующая задача:

Необходимо разместить 16 игральных карт из тузов, королей, дам и валетов всех четырёх мастей в виде квадрата так, чтобы все масти и карты всех достоинств встречались в каждой строке и в каждом столбце ровно один раз.

Эта задача имеет 6912 решений (если дополнительно потребовать, чтобы и диагонали квадрата удовлетворяли тому же условию, то число решений уменьшится в 6 раз и станет равным 1152).

Важной вехой в истории исследований латинских квадратов стала работа Эйлера. Он занимался в ней методами построения магических квадратов и предложил метод, основанный на паре ортогональных латинских квадратов. Исследуя такие пары, Эйлер выяснил, что проблема их построения подразделяется на три случая в зависимости от остатка от деления числа n на 4. Он предложил способы построения пар ортогональных квадратов для n, делящихся на 4 и для нечётных n. Очевидно, что при n = 2 таких пар не существует. Ему не удалось построить пары ортогональных латинских квадратов для n = 6, 10 и он высказал гипотезу о том, что не существует пар ортогональных квадратов для n = 4t+2. Для n = 6 он сформулировал «задачу о 36 офицерах»:

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

В 1890 году Кэли вывел формулу для числа латинских прямоугольников из двух строк (частный случай классической комбинаторной «задачи о встречах», поставленной P. Montmort в 1708 году).

В 1900 году гипотеза Эйлера для n = 6 была подтверждена Шаблон:Нп5. Он построил все 9408 нормализованных латинских квадратов, разбил их на 17 типов и показал, что при любом их сочетании невозможно построить пару ортогональных квадратов. Таким образом, он отрицательно решил «задачу о 36 офицерах».

В 1922 году MacNeish впервые применил теоретико-групповой подход к решению задач относительно латинских квадратов. В частности, он предложил метод конструирования латинских квадратов порядка n1•n2 из латинских квадратов порядков n1 и n2, при этом свойство ортогональности сохраняется.

В 1925 году Роналд Фишер предложил использовать ортогональные латинские квадраты для планирования сельскохозяйственных экспериментов.

В 1920—1930 годы стали интенсивно изучаться неассоциативные алгебраические структуры, что привело, в частности, к созданию теории квазигрупп, тесно связанной с изучением латинских квадратов, так как между латинскими квадратами и таблицами Кэли квазигрупп существует взаимно-однозначное соответствие.

В 1959 году Bose и Shrikhande построили 2 ортогональных латинских квадрата для n = 22, а в 1960 году они же и Parker построили с использованием ЭВМ минимальный контрпример для n = 10. Таким образом, спустя 177 лет гипотеза Эйлера была опровергнута.

Число латинских квадратов

Точная формула для числа L(n) латинских квадратов n-го порядка неизвестна. Наилучшие оценки для L(n) даёт формула

<math> \prod_{k=1}^n \left(k!\right)^{n/k}\geq L(n)\geq\frac{\left(n!\right)^{2n}}{n^{n^2}}</math>

Каждому латинскому квадрату можно поставить в соответствие нормализованный (или редуцированный) латинский квадрат, у которого первая строка и первый столбец заполнены в соответствии с порядком, заданном на множестве M. Пример нормализованного латинского квадрата:

<math>

\begin{bmatrix} A & B & C \\ B & C & A \\ C & A & B \\ \end{bmatrix}

</math>

Число R(n) нормализованных латинских квадратов n-го порядка (Шаблон:OEIS) в n!(n-1)! раз меньше, чем L(n) (Шаблон:OEIS).

Точные значения величины L(n) известны для n от 1 до 11:

Число латинских квадратов

n	R(n)	L(n)	Автор и год
1	1	1
2	1	2
3	1	12
4	4	576
5	56	161280	Euler (1782)
6	9408	812851200	Frolov (1890)
7	16942080	61479419904000	Sade (1948)
8	535281401856	108776032459082956800	Wells (1967)
9	377597570964258816	5524751496156892842531225600	Bammel и Rothstein (1975)
10	7580721483160132811489280	9982437658213039871725064756920320000	McKay и Rogoyski (1995)
11	5363937773277371298119673540771840	776966836171770144107444346734230682311065600000	McKay и Wanless (2005)

Отношения эквивалентности на множестве латинских квадратов

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

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

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

Композиция изотопии и парастрофии называется изострофией. Это ещё одно отношение эквивалентности, его классы называются главными классами. Каждый главный класс содержит 1, 2, 3 или 6 изотопических классов. В случае совпадения исходного латинского квадрата и изострофного ему, говорят об автострофии. С ростом n почти все латинские квадраты имеют тривиальную группу автострофий.

Число классов эквивалентности

n	Число главных классов	Число изотопических классов
1	1	1
2	1	1
3	1	1
4	2	2
5	2	2
6	12	22
7	147	564
8	283657	1676267
9	19270853541	115618721533
10	34817397894749939	208904371354363006
11	2036029552582883134196099	12216177315369229261482540

Ортогональные латинские квадраты

Шаблон:Main Два латинских квадрата L=(l_ij) и K=(k_ij) n-го порядка называются ортогональными, если все упорядоченные пары (l_ij,k_ij) различны. Пример двух ортогональных латинских квадратов и соответствующие им упорядоченные пары:

<math>

\begin{bmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \\ \end{bmatrix} \quad\quad \begin{bmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \\ 2 & 3 & 1 \\ \end{bmatrix} \quad\quad \begin{bmatrix} (1,1) & (2,2) & (3,3)\\ (2,3) & (3,1) & (1,2)\\ (3,2) & (1,3) & (2,1)\\ \end{bmatrix}

</math>

Эйлер называл такие квадраты «полными». В его честь в научной литературе их раньше называли «эйлеровыми» или «греко-латинскими» (так как Эйлер использовал буквы греческого алфавита для квадрата, ортогонального латинскому).

Ортогональные латинские квадраты существуют для любого n, не равного 2 и 6.

Латинский квадрат L n-го порядка имеет ортогональный ему квадрат тогда и только тогда, когда в L существует n непересекающихся трансверсалей.

Особый интерес в связи с многочисленными приложениями вызывают множества из нескольких попарно ортогональных латинских квадратов n-го порядка. Максимально возможная мощность N(n) такого множества равна n-1, в этом случае множество называется полным.

При n, стремящемуся к ∞, величина N(n) тоже стремится к ∞.

Для n, являющегося степенью простого числа, всегда существует полное множество попарно ортогональных латинских квадратов, его можно взаимооднозначно сопоставить с конечной проективной плоскостью порядка n. Для его построения применяется метод Боуза, использующий для заполнения квадратов значения многочленов вида <math>f_a(x, y)=ax+y</math> при ненулевом a над полем <math>\mathrm{GF}(n)</math>. Пример построения полного множества попарно ортогональных латинских квадратов 4-го порядка (d — корень примитивного многочлена <math>x^2+x+1</math> над <math>\mathrm{GF}(2)</math>):

<math>

\begin{bmatrix} 0 & 1 & d & d+1\\ 1 & 0 & d+1 & d\\ d & d+1 & 0 & 1\\ d+1 & d & 1 & 0\\ \end{bmatrix} \quad\quad \begin{bmatrix} 0 & 1 & d & d+1\\ d & d+1 & 0 & 1\\ d+1 & d & 1 & 0\\ 1 & 0 & d+1 & d\\ \end{bmatrix} \quad\quad \begin{bmatrix} 0 & 1 & d & d+1\\ d+1 & d & 1 & 0\\ 1 & 0 & d+1 & d\\ d & d+1 & 0 & 1\\ \end{bmatrix}

</math>

Если n ≡ 1 (mod 4) или n ≡ 2 (mod 4) и свободная от квадрата часть числа n содержит хотя бы один простой множитель p ≡ 3 (mod 4), то для таких n полного множества попарно ортогональных латинских квадратов не существует.

Известные нижние оценки числа N(n) при n < 33 приведены в следующей таблице (выделены оценки, которые могут быть улучшены):

Нижние оценки числа N(n)

n	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
N(n)≥			2	3	4		6	7	8	2	10	5	12	3	4	15	16	3	18	4	5	3	22	6	24	4	26	5	28	4	30	31

Построение ортогональных квадратов — сложная комбинаторная задача. Для её решения применяются как алгебраические конструкции, так и комбинаторные (трансверсали, ортогональные массивы, дизайны, блок-схемы, тройки Штейнера и др.) Существует несколько подходов к решению этой задачи, их можно разделить на две группы. К первой группе относятся методы, основанные на выборе базового латинского квадрата, к которому отыскиваются изотопные ортогональные латинские квадраты. Например, пять попарно ортогональных латинских квадратов 12-го порядка были найдены в результате построения четырёх ортоморфизмов абелевой группы, являющейся прямым произведением циклических групп порядков 6 и 2.

Ко второй группе относятся методы, использующие для построения ортогональных латинских квадратов комбинаторные объекты (включая сами латинские квадраты) меньших порядков. Например, два латинских квадрата 22-го порядка были построены Bose и Shrikhande на основе двух дизайнов 15-го и 7-го порядка.

Диагональные латинские квадраты

Латинский квадрат называется диагональным, если в дополнение к требованиям уникальности элементов в строках и столбцах, свойственным для латинского квадрата, добавляются требования уникальности элементов на главной и побочной диагоналях. Аналитическая оценка числа диагональных латинских квадратов неизвестна, их число для размерностей N<10 было определено в 2016 г. в проекте добровольных распределённых вычислений Gerasim@Home (Шаблон:OEIS и Шаблон:OEIS). Для диагональных латинских квадратов, как и для просто латинских, возможно построение ортогональных пар, часть из которых (порядка 9 и 10) была найдена в проекте добровольных распределённых вычислений SAT@home с использованием SAT-подхода. В настоящее время поиск пар ортогональных диагональных латинских квадратов 10-го порядка производится в проекте добровольных распределённых вычислений Gerasim@Home с использованием трансверсалей, а также в BOINC-проектах ODLK и ODLK1. 25 апреля 2018 г. найден диагональный латинский квадрат 10-го порядка, имеющий 10 ортогональных диагональных латинских квадратов. Это максимальное известное количество ортогональных диагональных квадратов у диагонального латинского квадрата 10-го порядка (Шаблон:OEIS). Открытой математической проблемой является существование тройки попарно ортогональных диагональных латинских квадратов порядка 10 (на текущий момент наилучшим приближением к её решению является тройка квадратов, в которой две пары квадратов ортогональны, а третья частично ортогональна в 74 ячейках).

Частичные квадраты

Квадрат, в котором каждый элемент множества M в каждой строке и в каждом столбце встречается не более одного раза, называется частичным.

Задача распознавания того, может ли частичный квадрат быть дополнен до латинского, является NP-полной.

Введено понятие критического множества, соответствующего частичному квадрату, который однозначно может быть дополнен до латинского, причём никакое его подмножество условию однозначности не удовлетворяет. Мощность C(n) критического множества для квадратов размеров n × n известна для n < 7:

Мощность критического множества

n	1	2	3	4	5	6
С(n)	0	1	3	7	11	18

Нерешённые задачи

Помимо задачи нахождения формулы для величины L(n), имеется большое количество нерешённых задач относительно латинских квадратов. Ряд таких задач был сформулирован на конференции Loops’03:

• Оценка максимального числа трансверсалей в латинском квадрате n-го порядка
• Характеризация латинских подквадратов в таблице умножения луп Муфанг
• Оценка плотности частичного квадрата, удовлетворяющего свойству Блэкберна
• Вычисление максимального t(n), при котором 2^t(n) делит величину L(n)

Применение

Файл:The Soviet Union 1949 CPA 1405 souvenir sheet of 4 (Pushkin is a lyceum student and portrait by Kiprensky. Illustrations for 'Ruslan and Lyudmila' and 'Bronze Horseman').jpg

Пример использования латинского квадрата в филателии

Латинские квадраты находят широкое применение в алгебре, комбинаторике, статистике, криптографии, теории кодов и многих других областях.

Применение в криптографии. Протокол с нулевым разглашением

В настоящее время латинские квадраты активно применяются для реализации протоколов с нулевым разглашением. В частности для генерации MAC.
Пусть q={1,2,…,n}. Для данного латинского квадрата

<math>LS=

\begin{bmatrix} l_{1,1} & ... & l_{1,q} \\ . & ... & . \\ l_{q,1} & ... & l_{q,q} \\ \end{bmatrix}

</math>

b = q/2 варианты LS изотопные друг другу.

Предположим, пользователи <math>(u_1, u_2, ..., u_k)</math> образуют сеть. <math>u_i</math> имеет публичный ключ <math>L_ui</math> и <math>L'_ui</math> (обозначим два изотопных Латинских квадрата порядка n) и секретный ключ <math>I_ui</math> (обозначим изотопизм <math>L_ui</math> над <math>L'_ui</math>). <math>u_i</math> хочет доказать подлинность <math>u_j</math>, но он не хочет раскрывать секретный ключ (Доказательство с нулевым разглашением).

1. <math>u_i</math> случайным образом переставляет <math>L_ui</math> и получает другой латинский квадрат Н
2. <math>u_i</math> отправляет Н к <math>u_j</math>
3. <math>u_j</math> просит <math>u_i</math> либо:
— доказать что Н и <math>L'_ui</math> изотопны
— доказать что Н и <math>L_ui</math> изотопны
4. <math>u_i</math> выполняет просьбу. Он или
— доказывает что Н и <math>L'_ui</math> изотопны
— доказывает что Н и <math>L_ui</math> изотопны
5. <math>u_i</math> и <math>u_j</math> повторяют шаги 1-4 n раз

Ниже приведён псевдокод для посчёта Хеш-функции

for k from 1 to q do
    begin
        d_k=1;
    end
for i from 1 to q do
    begin
    for j from 1 to q do
        begin
        for k from 1 to b do
            begin
                 d_l_ji=m_ij*d_l_ji;
            end
        end
    end

Хеш-сумма получится в векторе D=[<math>d_1,...,d_n</math>]
Пример использования:
Пусть q=8, b=4

<math>LS=

\begin{bmatrix} 1 & 7 & 3 & 8 & 5 & 6 & 4 & 2\\ 2 & 5 & 4 & 6 & 7 & 8 & 3 & 1\\ 3 & 8 & 1 & 7 & 6 & 5 & 2 & 4\\ 4 & 6 & 2 & 5 & 8 & 7 & 1 & 3\\ 7 & 1 & 8 & 3 & 4 & 2 & 5 & 6\\ 8 & 3 & 7 & 1 & 2 & 4 & 6 & 5\\ 5 & 2 & 6 & 4 & 3 & 1 & 7 & 8\\ 6 & 4 & 5 & 2 & 1 & 3 & 8 & 7\\ \end{bmatrix}

</math>

<math>LS^1=

\begin{bmatrix} 7 & 1 & 8 & 3 & 4 & 2 & 5 & 6\\ 5 & 2 & 6 & 4 & 3 & 1 & 7 & 8\\ 1 & 7 & 3 & 8 & 5 & 6 & 4 & 2\\ 3 & 8 & 1 & 7 & 6 & 5 & 2 & 4\\ 8 & 3 & 7 & 1 & 4 & 4 & 6 & 5\\ 6 & 4 & 5 & 2 & 1 & 3 & 8 & 7\\ 2 & 5 & 4 & 6 & 7 & 8 & 3 & 1\\ 4 & 6 & 2 & 5 & 8 & 7 & 1 & 3\\ \end{bmatrix} </math> <math>LS^2= \begin{bmatrix} 8 & 3 & 7 & 1 & 2 & 4 & 6 & 5\\ 4 & 6 & 2 & 5 & 8 & 7 & 1 & 3\\ 5 & 2 & 6 & 4 & 3 & 1 & 7 & 8\\ 1 & 7 & 3 & 8 & 5 & 6 & 4 & 2\\ 7 & 1 & 8 & 3 & 4 & 2 & 5 & 6\\ 3 & 8 & 1 & 7 & 6 & 5 & 2 & 4\\ 6 & 4 & 5 & 2 & 1 & 3 & 8 & 7\\ 2 & 5 & 4 & 6 & 3 & 8 & 3 & 1\\ \end{bmatrix}

</math>

и

<math>LS^3=

\begin{bmatrix} 1&7&3&8&5&6&4&2\\ 3&8&1&7&6&5&2&4\\ 7&1&8&3&4&2&5&6\\ 5&2&6&4&3&1&7&8\\ 2&5&4&6&7&8&3&1\\ 4&6&2&5&8&7&1&3\\ 8&3&7&1&2&4&6&5\\ 6&4&5&2&1&3&8&7\\ \end{bmatrix} </math><math>LS^4= \begin{bmatrix} 4&6&2&5&8&7&1&3\\ 2&5&4&6&7&8&3&1\\ 6&4&5&2&1&3&8&7\\ 8&3&7&1&2&4&6&5\\ 3&8&1&7&6&5&2&4\\ 1&7&3&8&5&6&4&2\\ 5&2&6&4&3&1&7&8\\ 7&1&8&3&4&2&5&6\\ \end{bmatrix} </math>

Предположим что передаётся следующее сообщение:

<math>M=

\begin{bmatrix} 3 & 2 & 5 & 4 & 1 & 2 & 1 & 6\\ 7 & 8 & 4 & 5 & 2 & 3 & 3 & 1\\ 4 & 8 & 6 & 7 & 5 & 4 & 3 & 2\\ 1 & 4 & 5 & 7 & 8 & 6 & 6 & 6\\ 7 & 1 & 2 & 8 & 7 & 3 & 4 & 5\\ 7 & 8 & 1 & 1 & 8 & 2 & 6 & 5\\ 3 & 4 & 8 & 1 & 2 & 3 & 7 & 6\\ 2 & 4 & 5 & 3 & 3 & 6 & 8 & 7\\ \end{bmatrix}

</math>

Перемещения строк для получения матриц с <math>LS^1 </math> до <math>LS^4</math>
<math> RP^1= \begin{bmatrix} 5 & 7 & 1 & 3 & 6 & 8 & 2 & 4\\ \end{bmatrix}</math>
<math> RP^2= \begin{bmatrix} 6 & 4 & 7 & 1 & 5 & 3 & 8 & 2\\ \end{bmatrix}</math>
<math> RP^3= \begin{bmatrix} 1 & 3 & 5 & 7 & 2 & 4 & 6 & 8\\ \end{bmatrix}</math>
<math> RP^4= \begin{bmatrix} 4 & 2 & 8 & 6 & 3 & 1 & 7 & 5\\ \end{bmatrix}</math>

Зададим вектор <math> D= \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ \end{bmatrix}</math>
И будем считать хеш по алгоритму приведённому выше:
Получим <math> D= \begin{bmatrix} 1 & 7 & 5 & 4 & 4 & 5 & 8 & 1\\ \end{bmatrix}</math>

Применение в криптографии. Схема разделения секрета

Схема с разделением секрета, в которой ключом является латинский квадрат <math>L</math> порядка <math>n</math>. Латинский квадрат держится в секрете. Между тем порядок латинского квадрата публикуется для всех. Разделение секрета основано на частичных латинских квадратах <math>S</math>={<math>A_{i}</math> | <math>A_{i}</math> критические множества <math>L</math>}. Объединение может быть составлено из всех возможных критических множеств L или из множества критических множеств. Количество критических множеств зависит от порядка латинского квадрата и числа участников, участвующих в схеме.
Протокол:
Выбирается латинский квадрат L. Порядок n разглашается, но сам латинский квадрат остаётся в секрете и используется как ключ.
Множество S объединение критических множеств L.
Каждый участник получает долю (i, j, k) .
Когда участники собираются вместе они могут соединить свои части вместе и восстановить квадрат L.
Пример:
Выделим три частичных квадрата: <math>C_{1}, C_{2}, C_{3}</math>

<math>

\begin{bmatrix} 0 & . & . \\ . & 2 & . \\ . & . & . \\ \end{bmatrix} \quad\quad \begin{bmatrix} . & . & . \\ . & 2 & . \\ . & . & 1 \\ \end{bmatrix} \quad\quad \begin{bmatrix} 0 & . & . \\ . & . & . \\ . & . & 1 \\ \end{bmatrix}

</math>

И целый квадрат L

0	1	2
1	2	0
2	0	1

Мы можем легко убедиться, что все частные латинские квадраты <math>C_{1}</math>, <math>C_{2}</math>, <math>C_{3}</math> являются критическими множествами. Они могут быть однозначно расширены до полного латинского квадрата L. Это уникальное свойство теряется если любой элемент любого частичного латинского квадрата <math>C_{1}</math>, <math>C_{2}</math>, <math>C_{3}</math> удаляется.
Пусть <math>S</math> объединение трёх критических наборов <math>C_{1}</math>, <math>C_{2}</math>, <math>C_{3}</math> . Тогда <math>S</math> = <math> {(1, 1, 1), (2, 2, 3), (3, 3, 2)}</math>.
Мы распространяем трём участникам части <math>S</math>. Любые два участника могут восстановить полный латинский квадрат.
Полученный выше простой пример может быть расширен до общего случая.
В 1979 латинский квадрат был предложен в качестве хорошего кандидата для использования в секретных схемах распределения. Однако, Есть определённые ограничения для его применения, как описано ниже.
1) Сразу после распределения частей критического множества, частичная информация будет доступна любой несанкционированной группе. Это означает, что есть высокий шанс для любой несанкционированной группе, чтобы выяснить остальные части методом проб и ошибок. Таким образом, предложенная схема не идеальна.
2) Схема не является гибкой. В данном случае это просто схема расщепления секрета.
Хеширование
Если мы хотим, использовать хеш-сумму для хранения фиксированного секретного квадрата, например, латинского квадрата порядка 10, мы должны хранить 81 номер (последнюю строку и столбец хранить не обязательно). Четыре бита могут быть использованы для хранения ряда, так что нам понадобится 324 бит. В этом случае, мы можем выбрать SHA-384 или SHA-512. Если нам нужно использовать SHA-256, мы можем проступить следующим образом. 10 бит будем использовать для представления 3-го номера. Таким образом, мы сначала использовали 250 бит для представления 75 чисел, а затем следующие 4 бита для представления одного номера. В общей сложности, мы можем хранить 76 номеров. Зафиксируем частичный латинский квадрат в следующем формате. Выберем латинский квадрат порядка 10, который можно восстановить однозначно, удалив записи, как показано в таблице. Компромиссом здесь является то, что небольшой процент латинских квадратов порядка 10, не могут быть восстановлены однозначно и, следовательно, не могут быть выбран в качестве секрета.

x	x	x	x	x	x	x	x	x	.
x	x	x	x	x	x	x	x	x	.
x	x	x	x	x	x	x	x	x	.
x	x	x	x	x	x	x	x	x	.
x	x	x	x	x	x	x	x	.	.
x	x	x	x	x	x	x	x	.	.
x	x	x	x	x	x	x	x	.	.
x	x	x	x	x	x	x	x	.	.
x	x	x	x	x	x	x	x	.	.
.	.	.	.	.	.	.	.	.	.

Игры и головоломки с латинскими квадратами

Существует ряд игр, в которых используются латинские квадраты. Наиболее известна из них судоку. В ней требуется частичный квадрат дополнить до латинского квадрата 9-го порядка, обладающего дополнительным свойством: все девять его подквадратов содержат по одному разу все натуральные числа от 1 до 9.

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

См. также

• Ортогональный массив
• Магический квадрат
• Судоку
• SAT@home проект распределённых вычислений, занимающийся поиском ортогональных пар латинских квадратов 9 и 10 порядка.

Литература

• Холл М. Комбинаторика, пер. с англ. М., 1970.
• Dénes J. H., Keedwell A. D. Latin Squares and their Applications. Budapest, 1974.
• Сачков В. Н. Комбинаторные методы дискретной математики. М., 1977.
• Dénes J. H., Keedwell A. D. Latin squares: New developments in the theory and applications. Annals of Discrete Mathematics vol. 46. Academic Press. Amsterdam. 1991.
• Laywine C.F., Mullen G.L. Discrete mathematics using Latin squares. New York, 1998.
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья

Ссылки

• Шаблон:Статья
• Шаблон:Статья