e-olymp 4853. Кратчайший путь

14.06.2017 by Маша Лукьянова

Условие:

Задан неориентированный граф. Найдите кратчайший путь от вершины $start$ до вершины $end$.

Входные данные:

В первой строке находится два целых числа $n$ и $m$ $ (1 ≤ n ≤ 50000, 1 ≤ m ≤ 100000)$ — количества вершин и рёбер соответственно. Во второй строке заданы целые числа $start$ и $end$ — стартовая и конечная вершина соответственно. Далее идут $m$ строк, описывающие рёбра.

Выходные данные:

Если пути между $start$ и $end$ нет, то выведите $-1$. Иначе выведите в первой строке длину $l$ кратчайшего пути между этими двумя вершинами в рёбрах, а во второй строке выведите $l + 1$ число — вершины этого пути.

Тесты:

№	Входные данные	Выходные данные
1	4 5 1 4 1 3 3 2 2 4 2 1 2 3	2 1 2 4
2	5 3 1 4 2 3 3 5 3 4	-1
3	5 4 1 4 1 2 2 3 3 5 3 4	3 1 2 3 4

Решение:

Поскольку нам необходимо найти кратчайшее расстояние между вершинами реализуем поиском в ширину. Запомним посещенные вершины в массиве [latex]used[/latex], родительские вершины в массиве [latex]parent[/latex], а план посещений в списке [latex]plan[/latex].

Изначально в списке [latex]plan[/latex] находится единственная вершина $start$. Каждый шаг начинается с того, что мы берем первую вершину из списка [latex]plan[/latex], отмечаем ее как посещенную, удаляем из списка и после посещаем все ее соседние вершины, которые еще не были посещены.

Когда очередь опустеет, обход в ширину обойдёт все достижимые из [latex]point[/latex] вершины, причём до каждой дойдёт кратчайшим путём. После того, как кратчайший путь найден — мы с помощью массива «предков» восстанавливаем его.

import cpp.vm.Gc;
import cpp.Lib;
import sys.io.*;

class Main {
	
    static function main() {
		var n = 5;
		var m = 4;
		
		var g = new Array < Array<Int> >(); 	//граф
		
		var taskIn = new Array < Array<Int> >();	//ввод
		
		for (i in 0...n){
			g[i] = new Array <Int>();
		}
		
		var start = 1; //начальная вершина
		var end = 4; //конечная вершина
		
		--start;
		--end;
		
		taskIn.push([2, 3]); //вводимые ребра
		taskIn.push([1, 2]);
		taskIn.push([3, 5]);
		taskIn.push([3, 4]);
		taskIn.push([4, 3]);
		
		
		
		for (x in taskIn){
			var v1 = --x[0]; // декремент -> нумерация с 0
			var v2 = --x[1];

			g[v1].push(v2);
			g[v2].push(v1);
			
		}
		
		var plan = new List<Int>();
		var used = new Array<Bool>();
		var parent = new Array<Int>();
		
		
		for (i in 0...n){
			used.push(false);
			parent.push(0);
		}
		
		
		plan.add(start);
		used [start] = true;
		parent [start] = start;
		
		var point : Int = start;

		//пока не достигли конца и пока план не пуст
		while (point != end && !plan.isEmpty()){  
			point = plan.first();
			plan.pop();
			
			for (x in g[point]){
				
				if (!used[x]){
					used[x] = true;
					plan.add(x);
					parent[x] = point;
				}
			}
		}
		

		var answ: String = "";	//ответ
		
		if (point == end){	//если достигли конца -> путь существует
			var path = new Array<Int>();
			
			while (point != start){
				path.push(point);
				point = parent[point];
			}
			
			path.push(start);
			path.reverse();
			
			trace (path.length - 1);
			for (x in path)
				answ += x + 1 + " ";
		}else{
			answ = -1 + "";
		}
		trace(answ);

		
    }
}

import cpp.vm.Gc;

import cpp.Lib;

import sys.io.*;

class Main {

static function main() {

var n = 5;

var m = 4;

var g = new Array < Array<Int> >(); //граф

var taskIn = new Array < Array<Int> >(); //ввод

for (i in 0...n){

g[i] = new Array <Int>();

}

var start = 1; //начальная вершина

var end = 4; //конечная вершина

--start;

--end;

taskIn.push([2, 3]); //вводимые ребра

taskIn.push([1, 2]);

taskIn.push([3, 5]);

taskIn.push([3, 4]);

taskIn.push([4, 3]);

for (x in taskIn){

var v1 = --x[0]; // декремент -> нумерация с 0

var v2 = --x[1];

g[v1].push(v2);

g[v2].push(v1);

}

var plan = new List<Int>();

var used = new Array<Bool>();

var parent = new Array<Int>();

for (i in 0...n){

used.push(false);

parent.push(0);

}

plan.add(start);

used [start] = true;

parent [start] = start;

var point : Int = start;

//пока не достигли конца и пока план не пуст

while (point != end && !plan.isEmpty()){

point = plan.first();

plan.pop();

for (x in g[point]){

if (!used[x]){

used[x] = true;

plan.add(x);

parent[x] = point;

}

var answ: String = ""; //ответ

if (point == end){ //если достигли конца -> путь существует

var path = new Array<Int>();

while (point != start){

path.push(point);

point = parent[point];

}

path.push(start);

path.reverse();

trace (path.length - 1);

for (x in path)

answ += x + 1 + " ";

}else{

answ = -1 + "";

}

trace(answ);

}

try online

Алгоритм шифрования MARS

06.05.2017 by Маша Лукьянова

MARS — шифр-кандидат в AES был разработан коллективом криптологов из корпорации IBM. Именно IBM в свое время разработала семейство алгоритмов Lucifer, которое легло в основу прошлого стандарта шифрования США — DES.

Cтруктура алгоритма:

Предварительное наложение ключа: на [latex]32[/latex]-битные субблоки [latex]A, B, C, D[/latex] накладываются [latex]4[/latex] фрагмента расширенного ключа [latex]k_{0}…k_{3}[/latex] операцией сложения по модулю [latex]2^{32}[/latex];
Выполняются [latex]8[/latex] раундов прямого перемешивания (без участия ключа шифрования);
Выполняются [latex]8[/latex] раундов прямого криптопреобразования;
Выполняются [latex]8[/latex] раундов обратного криптопреобразования;
Выполняются [latex]8[/latex] раундов обратного перемешивания, также без участия ключа шифрования;
Финальное наложение фрагментов расширенного ключа [latex]k_{36}…k_{39}[/latex] операцией вычитания по модулю [latex]2^{32}[/latex].

Алгоритм уникален тем, что использовал практически все существующие технологии, применяемые в криптоалгоритмах, а именно:

простейшие операции сложение, вычитание, исключающее или
подстановки с использованием таблицы замен
фиксированный циклический сдвиг
зависимый от данных циклический сдвиг
умножение по модулю [latex]2^{32}[/latex]
ключевое забеливание

Следовательно, для реализации алгоритма было бы удобно завести некоторую «обертку» над [latex]32[/latex] битным интом (поскольку мы оперируем [latex]32[/latex]-битными субблоками).

Нам понадобится реализовать:

циклический сдвиг влево/вправо на [latex]n[/latex]-ое кол-во бит
выделение [latex]n[/latex]-ого байта из субблока
выделение последних [latex]n[/latex] бит из субблока

Реализуем новый абстрактный тип Integer (прежде стоит ознакомиться с логическими операциями):

package;
import cpp.UInt32;


abstract Integer {

    public inline function new(p : UInt32 ) {
 
        this = p;
    } 

    //переопределение операторов
    @:op(A ^= B ) 
    public inline function xor(rhs : UInt32) : Integer {

        this ^= rhs;
		return new Integer(this);
    }
	
	@:op(A *= B ) 
    public inline function mult(rhs : UInt32) : Integer {

        this *= rhs;
		return new Integer(this);
    }
	
	@:op(A |= B ) 
    public inline function or(rhs : UInt32) : Integer {

        this |= rhs;
		return new Integer(this);
    }

	@:op(A += B ) 
    public inline function summ (rhs : UInt32) : Integer {

        this += rhs;
		return new Integer(this);
    }
		
	@:op(A -= B ) 
    public inline function sub(rhs : UInt32) : Integer {

        this -= rhs;
		return new Integer(this);
    }
	
	@:op(A - B ) 
    public inline function subI(rhs : Integer) : Integer {

		return new Integer(this - rhs.GetValue());
    }
	
	@:op(A + B ) 
    public function summI(rhs : Integer) : Integer {

		return new Integer(this + rhs.GetValue());
    }
	
	@:op(A ^ B ) 
    public function xorI(rhs : Integer) : Integer {

		return new Integer(this ^ rhs.GetValue());
    }
	
	@:op(A * B ) 
    public function multI(rhs : Integer) : Integer {

		return new Integer(this * rhs.GetValue());
    } 
}

package;

import cpp.UInt32;

abstract Integer {

public inline function new(p : UInt32 ) {

this = p;

}

//переопределение операторов

@:op(A ^= B )

public inline function xor(rhs : UInt32) : Integer {

this ^= rhs;

return new Integer(this);

}

@:op(A *= B )

public inline function mult(rhs : UInt32) : Integer {

this *= rhs;

return new Integer(this);

}

@:op(A |= B )

public inline function or(rhs : UInt32) : Integer {

this |= rhs;

return new Integer(this);

}

@:op(A += B )

public inline function summ (rhs : UInt32) : Integer {

this += rhs;

return new Integer(this);

}

@:op(A -= B )

public inline function sub(rhs : UInt32) : Integer {

this -= rhs;

return new Integer(this);

}

@:op(A - B )

public inline function subI(rhs : Integer) : Integer {

return new Integer(this - rhs.GetValue());

}

@:op(A + B )

public function summI(rhs : Integer) : Integer {

return new Integer(this + rhs.GetValue());

}

@:op(A ^ B )

public function xorI(rhs : Integer) : Integer {

return new Integer(this ^ rhs.GetValue());

}

@:op(A * B )

public function multI(rhs : Integer) : Integer {

return new Integer(this * rhs.GetValue());

}

Добавим методы циклического сдвига:

    //циклический сдвиг влево на countOfbits
    public inline function LeftCyclicShift(countOfbits : Int) {

        countOfbits %= 32;
        var ones : Int = this;
        ones >>>= (32 - countOfbits);
        this <<= countOfbits;
        this |= ones;
    }

//циклический сдвиг влево на countOfbits

public inline function LeftCyclicShift(countOfbits : Int) {

countOfbits %= 32;

var ones : Int = this;

ones >>>= (32 - countOfbits);

this <<= countOfbits;

this |= ones;

}

Для наглядности подробно разберем принцип работы одного из методов, основанных на битовых операциях, для краткости возьмем не [latex]32[/latex]-битное число, а [latex]8[/latex]-битное. Пусть нам нужен циклический сдвиг влево на [latex]4[/latex] бита.

Из этого следует что, нам нужно сдвинуть входное число на [latex]4[/latex] бита влево, предварительно сохранив [latex]4[/latex] старших бита, чтобы не потерять их. Для этого воспользуемся операцией сдвига вправо на [latex]n — 4[/latex] бита с заполнением нулями, где [latex]n[/latex] — максимальное кол-во бит в числе. Сохраним результат в переменную ones .

Далее сдвинем исходное слово на [latex]4[/latex] бита влево и операцией «побитовое или» соединим с ones.

Аналогично реализуем метод циклического сдвига вправо:

    //Циклический сдвиг вправо на countOfbits бит   
    public inline function RightCyclicShift(countOfbits : Int) {

        countOfbits %= 32; 
        var ones : Int = this;
        ones <<= (32 - countOfbits);
        this >>>= countOfbits;
        this |= ones;
    }

//Циклический сдвиг вправо на countOfbits бит

public inline function RightCyclicShift(countOfbits : Int) {

countOfbits %= 32;

var ones : Int = this;

ones <<= (32 - countOfbits);

this >>>= countOfbits;

this |= ones;

}

Так же нам потребуется реализовать метод выделения [latex]n[/latex]-ого байта из субблока. Для этого мы будем сдвигать требуемый байт на место младшего байта и выделим его с помощью операции «логическое и» маской [latex]255[/latex] (в битовом представлении подряд идущих [latex]8[/latex] единиц, начиная с младшего бита) .

    public function GetByte(i : Int) : UInt32 {

        if (i < 0 || i > 3)
            throw "4 bytes max";
        var curr = (this >>> 8 * i) & 255;
        return curr;
    }

public function GetByte(i : Int) : UInt32 {

if (i < 0 || i > 3)

throw "4 bytes max";

var curr = (this >>> 8 * i) & 255;

return curr;

}

Осталось реализовать метод выделения последних [latex]n[/latex] бит из субблока. Для этого мы сначала сдвинем число влево на ([latex]32 — n[/latex]), чтобы на место старших бит встали искомые биты (таким образом стерев ненужные биты). А затем сдвинем их на место младших битов (то есть вправо с заполнением нулями на [latex]32 — n[/latex]).

    public function GetBites (countOfbits : UInt32) : UInt32 {

        countOfbits %= 32;
        var value = this;
        value << (32 - countOfbits);
        return value >>> (32 - countOfbits);
    }

public function GetBites (countOfbits : UInt32) : UInt32 {

countOfbits %= 32;

var value = this;

value << (32 - countOfbits);

return value >>> (32 - countOfbits);

}

Для работы алгоритма потребуется объявить некоторые элементы ([latex]S[/latex] и [latex]B[/latex] блоки) — они описаны в конце статьи.

Прямое перемешивание:

Раунд прямого перемешивания показан на рисунке [latex]1[/latex], в раунде выполняются следующие действия:

Значение субблока [latex]A[/latex] прогоняется через таблицу замен [latex]S0[/latex] и накладывается на субблок [latex]B[/latex] операцией [latex]XOR[/latex].
Исходное значение субблока [latex]A[/latex] вращается на [latex]8[/latex] бит вправо.
Результат предыдущего шага обрабатывается таблицей замен [latex]S1[/latex] и снова накладывается на субблок [latex]B[/latex] операцией сложения по модулю [latex]32[/latex].
Результат шага [latex]2[/latex] вращается на [latex]8[/latex] бит вправо.
Результат предыдущего шага обрабатывается таблицей замен [latex]S0[/latex] и накладывается на субблок [latex]С[/latex] операцией сложения по модулю [latex]32[/latex].
Результат шага [latex]4[/latex] вращается на [latex]8[/latex] бит вправо.
Результат предыдущего шага обрабатывается таблицей замен [latex]S1[/latex] и накладывается на субблок [latex]D[/latex] операцией [latex]XOR[/latex].
Субблоки меняются местами, как показано на рис. [latex]1[/latex].

Кроме того, в некоторых раундах прямого перемешивания выполняются следующие дополнительные операции (не приведены на рис. [latex]1[/latex]):
В раундах [latex]0[/latex] и [latex]4[/latex] после шага [latex]7[/latex] выполняется наложение значения субблока [latex]D[/latex] на субблок [latex]A[/latex] операцией сложения по модулю .
В раундах [latex]1[/latex] и [latex]5[/latex] субблок [latex]B[/latex] аналогичным образом накладывается на субблок [latex]A[/latex].

рис. 1.

Стоит заметить, что каждый раз, «прогоняя» [latex]i[/latex]-ий субблок через [latex]S[/latex] блоки мы берем последние [latex]8[/latex] бит, то есть байт субблока и его значение используем в качестве индексного обращения к блоку [latex]S[/latex]. (Понятно, что в блоках [latex]256[/latex] элементов. О правилах их получения рассказывается ниже).

Для простоты, мы будем возвращать для «прогона» каждый раз не последний байт, а младший, первый, второй и старший. Потом мы подвинем субблок вправо сразу на [latex]24[/latex] бита.

Заведем класс subblock, который будет содержать четыре [latex]32[/latex]-битные посылки и расширенный ключ (о его получении мы поговорим ниже).

class Block {	
	
		public var subblock = new Array<Integer>();
		var K : Key;
		
		public function new(A : UInt32, B : UInt32, C : UInt32, D : UInt32, K : Key) {

			subblock.push(new Integer(A));
			subblock.push(new Integer(B));
			subblock.push(new Integer(C));
			subblock.push(new Integer(D));
			this.K = K;
		}
}

class Block {

public var subblock = new Array<Integer>();

var K : Key;

public function new(A : UInt32, B : UInt32, C : UInt32, D : UInt32, K : Key) {

subblock.push(new Integer(A));

subblock.push(new Integer(B));

subblock.push(new Integer(C));

subblock.push(new Integer(D));

this.K = K;

}

Теперь добавим в него метод прямого перемешивания:

		public function ForwardPass(i : Int) {

			// обращаемся к 4-ем S-блокам
			subblock[1] ^= MARSInfo.S0[subblock[0].GetByte(0)]; 
			subblock[1] += MARSInfo.S1[subblock[0].GetByte(1)];
			subblock[2] += MARSInfo.S0[subblock[0].GetByte(2)];
			subblock[3] ^= MARSInfo.S1[subblock[0].GetByte(3)];
			
			subblock[0].RightCyclicShift(24);
			
			// также проделаем дополнительные операции смешивания
			if (i == 0 || i == 4)
				subblock[0] += subblock[3];
			if (i == 1 || i == 5)
				subblock[0] += subblock[1];
			
			subblock.push(subblock[0]);
			subblock.splice(0, 1);
		}

public function ForwardPass(i : Int) {

// обращаемся к 4-ем S-блокам

subblock[1] ^= MARSInfo.S0[subblock[0].GetByte(0)];

subblock[1] += MARSInfo.S1[subblock[0].GetByte(1)];

subblock[2] += MARSInfo.S0[subblock[0].GetByte(2)];

subblock[3] ^= MARSInfo.S1[subblock[0].GetByte(3)];

subblock[0].RightCyclicShift(24);

// также проделаем дополнительные операции смешивания

if (i == 0 || i == 4)

subblock[0] += subblock[3];

if (i == 1 || i == 5)

subblock[0] += subblock[1];

subblock.push(subblock[0]);

subblock.splice(0, 1);

}

Процесс кодирования алгоритма Mars обратен процессу декодирования. По этому сразу добавим обратный метод. Назовем его backward pass, чтобы не менять порядок следования функции в методе дешифрования, и добавим, в начало названия префикс [latex]d[/latex], чтобы обозначить его принадлежность к методам декодирования. Стоит отметить, что перед этим стоит ознакомиться с понятием обратных операций.

		public function DBackwardPass(i : Int) {

			// вращаем массив subblock[]
			subblock.insert(0, subblock[subblock.length - 1]);
			subblock.splice(subblock.length - 1, 1);
			
			// дополнительное смешивание
			if (i == 0 || i == 4)
				subblock[0] -= subblock[3];
			else if (i == 1 || i == 5)
				subblock[0] -= subblock[1];
			// и вращаем исходное слово влево
			subblock[0].LeftCyclicShift(24);
			 // обращаемся к 4-ем элементам S-блоков
			subblock[3] ^= MARSInfo.S1[subblock[0].GetByte(3)];
			subblock[2] -= MARSInfo.S0[subblock[0].GetByte(2)];
			subblock[1] -= MARSInfo.S1[subblock[0].GetByte(1)];
			subblock[1] ^= MARSInfo.S0[subblock[0].GetByte(0)];
		}

public function DBackwardPass(i : Int) {

// вращаем массив subblock[]

subblock.insert(0, subblock[subblock.length - 1]);

subblock.splice(subblock.length - 1, 1);

// дополнительное смешивание

if (i == 0 || i == 4)

subblock[0] -= subblock[3];

else if (i == 1 || i == 5)

subblock[0] -= subblock[1];

// и вращаем исходное слово влево

subblock[0].LeftCyclicShift(24);

// обращаемся к 4-ем элементам S-блоков

subblock[3] ^= MARSInfo.S1[subblock[0].GetByte(3)];

subblock[2] -= MARSInfo.S0[subblock[0].GetByte(2)];

subblock[1] -= MARSInfo.S1[subblock[0].GetByte(1)];

subblock[1] ^= MARSInfo.S0[subblock[0].GetByte(0)];

}

Криптографическое преобразование:

Криптографическое ядро MARS — сеть Фейстеля 3-го типа, содержащая в себе [latex]16[/latex] раундов. [latex]8[/latex] раундов прямого (рис. 2) и [latex]8[/latex] раундов обратного криптопреобразования (рис. 3). В каждом раунде мы используем ключевую [latex]Е[/latex]-функцию, которая является комбинацией умножений, вращений, а также обращений к [latex]S[/latex]-блокам. Функция принимает на вход одно слово данных, а возвращает три слова, с которыми впоследствии будет осуществлена операция сложения или [latex]XOR[/latex] к другим трем словам данным. В дополнении исходное слово вращается на [latex]13[/latex] бит влево.

рис.2.

Для обеспечения, серьёзного сопротивления к криптоатакам, три выходных значения [latex]Е[/latex]-функции ([latex]O_{1}[/latex], [latex]O_{2}[/latex], [latex]O_{3}[/latex]) используются в первых восьми раундах и в последних восьми раундах в разных порядках. В первые восемь раундов мы добавляем [latex]O_{1}[/latex] и [latex]O_{2}[/latex] к первому и второму целевому слову, соответственно, и [latex]XOR[/latex] [latex]O_{3}[/latex] к третьему целевому слову. За последние восемь раундов, мы добавляем [latex]O_{1}[/latex] и [latex]O_{2}[/latex] к третьему и второму целевому слову, соответственно, и [latex]XOR[/latex] [latex]O_{3}[/latex] к первому целевому слову.

рис.3.

		public function Crypto(i: Int) {

			// три выходных значения O0, O1, 02
			var O = E (subblock[0], i);
			subblock[0].LeftCyclicShift(13);
			subblock[2] += O[1];
			
			if (i < 8) {
				subblock[1] += O[0];
				subblock[3] ^= O[2];
			}
			else{
				subblock[3] += O[0];
				subblock[1] ^= O[2];
			}
			
			subblock.push(subblock[0]);
			subblock.splice(0, 1);
		}

public function Crypto(i: Int) {

// три выходных значения O0, O1, 02

var O = E (subblock[0], i);

subblock[0].LeftCyclicShift(13);

subblock[2] += O[1];

if (i < 8) {

subblock[1] += O[0];

subblock[3] ^= O[2];

}

else{

subblock[3] += O[0];

subblock[1] ^= O[2];

}

subblock.push(subblock[0]);

subblock.splice(0, 1);

}

Для декодирования:

		public function DCrypto(i : Int) {

			// вращаем массив subblock[]
			subblock.insert(0, subblock[subblock.length - 1]);
			subblock.splice(subblock.length - 1, 1);
			
			// и вращаем исходное слово вправо
			subblock[0].RightCyclicShift(13);
			var O = E(subblock[0], i);
			subblock[2] -= O[1];
			// последние 8 раундов в прямом порядке
			if (i < 8){
				subblock[1] -= O[0];
				subblock[3] ^= O[2];
			}
			else {
				subblock[3] -= O[0];
				subblock[1] ^= O[2];
			}
		}

public function DCrypto(i : Int) {

// вращаем массив subblock[]

subblock.insert(0, subblock[subblock.length - 1]);

subblock.splice(subblock.length - 1, 1);

// и вращаем исходное слово вправо

subblock[0].RightCyclicShift(13);

var O = E(subblock[0], i);

subblock[2] -= O[1];

// последние 8 раундов в прямом порядке

if (i < 8){

subblock[1] -= O[0];

subblock[3] ^= O[2];

}

else {

subblock[3] -= O[0];

subblock[1] ^= O[2];

}

[latex]E[/latex]-функция

[latex]E[/latex]-функция принимает в качестве входных данных одно слово данных и использует ещё два слова расширенного ключа с индексами [latex]2*i + 4[/latex] и [latex]2*i + 5[/latex] , производя на выходе три слова. В этой функции мы используем три временные переменные, обозначаемые [latex]L[/latex], [latex]M[/latex] и [latex]R[/latex] (для левой, средней и правой).

<p\>Изначально мы устанавливаем в [latex]R[/latex] значение исходного слова смещенного на [latex]13[/latex] бит влево, а в [latex]M[/latex] — сумма исходных слов и первого ключевого слова. Затем мы используем первые девять битов [latex]M[/latex] как индекс к одной из [latex]512[/latex] [latex]S[/latex]-блоков (которое получается совмещением [latex]S0[/latex] и [latex]S1[/latex] смешиванием фазы), и сохраняем в [latex]L[/latex] значение соответствующего [latex]S[/latex]-блока.

Затем умножим второе ключевое слово на [latex]R[/latex], сохранив значение в [latex]R[/latex]. Затем вращаем [latex]R[/latex] на [latex]5[/latex] позиций влево (так, [latex]5[/latex] старших битов становятся [latex]5[/latex] нижними битами [latex]R[/latex] после вращения). Тогда мы делаем [latex]XOR[/latex] [latex]R[/latex] в [latex]L[/latex], а также просматриваем пять нижних бит [latex]R[/latex] для определения величины сдвига (от [latex]0[/latex] до [latex]31[/latex]), и вращаем [latex]M[/latex] влево на эту величину. Далее мы вращаем [latex]R[/latex] ещё на [latex]5[/latex] позиций влево и делаем [latex]XOR[/latex] в [latex]L[/latex]. В заключении, мы вновь смотрим на [latex]5[/latex] младших битов [latex]R[/latex], как на величину вращения и вращаем [latex]L[/latex] на эту величину влево. Таким образом результат работы [latex]E[/latex]-функции — [latex]3[/latex] слова (по порядку): [latex]L, M, R[/latex].

		private function E(subblock : Integer, i : Int) : Array <UInt32>  {

			var M = subblock;
			M += K.getElement(2 * i + 4);
			var R = subblock;
			R.LeftCyclicShift(13);
			R *= K.getElement(2 * i + 5);
			var i = M.GetBites(9);
			var L : Integer;
			if (i < 256)
				L = new Integer(MARSInfo.S0[i]);
			
			else
				L = new Integer(MARSInfo.S1[i % 256]);
				M.LeftCyclicShift(R.GetBites(5));
				L ^= R;
				R.LeftCyclicShift(5);
				L ^= R;
				L.LeftCyclicShift(R.GetBites(5));
				return [L.GetValue(), M.GetValue(), R.GetValue()];
			
		}

private function E(subblock : Integer, i : Int) : Array <UInt32> {

var M = subblock;

M += K.getElement(2 * i + 4);

var R = subblock;

R.LeftCyclicShift(13);

R *= K.getElement(2 * i + 5);

var i = M.GetBites(9);

var L : Integer;

if (i < 256)

L = new Integer(MARSInfo.S0[i]);

else

L = new Integer(MARSInfo.S1[i % 256]);

M.LeftCyclicShift(R.GetBites(5));

L ^= R;

R.LeftCyclicShift(5);

L ^= R;

L.LeftCyclicShift(R.GetBites(5));

return [L.GetValue(), M.GetValue(), R.GetValue()];

}

Обратное перемешивание:

Раунд обратного перемешивания (см. рис. 4) более существенно отличается от прямого. Фактически, обратное перемешивание выполняет обратные операции в обратной последовательности (см. рис. 1 и 4):

Значение субблока [latex]A[/latex] прогоняется через таблицу замен [latex]S1[/latex] и накладывается на субблок [latex]B[/latex] операцией XOR.
Исходное значение субблока [latex]A[/latex] вращается на [latex]8[/latex] бит влево.
Результат предыдущего шага обрабатывается таблицей замен [latex]S0[/latex] и накладывается на субблок [latex]C[/latex] операцией вычитания по модулю [latex]2^{32}[/latex]/>.
Результат шага [latex]2[/latex] вращается на [latex]8[/latex] бит влево.
Результат предыдущего шага обрабатывается таблицей замен [latex]S1[/latex] и накладывается на субблок [latex]D[/latex] операцией вычитания по модулю [latex]2^{32}[/latex] />.
Результат шага [latex]4[/latex] вращается на [latex]8[/latex] бит влево.
Результат предыдущего шага обрабатывается таблицей замен [latex]S0[/latex] и накладывается на субблок [latex]D[/latex] операцией [latex]XOR[/latex].
Субблоки меняются местами, как показано на рис. 4.

Аналогично прямому перемешиванию, в некоторых раундах выполняются следующие дополнительные операции, не показанные на рис. 4:
— В раундах [latex]1[/latex] и [latex]5[/latex] после шага [latex]7[/latex] выполняется наложение значения субблока [latex]A[/latex] на субблок [latex]B[/latex] операцией вычитания по модулю [latex]2^{32}[/latex].

— В раундах [latex]2[/latex] и [latex]6[/latex] субблок [latex]C[/latex] аналогичным образом накладывается на субблок [latex]B[/latex].

		public function BackwardPass(i:Int) {

			// также проделаем дополнительные операции смешивания
			if (i == 2 || i == 6)
				subblock[0] -= subblock[3];
			else if (i == 3 || i == 7)
				subblock[0] -= subblock[1];
			
			// обращаемся к 4-ем S-блокам
			subblock[1] ^= MARSInfo.S1[subblock[0].GetByte(0)]; 
			subblock[2] -= MARSInfo.S0[subblock[0].GetByte(3)];
			subblock[3] -= MARSInfo.S1[subblock[0].GetByte(2)];
			subblock[3] ^= MARSInfo.S0[subblock[0].GetByte(1)];
			
			subblock[0].LeftCyclicShift(24);
			var a = new Integer(MARSInfo.S1[subblock[0].GetByte(0)]);
			subblock.push(subblock[0]);
			subblock.splice(0, 1);		
		}

public function BackwardPass(i:Int) {

// также проделаем дополнительные операции смешивания

if (i == 2 || i == 6)

subblock[0] -= subblock[3];

else if (i == 3 || i == 7)

subblock[0] -= subblock[1];

// обращаемся к 4-ем S-блокам

subblock[1] ^= MARSInfo.S1[subblock[0].GetByte(0)];

subblock[2] -= MARSInfo.S0[subblock[0].GetByte(3)];

subblock[3] -= MARSInfo.S1[subblock[0].GetByte(2)];

subblock[3] ^= MARSInfo.S0[subblock[0].GetByte(1)];

subblock[0].LeftCyclicShift(24);

var a = new Integer(MARSInfo.S1[subblock[0].GetByte(0)]);

subblock.push(subblock[0]);

subblock.splice(0, 1);

}

и для декодирования:

		public function DForwardPass(i : Int) {

			subblock.insert(0, subblock[subblock.length - 1]);
			subblock.splice(subblock.length - 1, 1);
			
			// и вращаем исходное слово вправо]
			subblock[0].RightCyclicShift(24);
			 // обращаемся к 4-ем элементам S-блоков
			subblock[3] ^= MARSInfo.S0[subblock[0].GetByte(1)];
			subblock[3] += MARSInfo.S1[subblock[0].GetByte(2)];
			subblock[2] += MARSInfo.S0[subblock[0].GetByte(3)];
			subblock[1] ^= MARSInfo.S1[subblock[0].GetByte(0)];
			// дополнительное смешивание
			if (i == 2 || i == 6)
				subblock[0] += subblock[3];
			else if (i == 3 || i == 7)
				subblock[0] += subblock[1];
		}

public function DForwardPass(i : Int) {

subblock.insert(0, subblock[subblock.length - 1]);

subblock.splice(subblock.length - 1, 1);

// и вращаем исходное слово вправо]

subblock[0].RightCyclicShift(24);

// обращаемся к 4-ем элементам S-блоков

subblock[3] ^= MARSInfo.S0[subblock[0].GetByte(1)];

subblock[3] += MARSInfo.S1[subblock[0].GetByte(2)];

subblock[2] += MARSInfo.S0[subblock[0].GetByte(3)];

subblock[1] ^= MARSInfo.S1[subblock[0].GetByte(0)];

// дополнительное смешивание

if (i == 2 || i == 6)

subblock[0] += subblock[3];

else if (i == 3 || i == 7)

subblock[0] += subblock[1];

}

Финальная реализиция класса Block:

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

class Block {		
		public var subblock = new Array<Integer>();
		var K : Key;
		
		public function new(A : UInt32, B : UInt32, C : UInt32, D : UInt32, K : Key) {
			subblock.push(new Integer(A));
			subblock.push(new Integer(B));
			subblock.push(new Integer(C));
			subblock.push(new Integer(D));
			this.K = K;
		}
		
		public function ForwardPass(i : Int) {
			
			// обращаемся к 4-ем S-блокам
			subblock[1] ^= MARSInfo.S0[subblock[0].GetByte(0)]; 
			subblock[1] += MARSInfo.S1[subblock[0].GetByte(1)];
			subblock[2] += MARSInfo.S0[subblock[0].GetByte(2)];
			subblock[3] ^= MARSInfo.S1[subblock[0].GetByte(3)];
			
			subblock[0].RightCyclicShift(24);
			
			// также проделаем дополнительные операции смешивания
			if (i == 0 || i == 4)
				subblock[0] += subblock[3];
			if (i == 1 || i == 5)
				subblock[0] += subblock[1];
			
			subblock.push(subblock[0]);
			subblock.splice(0, 1);
		}
		
		public function DBackwardPass(i : Int) {

			// вращаем массив D[]
			
			subblock.insert(0, subblock[subblock.length - 1]);
			subblock.splice(subblock.length - 1, 1);
			
			// дополнительное смешивание
			if (i == 0 || i == 4)
				subblock[0] -= subblock[3];
			else if (i == 1 || i == 5)
				subblock[0] -= subblock[1];
			// и вращаем исходное слово влево
			subblock[0].LeftCyclicShift(24);
			 // обращаемся к 4-ем элементам S-блоков
			subblock[3] ^= MARSInfo.S1[subblock[0].GetByte(3)];
			subblock[2] -= MARSInfo.S0[subblock[0].GetByte(2)];
			subblock[1] -= MARSInfo.S1[subblock[0].GetByte(1)];
			subblock[1] ^= MARSInfo.S0[subblock[0].GetByte(0)];
		}
		
		private function E(subblock : Integer, i : Int) : Array < UInt32 >  {

			var M = subblock;
			M += K.getElement(2 * i + 4);
			var R = subblock;
			R.LeftCyclicShift(13);
			R *= K.getElement(2 * i + 5);
			var i = M.GetBites(9);
			var L : Integer;
			if (i < 256)
				L = new Integer(MARSInfo.S0[i]);
			
			else
				L = new Integer(MARSInfo.S1[i % 256]);
				M.LeftCyclicShift(R.GetBites(5));
				L ^= R;
				R.LeftCyclicShift(5);
				L ^= R;
				L.LeftCyclicShift(R.GetBites(5));
				return [L.GetValue(), M.GetValue(), R.GetValue()];
			
		}
		public function Crypto(i: Int) {

			var O = E (subblock[0], i);
			subblock[0].LeftCyclicShift(13);
			subblock[2] += O[1];
			
			if (i < 8){
				subblock[1] += O[0];
				subblock[3] ^= O[2];
			}
			else{
				subblock[3] += O[0];
				subblock[1] ^= O[2];
			}
			
			subblock.push(subblock[0]);
			subblock.splice(0, 1);
		}
		
		public function DCrypto(i : Int) {

			// вращаем массив subblock[]
			subblock.insert(0, subblock[subblock.length - 1]);
			subblock.splice(subblock.length - 1, 1);
			
			// и вращаем исходное слово вправо
			subblock[0].RightCyclicShift(13);
			var O = E(subblock[0], i);
			subblock[2] -= O[1];
			// последние 8 раундов в прямом порядке
			if (i < 8){
				subblock[1] -= O[0];
				subblock[3] ^= O[2];
			}
			else {
				subblock[3] -= O[0];
				subblock[1] ^= O[2];
			}
		}
		
		public function BackwardPass(i:Int) {

			// также проделаем дополнительные операции смешивания
			if (i == 2 || i == 6)
				subblock[0] -= subblock[3];
			else if (i == 3 || i == 7)
				subblock[0] -= subblock[1];
			
			// обращаемся к 4-ем S-блокам
			subblock[1] ^= MARSInfo.S1[subblock[0].GetByte(0)]; 
			subblock[2] -= MARSInfo.S0[subblock[0].GetByte(3)];
			subblock[3] -= MARSInfo.S1[subblock[0].GetByte(2)];
			subblock[3] ^= MARSInfo.S0[subblock[0].GetByte(1)];
			
			subblock[0].LeftCyclicShift(24);
			var a = new Integer(MARSInfo.S1[subblock[0].GetByte(0)]);
			subblock.push(subblock[0]);
			subblock.splice(0, 1);		
		}
		
		public function DForwardPass(i : Int) {
			subblock.insert(0, subblock[subblock.length - 1]);
			subblock.splice(subblock.length - 1, 1);
			
			// и вращаем исходное слово вправо]
			subblock[0].RightCyclicShift(24);
			 // обращаемся к 4-ем элементам S-блоков
			subblock[3] ^= MARSInfo.S0[subblock[0].GetByte(1)];
			subblock[3] += MARSInfo.S1[subblock[0].GetByte(2)];
			subblock[2] += MARSInfo.S0[subblock[0].GetByte(3)];
			subblock[1] ^= MARSInfo.S1[subblock[0].GetByte(0)];
			// дополнительное смешивание
			if (i == 2 || i == 6)
				subblock[0] += subblock[3];
			else if (i == 3 || i == 7)
				subblock[0] += subblock[1];
		}
		
		public function AddKey() {

			for (i in 0...4)
				subblock[i] += K.getElement(i);
		}
		
		public function DAddKey() {

			for (i in 0...4)
				subblock[i] += K.getElement(36 + i);
		}
		
		public function SubKey() {

			for (i in 0...4)
				subblock[i] -= K.getElement(36 + i);
		}
		
		public function DSubKey() {

			for (i in 0...4)
				subblock[i] -= K.getElement(i);
		}
		
		public function ToInt32() : Array<UInt32> {

			var arr = new Array<UInt32>();
			for (i in 0...4){
				arr.push(subblock[i].GetValue());
			}
			return arr;
		}
		
	}

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

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

class Block {

public var subblock = new Array<Integer>();

var K : Key;

public function new(A : UInt32, B : UInt32, C : UInt32, D : UInt32, K : Key) {

subblock.push(new Integer(A));

subblock.push(new Integer(B));

subblock.push(new Integer(C));

subblock.push(new Integer(D));

this.K = K;

}

public function ForwardPass(i : Int) {

// обращаемся к 4-ем S-блокам

subblock[1] ^= MARSInfo.S0[subblock[0].GetByte(0)];

subblock[1] += MARSInfo.S1[subblock[0].GetByte(1)];

subblock[2] += MARSInfo.S0[subblock[0].GetByte(2)];

subblock[3] ^= MARSInfo.S1[subblock[0].GetByte(3)];

subblock[0].RightCyclicShift(24);

// также проделаем дополнительные операции смешивания

if (i == 0 || i == 4)

subblock[0] += subblock[3];

if (i == 1 || i == 5)

subblock[0] += subblock[1];

subblock.push(subblock[0]);

subblock.splice(0, 1);

}

public function DBackwardPass(i : Int) {

// вращаем массив D[]

subblock.insert(0, subblock[subblock.length - 1]);

subblock.splice(subblock.length - 1, 1);

// дополнительное смешивание

if (i == 0 || i == 4)

subblock[0] -= subblock[3];

else if (i == 1 || i == 5)

subblock[0] -= subblock[1];

// и вращаем исходное слово влево

subblock[0].LeftCyclicShift(24);

// обращаемся к 4-ем элементам S-блоков

subblock[3] ^= MARSInfo.S1[subblock[0].GetByte(3)];

subblock[2] -= MARSInfo.S0[subblock[0].GetByte(2)];

subblock[1] -= MARSInfo.S1[subblock[0].GetByte(1)];

subblock[1] ^= MARSInfo.S0[subblock[0].GetByte(0)];

}

private function E(subblock : Integer, i : Int) : Array < UInt32 > {

var M = subblock;

M += K.getElement(2 * i + 4);

var R = subblock;

R.LeftCyclicShift(13);

R *= K.getElement(2 * i + 5);

var i = M.GetBites(9);

var L : Integer;

if (i < 256)

L = new Integer(MARSInfo.S0[i]);

else

L = new Integer(MARSInfo.S1[i % 256]);

M.LeftCyclicShift(R.GetBites(5));

L ^= R;

R.LeftCyclicShift(5);

L ^= R;

L.LeftCyclicShift(R.GetBites(5));

return [L.GetValue(), M.GetValue(), R.GetValue()];

}

public function Crypto(i: Int) {

var O = E (subblock[0], i);

subblock[0].LeftCyclicShift(13);

subblock[2] += O[1];

if (i < 8){

subblock[1] += O[0];

subblock[3] ^= O[2];

}

else{

subblock[3] += O[0];

subblock[1] ^= O[2];

}

subblock.push(subblock[0]);

subblock.splice(0, 1);

}

public function DCrypto(i : Int) {

// вращаем массив subblock[]

subblock.insert(0, subblock[subblock.length - 1]);

subblock.splice(subblock.length - 1, 1);

// и вращаем исходное слово вправо

subblock[0].RightCyclicShift(13);

var O = E(subblock[0], i);

subblock[2] -= O[1];

// последние 8 раундов в прямом порядке

if (i < 8){

subblock[1] -= O[0];

subblock[3] ^= O[2];

}

else {

subblock[3] -= O[0];

subblock[1] ^= O[2];

}

public function BackwardPass(i:Int) {

// также проделаем дополнительные операции смешивания

if (i == 2 || i == 6)

subblock[0] -= subblock[3];

else if (i == 3 || i == 7)

subblock[0] -= subblock[1];

// обращаемся к 4-ем S-блокам

subblock[1] ^= MARSInfo.S1[subblock[0].GetByte(0)];

subblock[2] -= MARSInfo.S0[subblock[0].GetByte(3)];

subblock[3] -= MARSInfo.S1[subblock[0].GetByte(2)];

subblock[3] ^= MARSInfo.S0[subblock[0].GetByte(1)];

subblock[0].LeftCyclicShift(24);

var a = new Integer(MARSInfo.S1[subblock[0].GetByte(0)]);

subblock.push(subblock[0]);

subblock.splice(0, 1);

}

public function DForwardPass(i : Int) {

subblock.insert(0, subblock[subblock.length - 1]);

subblock.splice(subblock.length - 1, 1);

// и вращаем исходное слово вправо]

subblock[0].RightCyclicShift(24);

// обращаемся к 4-ем элементам S-блоков

subblock[3] ^= MARSInfo.S0[subblock[0].GetByte(1)];

subblock[3] += MARSInfo.S1[subblock[0].GetByte(2)];

subblock[2] += MARSInfo.S0[subblock[0].GetByte(3)];

subblock[1] ^= MARSInfo.S1[subblock[0].GetByte(0)];

// дополнительное смешивание

if (i == 2 || i == 6)

subblock[0] += subblock[3];

else if (i == 3 || i == 7)

subblock[0] += subblock[1];

}

public function AddKey() {

for (i in 0...4)

subblock[i] += K.getElement(i);

}

public function DAddKey() {

for (i in 0...4)

subblock[i] += K.getElement(36 + i);

}

public function SubKey() {

for (i in 0...4)

subblock[i] -= K.getElement(36 + i);

}

public function DSubKey() {

for (i in 0...4)

subblock[i] -= K.getElement(i);

}

public function ToInt32() : Array<UInt32> {

var arr = new Array<UInt32>();

for (i in 0...4){

arr.push(subblock[i].GetValue());

}

return arr;

}

Свойства [latex]S[/latex]-блоков:

Стоит отметить, что [latex]S[/latex]-блок — это конкатенация блоков [latex]S0[/latex] и [latex]S1[/latex].

[latex]S[/latex]-блок не должен содержать слова, состоящие все [latex]0[/latex] или [latex]1[/latex]
Каждые два [latex]S[/latex]-блока [latex]S0[/latex], [latex]S1[/latex] должны отличаться друг от друга как минимум в [latex]3[/latex] из [latex]4[/latex] байтах.(так как выполнение этого условия для псевдослучайных [latex]S[/latex]-блоков крайне маловероятно, то один из двух [latex]S[/latex]-блоков модифицируется)
S-блок не содержит двух элементов [latex]S[i],S[j](i\neq j)[/latex] таких, что [latex] S\left[i\right]=S\left[j\right][/latex]; [latex]S\left[i\right]=-S\left[j\right][/latex] или [latex] S\left[i\right]=-S\left[j\right][/latex]
В [latex]S[/latex]-блоке не существует двух пар элементов [latex]XOR[/latex]-отличия которых равны и двух пар элементов упорядоченная разность которых равна
Каждые два элемента [latex]S[/latex]-блока должны отличаться хотя бы [latex]4[/latex] битами

В данном программе будем использовать блок, предложенный в реализации IBM для AES.

Расширение ключа:

Процедура расширения ключа расширяет заданный массив ключей [latex]T[][/latex], состоящий из [latex]n[/latex] [latex]32[/latex]-битных слов (где [latex]n[/latex] целое число от [latex]4[/latex] до [latex]14[/latex]) в массив [latex]K[][/latex] из [latex]40[/latex] элементов. Исходный ключ не должен придерживаться какой-либо структуры. В дополнение, процедура расширения ключа гарантирует следующие свойства ключевого слова, используемого при перемножении в криптографическом ядре алгоритма:

два младших бита ключевого слова будут всегда единицами
ни одно из ключевых слов не будет содержать десять подряд идущих [latex]0[/latex] или [latex]1[/latex]

Опишем алгоритм расширения ключа.

Сначала массив [latex]T[][/latex] дополняется до 15 элементов следующим образом: [latex]T[n]=n[/latex];[latex]T[n+1\ldots 14]=0[/latex]

		if (T.length < 4 || T.length > 14)
			throw "Длина ключа от 128 до 448 бит";
		T.push(new Integer(T.length));
		for (i in T.length...15){

			T.push(new Integer(0));
		}

if (T.length < 4 || T.length > 14)

throw "Длина ключа от 128 до 448 бит";

T.push(new Integer(T.length));

for (i in T.length...15){

T.push(new Integer(0));

}

Далее данный процесс повторяется [latex]4[/latex] раза:

- На каждой итерации генерируются [latex]10[/latex] слов расширенного ключа. [latex]j[/latex] переменная отображающая текущий номер итерации.(для первой итерации [latex]0[/latex], для второй [latex]1[/latex] и т. д.)
  Массив [latex]T[][/latex] преобразуется по следующему правилу: [latex]i=0\ldots 14,T[i]=T[i]\oplus ((T[i-7\mod 15]\oplus T[i-2\mod 15])\lll 3)\oplus (4i+j)[/latex]

		for (i in 0...15) {

			var temp = T[(i + 8) % 15] ^ T[(i + 13) % 15];
			temp.LeftCyclicShift(3);
			temp ^= 4 * i + j;	
			T[i] ^= temp;
		}

for (i in 0...15) {

var temp = T[(i + 8) % 15] ^ T[(i + 13) % 15];

temp.LeftCyclicShift(3);

temp ^= 4 * i + j;

T[i] ^= temp;

}

- Далее мы перемешиваем массив [latex]T[][/latex] при помощи [latex]4[/latex] раундов Сети Фейстеля 1-го типа. Повторяем четыре раза следующую операцию: [latex]T[i]=(T[i]+S[low~9~bits~of~T[i-1\mod 15]])\lll 9;i=0,1\ldots 14[/latex]

			for (k in 0...4) {
				for (i in 0...15) {

					var temp = T[(i + 14) % 15].GetBites(9);
					if (temp < 256)
						temp = MARSInfo.S0[temp];	
					else
						temp = MARSInfo.S1[temp % 256];
					var temp1 = T[i] + new Integer(temp);
					temp1.LeftCyclicShift(9);
					T[i] = temp1;
				}	
			 }

for (k in 0...4) {

for (i in 0...15) {

var temp = T[(i + 14) % 15].GetBites(9);

if (temp < 256)

temp = MARSInfo.S0[temp];

else

temp = MARSInfo.S1[temp % 256];

var temp1 = T[i] + new Integer(temp);

temp1.LeftCyclicShift(9);

T[i] = temp1;

}

Далее берем десять слов из массива [latex]T[][/latex] и вставляем их в качестве следующих десяти слов в массив [latex]K[][/latex] ещё раз перемешав: [latex]K[10j+i]=T[4i\mod 15];i=0,1\ldots 9[/latex]

			for (i in 0...10) {

				K[10 * j + i] = T[(4 * i) % 15];
			}

for (i in 0...10) {

K[10 * j + i] = T[(4 * i) % 15];

}

Окончательно, мы пробегаемся по шестнадцати словам, используемыми для перемножения[latex](K[5],K[7]…K[35])[/latex] и модифицируем их для того, чтобы они соответствовали двум свойствам, описанным выше.
Записываем два младших бита [latex]K[i][/latex], по формуле [latex] j=K[i]\land 3[/latex] , а затем записываем вместо этих двух бит единицы, [latex] w=K[i]\lor 3[/latex] .
Собираем маску [latex]M[/latex] для битов [latex]w[/latex], которые принадлежат последовательностям из десяти и более нулей или единиц. К примеру, [latex] M_{l}=1[/latex] , тогда и только тогда, когда [latex]w_{l}[/latex] принадлежит последовательности из [latex]10[/latex] или более одинаковых элементов. Тогда мы сбрасываем (выставляем их в [latex]0[/latex]) значения тех единиц [latex]M[/latex], которые находятся на границах нулевых или единичных последовательностей, а также тех единиц, которые находятся в старшем и младшем битах. К примеру, пусть наше слово выглядит так: [latex] w=0^{3}1^{13}0^{12}1011[/latex] (выражение [latex]0^{i}[/latex] или же [latex] 1^{i}[/latex] обозначает, что [latex]0[/latex] или [latex]1[/latex] будут повторены в слове [latex]i[/latex] раз). Тогда маска [latex]M[/latex] будет выглядеть следующим образом: [latex] 0^{3}1^{25}0^{4}[/latex] . А значит мы сбрасываем биты в [latex]4, 15, 16, 28[/latex] позициях, то есть [latex]M=0^{4}1^{11}001^{10}0^{5}[/latex]
Далее, для исправления, мы используем таблицу из четырёх слов [latex]B[][/latex]. Все элементы таблицы [latex]B[/latex] подобраны так, что для них и для всех их цикличных сдвигов выполняется свойство, что в них нет семи подряд идущих [latex]0[/latex] или [latex]1[/latex]. В реализации IBM использовалась таблица [latex]B[]=\left\{0xa4a8d57b,0x5b5d193b,0xc8a8309b,0x73f9a978\right\}[/latex] . Далее используются два записанных бита [latex]j[/latex] для выбора слова из таблицы [latex]B[/latex], и используются младшие пять бит слова [latex]K[i-1][/latex] для вращения его элементов, [latex]p=B[j]\lll (lowest~5~bits~of~K[i-1])[/latex].
Окончательно, делается [latex]XOR[/latex] шаблона [latex]p[/latex] на исходное слово, при учете маски [latex]М[/latex]: [latex]K[i] = w\oplus (p\land M)[/latex] .

		while (i <= 35) {

			var jj = K[i].GetValue() & 3;
			var w = K[i].GetValue() | 3;
			var M = MakeMask(w);	
			var p = new Integer(MARSInfo.B[jj]);
			p.LeftCyclicShift(K[i - 1].GetBites(5));
			K[i] = new Integer (w ^ (p.GetValue() & M));
			i += 2;
		}

while (i <= 35) {

var jj = K[i].GetValue() & 3;

var w = K[i].GetValue() | 3;

var M = MakeMask(w);

var p = new Integer(MARSInfo.B[jj]);

p.LeftCyclicShift(K[i - 1].GetBites(5));

K[i] = new Integer (w ^ (p.GetValue() & M));

i += 2;

}

Сначала выделяем маской последовательность из [latex]10[/latex] нулей или единиц, и потом выставляем в маске [latex]1[/latex]-цы пока последовательность не прерывается.

	function MakeMask (w : UInt32) : UInt32 {

		var M : UInt32 = 0;
		var ones = (1 << 10) - 1; // 1 << 3 = 1000, 1000 - 0001 = 0111
		var d = 1;
		while (d < 31 - 10) {

			var zerosOrOnes = (ones << d) & w;
			//если все нули, то переменная = 0, 
			//если все единицы, то не должна измениться
			if (zerosOrOnes == 0 || zerosOrOnes == (ones << d)) {

				//не устанавливаем начало последовательности в 1
				++d;
				var dd = zerosOrOnes > 0;
				//не вышли за пределы 
				//и число все еще последовательность 0 или 1
				while (d < 32 && ((1 << d) > 0) == dd){

					M |= 1 << d;
					++d;
				}
				//обнуляем конец последовательности
				--d;
				M ^= 1 << d;
			}
			++d;
		}
		return M;
	}

function MakeMask (w : UInt32) : UInt32 {

var M : UInt32 = 0;

var ones = (1 << 10) - 1; // 1 << 3 = 1000, 1000 - 0001 = 0111

var d = 1;

while (d < 31 - 10) {

var zerosOrOnes = (ones << d) & w;

//если все нули, то переменная = 0,

//если все единицы, то не должна измениться

if (zerosOrOnes == 0 || zerosOrOnes == (ones << d)) {

//не устанавливаем начало последовательности в 1

++d;

var dd = zerosOrOnes > 0;

//не вышли за пределы

//и число все еще последовательность 0 или 1

while (d < 32 && ((1 << d) > 0) == dd){

M |= 1 << d;

++d;

}

//обнуляем конец последовательности

--d;

M ^= 1 << d;

}

++d;

}

return M;

}

Реализация класса Key:

class Key {
	
	var K = new Array <Integer> ();
	
	public function new(T : Array < Integer >){ 
		
		if (T.length < 4 || T.length > 14)
			throw "Длина ключа от 128 до 448 бит";
		T.push(new Integer(T.length));
		for (i in T.length...15){
			T.push(new Integer(0));
		}
		
		for (j in 0...4) {
			for (i in 0...15) {

				var temp = T[(i + 8) % 15] ^ T[(i + 13) % 15];
				temp.LeftCyclicShift(3);
				temp ^= 4 * i + j;	
				T[i] ^= temp;
			}
			
			for (k in 0...4) {
				for (i in 0...15) {

					var temp = T[(i + 14) % 15].GetBites(9);
					if (temp < 256)
						temp = MARSInfo.S0[temp];	
					else
						temp = MARSInfo.S1[temp % 256];
					var temp1 = T[i] + new Integer(temp);
					temp1.LeftCyclicShift(9);
					T[i] = temp1;
				}	
			}
			
			for (i in 0...10) {
				K[10 * j + i] = T[(4 * i) % 15];
			}
		}
			
		var i = 5;
		
		while (i <= 35){

			var jj = K[i].GetValue() & 3;
			var w = K[i].GetValue() | 3;
			var M = MakeMask(w);	
			var p = new Integer(MARSInfo.B[jj]);
			p.LeftCyclicShift(K[i - 1].GetBites(5));
			K[i] = new Integer (w ^ (p.GetValue() & M));
			i += 2;
		}
	}
	
	public function getElement(i :Int) {

		i %= K.length;
		return K[i];
	}
	

	function MakeMask (w : UInt32) : UInt32 {

		var M : UInt32 = 0;
		var ones = (1 << 10) - 1; // 1 << 3 = 1000, 1000 - 0001 = 0111
		var d = 1;
		while (d < 31 - 10){
			var zerosOrOnes = (ones << d) & w;
			//если все нули, то переменная = 0, 
			//если все единицы, то не должна измениться
			if (zerosOrOnes == 0 || zerosOrOnes == (ones << d)){
				//не устанавливаем начало последовательности в 1
				++d;
				var dd = zerosOrOnes > 0;
				//не вышли за пределы 
				//и число все еще последовательность 0 или 1
				//dd bool
				while (d < 32 && ((1 << d) > 0) == dd){
					M |= 1 << d;
					++d;
				}
				//обнуляем конец последовательности
				--d;
				M ^= 1 << d;
			}
			++d;
		}
		return M;
	}

class Key {

var K = new Array <Integer> ();

public function new(T : Array < Integer >){

if (T.length < 4 || T.length > 14)

throw "Длина ключа от 128 до 448 бит";

T.push(new Integer(T.length));

for (i in T.length...15){

T.push(new Integer(0));

}

for (j in 0...4) {

for (i in 0...15) {

var temp = T[(i + 8) % 15] ^ T[(i + 13) % 15];

temp.LeftCyclicShift(3);

temp ^= 4 * i + j;

T[i] ^= temp;

}

for (k in 0...4) {

for (i in 0...15) {

var temp = T[(i + 14) % 15].GetBites(9);

if (temp < 256)

temp = MARSInfo.S0[temp];

else

temp = MARSInfo.S1[temp % 256];

var temp1 = T[i] + new Integer(temp);

temp1.LeftCyclicShift(9);

T[i] = temp1;

}

for (i in 0...10) {

K[10 * j + i] = T[(4 * i) % 15];

}

var i = 5;

while (i <= 35){

var jj = K[i].GetValue() & 3;

var w = K[i].GetValue() | 3;

var M = MakeMask(w);

var p = new Integer(MARSInfo.B[jj]);

p.LeftCyclicShift(K[i - 1].GetBites(5));

K[i] = new Integer (w ^ (p.GetValue() & M));

i += 2;

}

public function getElement(i :Int) {

i %= K.length;

return K[i];

}

function MakeMask (w : UInt32) : UInt32 {

var M : UInt32 = 0;

var ones = (1 << 10) - 1; // 1 << 3 = 1000, 1000 - 0001 = 0111

var d = 1;

while (d < 31 - 10){

var zerosOrOnes = (ones << d) & w;

//если все нули, то переменная = 0,

//если все единицы, то не должна измениться

if (zerosOrOnes == 0 || zerosOrOnes == (ones << d)){

//не устанавливаем начало последовательности в 1

++d;

var dd = zerosOrOnes > 0;

//не вышли за пределы

//и число все еще последовательность 0 или 1

//dd bool

while (d < 32 && ((1 << d) > 0) == dd){

M |= 1 << d;

++d;

}

//обнуляем конец последовательности

--d;

M ^= 1 << d;

}

++d;

}

return M;

}

Теперь, мы реализовали все необходимое, чтобы написать алгоритм кодирования и декодирования:

class MARS {

	var key : Key;

	public inline function new (k : Array<Integer>) {

		key = new Key(k);
	}
	public function code (m : Array<UInt32>) : Array<Block> {

		// чтобы длина была кратна 4
		for (i in 0...(3 - ((m.length - 1)% 4))){
			m.push(0);
		}
		var blocks = new Array <Block>();
		var i = 0;
		while (i < m.length) {

			var block = new Block(m[i], m[i + 1], m[i + 2], m[i + 3], key);
			block.AddKey();
			for (j in 0...8)
				block.ForwardPass(j);
			for (j in 0...16)
				block.Crypto(j);
			for (j in 0...8)
				block.BackwardPass(j);
			block.SubKey();
				
			blocks.push(block);
			i += 4;
		}
		return blocks;
	}
	
	public function decode(blocks : Array<Block>) : Array<UInt32> {

		var m = new Array<UInt32>();
		for (i in 0...blocks.length){
			blocks[i].DAddKey();
			
			var j = 7;
			while (j >= 0) {
				blocks[i].DForwardPass(j);
				--j;
			}
			
			j = 15;
			while (j >= 0) {
				blocks[i].DCrypto(j);
				--j;
			}
			
			var j = 7;
			while (j >= 0) {
				blocks[i].DBackwardPass(j);
				--j;
			}
			blocks[i].DSubKey();
			
			m = m.concat(blocks[i].ToInt32());
		}
		return m;		
	}

class MARS {

var key : Key;

public inline function new (k : Array<Integer>) {

key = new Key(k);

}

public function code (m : Array<UInt32>) : Array<Block> {

// чтобы длина была кратна 4

for (i in 0...(3 - ((m.length - 1)% 4))){

m.push(0);

}

var blocks = new Array <Block>();

var i = 0;

while (i < m.length) {

var block = new Block(m[i], m[i + 1], m[i + 2], m[i + 3], key);

block.AddKey();

for (j in 0...8)

block.ForwardPass(j);

for (j in 0...16)

block.Crypto(j);

for (j in 0...8)

block.BackwardPass(j);

block.SubKey();

blocks.push(block);

i += 4;

}

return blocks;

}

public function decode(blocks : Array<Block>) : Array<UInt32> {

var m = new Array<UInt32>();

for (i in 0...blocks.length){

blocks[i].DAddKey();

var j = 7;

while (j >= 0) {

blocks[i].DForwardPass(j);

--j;

}

j = 15;

while (j >= 0) {

blocks[i].DCrypto(j);

--j;

}

var j = 7;

while (j >= 0) {

blocks[i].DBackwardPass(j);

--j;

}

blocks[i].DSubKey();

m = m.concat(blocks[i].ToInt32());

}

return m;

}

Осталась последняя проблема, наш алгоритм кодирует только массивы из целочисленных [latex]32[/latex] битных элементов, а хотелось бы сообщения. Исправить эту ситуацию помогут следующие функции:

	static function stringToUInt32Array(message : String) {
		
		var arr = new Array<UInt32>();
		
		var j = 0;
		for (i in 0...message.length) {
			
			if (j == 0) {
				
				arr.push(0);
			}
			
			arr[arr.length - 1] |= message.charCodeAt(i) << (j * 8);
			
			++j;
			j %= 4;
		}
		
		return arr;
	}
	
	static function stringFromUInt32Array(arr : Array<UInt32>) : String {
		
		var result = "";
		
		for (byte in arr) {
			for (i in 0...4) {
				//из одного субблока получается 4 символа (32 / 8)
				result += String.fromCharCode(byte & 255);
				byte >>>= 8;
			}
		}
		
		return result;
	}

static function stringToUInt32Array(message : String) {

var arr = new Array<UInt32>();

var j = 0;

for (i in 0...message.length) {

if (j == 0) {

arr.push(0);

}

arr[arr.length - 1] |= message.charCodeAt(i) << (j * 8);

++j;

j %= 4;

}

return arr;

}

static function stringFromUInt32Array(arr : Array<UInt32>) : String {

var result = "";

for (byte in arr) {

for (i in 0...4) {

//из одного субблока получается 4 символа (32 / 8)

result += String.fromCharCode(byte & 255);

byte >>>= 8;

}

return result;

}

[latex]S0[/latex], [latex]S1[/latex], [latex]B[/latex] блоки я хранила в классе MarsInfo, где все поля были статическими:

class MARSInfo {
		public static var B : Array<UInt32> = [0xa4a8d57b , 0x5b5d193b , 0xc8a8309b , 0x73f9a978 ];
		public static var S0 : Array<UInt32> = [
		0x09d0c479, 0x28c8ffe0, 0x84aa6c39, 0x9dad7287, 0x7dff9be3, 0xd4268361, 
		0xc96da1d4, 0x7974cc93, 0x85d0582e, 0x2a4b5705, 0x1ca16a62, 0xc3bd279d, 
		0x0f1f25e5, 0x5160372f, 0xc695c1fb, 0x4d7ff1e4, 0xae5f6bf4, 0x0d72ee46, 
		0xff23de8a, 0xb1cf8e83, 0xf14902e2, 0x3e981e42, 0x8bf53eb6, 0x7f4bf8ac, 
		0x83631f83, 0x25970205, 0x76afe784, 0x3a7931d4, 0x4f846450, 0x5c64c3f6, 
		0x210a5f18, 0xc6986a26, 0x28f4e826, 0x3a60a81c, 0xd340a664, 0x7ea820c4, 
		0x526687c5, 0x7eddd12b, 0x32a11d1d, 0x9c9ef086, 0x80f6e831, 0xab6f04ad, 
		0x56fb9b53, 0x8b2e095c, 0xb68556ae, 0xd2250b0d, 0x294a7721, 0xe21fb253, 
		0xae136749, 0xe82aae86, 0x93365104, 0x99404a66, 0x78a784dc, 0xb69ba84b, 
		0x04046793, 0x23db5c1e, 0x46cae1d6, 0x2fe28134, 0x5a223942, 0x1863cd5b, 
		0xc190c6e3, 0x07dfb846, 0x6eb88816, 0x2d0dcc4a, 0xa4ccae59, 0x3798670d, 
		0xcbfa9493, 0x4f481d45, 0xeafc8ca8, 0xdb1129d6, 0xb0449e20, 0x0f5407fb, 
		0x6167d9a8, 0xd1f45763, 0x4daa96c3, 0x3bec5958, 0xababa014, 0xb6ccd201, 
		0x38d6279f, 0x02682215, 0x8f376cd5, 0x092c237e, 0xbfc56593, 0x32889d2c, 
		0x854b3e95, 0x05bb9b43, 0x7dcd5dcd, 0xa02e926c, 0xfae527e5, 0x36a1c330, 
		0x3412e1ae, 0xf257f462, 0x3c4f1d71, 0x30a2e809, 0x68e5f551, 0x9c61ba44, 
		0x5ded0ab8, 0x75ce09c8, 0x9654f93e, 0x698c0cca, 0x243cb3e4, 0x2b062b97, 
		0x0f3b8d9e, 0x00e050df, 0xfc5d6166, 0xe35f9288, 0xc079550d, 0x0591aee8, 
		0x8e531e74, 0x75fe3578, 0x2f6d829a, 0xf60b21ae, 0x95e8eb8d, 0x6699486b, 
		0x901d7d9b, 0xfd6d6e31, 0x1090acef, 0xe0670dd8, 0xdab2e692, 0xcd6d4365, 
		0xe5393514, 0x3af345f0, 0x6241fc4d, 0x460da3a3, 0x7bcf3729, 0x8bf1d1e0, 
		0x14aac070, 0x1587ed55, 0x3afd7d3e, 0xd2f29e01, 0x29a9d1f6, 0xefb10c53, 
		0xcf3b870f, 0xb414935c, 0x664465ed, 0x024acac7, 0x59a744c1, 0x1d2936a7, 
		0xdc580aa6, 0xcf574ca8, 0x040a7a10, 0x6cd81807, 0x8a98be4c, 0xaccea063, 
		0xc33e92b5, 0xd1e0e03d, 0xb322517e, 0x2092bd13, 0x386b2c4a, 0x52e8dd58, 
		0x58656dfb, 0x50820371, 0x41811896, 0xe337ef7e, 0xd39fb119, 0xc97f0df6, 
		0x68fea01b, 0xa150a6e5, 0x55258962, 0xeb6ff41b, 0xd7c9cd7a, 0xa619cd9e, 
		0xbcf09576, 0x2672c073, 0xf003fb3c, 0x4ab7a50b, 0x1484126a, 0x487ba9b1, 
		0xa64fc9c6, 0xf6957d49, 0x38b06a75, 0xdd805fcd, 0x63d094cf, 0xf51c999e, 
		0x1aa4d343, 0xb8495294, 0xce9f8e99, 0xbffcd770, 0xc7c275cc, 0x378453a7, 
		0x7b21be33, 0x397f41bd, 0x4e94d131, 0x92cc1f98, 0x5915ea51, 0x99f861b7, 
		0xc9980a88, 0x1d74fd5f, 0xb0a495f8, 0x614deed0, 0xb5778eea, 0x5941792d, 
		0xfa90c1f8, 0x33f824b4, 0xc4965372, 0x3ff6d550, 0x4ca5fec0, 0x8630e964, 
		0x5b3fbbd6, 0x7da26a48, 0xb203231a, 0x04297514, 0x2d639306, 0x2eb13149, 
		0x16a45272, 0x532459a0, 0x8e5f4872, 0xf966c7d9, 0x07128dc0, 0x0d44db62, 
		0xafc8d52d, 0x06316131, 0xd838e7ce, 0x1bc41d00, 0x3a2e8c0f, 0xea83837e, 
		0xb984737d, 0x13ba4891, 0xc4f8b949, 0xa6d6acb3, 0xa215cdce, 0x8359838b, 
		0x6bd1aa31, 0xf579dd52, 0x21b93f93, 0xf5176781, 0x187dfdde, 0xe94aeb76, 
		0x2b38fd54, 0x431de1da, 0xab394825, 0x9ad3048f, 0xdfea32aa, 0x659473e3, 
		0x623f7863, 0xf3346c59, 0xab3ab685, 0x3346a90b, 0x6b56443e, 0xc6de01f8, 
		0x8d421fc0, 0x9b0ed10c, 0x88f1a1e9, 0x54c1f029, 0x7dead57b, 0x8d7ba426, 
		0x4cf5178a, 0x551a7cca, 0x1a9a5f08, 0xfcd651b9, 0x25605182, 0xe11fc6c3, 
		0xb6fd9676, 0x337b3027, 0xb7c8eb14, 0x9e5fd030
	];
	public static var S1 : Array<UInt32> = [
		0x6b57e354, 0xad913cf7, 0x7e16688d, 0x58872a69, 0x2c2fc7df, 0xe389ccc6, 
		0x30738df1, 0x0824a734, 0xe1797a8b, 0xa4a8d57b, 0x5b5d193b, 0xc8a8309b, 
		0x73f9a978, 0x73398d32, 0x0f59573e, 0xe9df2b03, 0xe8a5b6c8, 0x848d0704, 
		0x98df93c2, 0x720a1dc3, 0x684f259a, 0x943ba848, 0xa6370152, 0x863b5ea3, 
		0xd17b978b, 0x6d9b58ef, 0x0a700dd4, 0xa73d36bf, 0x8e6a0829, 0x8695bc14, 
		0xe35b3447, 0x933ac568, 0x8894b022, 0x2f511c27, 0xddfbcc3c, 0x006662b6, 
		0x117c83fe, 0x4e12b414, 0xc2bca766, 0x3a2fec10, 0xf4562420, 0x55792e2a, 
		0x46f5d857, 0xceda25ce, 0xc3601d3b, 0x6c00ab46, 0xefac9c28, 0xb3c35047, 
		0x611dfee3, 0x257c3207, 0xfdd58482, 0x3b14d84f, 0x23becb64, 0xa075f3a3, 
		0x088f8ead, 0x07adf158, 0x7796943c, 0xfacabf3d, 0xc09730cd, 0xf7679969, 
		0xda44e9ed, 0x2c854c12, 0x35935fa3, 0x2f057d9f, 0x690624f8, 0x1cb0bafd, 
		0x7b0dbdc6, 0x810f23bb, 0xfa929a1a, 0x6d969a17, 0x6742979b, 0x74ac7d05, 
		0x010e65c4, 0x86a3d963, 0xf907b5a0, 0xd0042bd3, 0x158d7d03, 0x287a8255, 
		0xbba8366f, 0x096edc33, 0x21916a7b, 0x77b56b86, 0x951622f9, 0xa6c5e650, 
		0x8cea17d1, 0xcd8c62bc, 0xa3d63433, 0x358a68fd, 0x0f9b9d3c, 0xd6aa295b, 
		0xfe33384a, 0xc000738e, 0xcd67eb2f, 0xe2eb6dc2, 0x97338b02, 0x06c9f246, 
		0x419cf1ad, 0x2b83c045, 0x3723f18a, 0xcb5b3089, 0x160bead7, 0x5d494656, 
		0x35f8a74b, 0x1e4e6c9e, 0x000399bd, 0x67466880, 0xb4174831, 0xacf423b2, 
		0xca815ab3, 0x5a6395e7, 0x302a67c5, 0x8bdb446b, 0x108f8fa4, 0x10223eda, 
		0x92b8b48b, 0x7f38d0ee, 0xab2701d4, 0x0262d415, 0xaf224a30, 0xb3d88aba, 
		0xf8b2c3af, 0xdaf7ef70, 0xcc97d3b7, 0xe9614b6c, 0x2baebff4, 0x70f687cf, 
		0x386c9156, 0xce092ee5, 0x01e87da6, 0x6ce91e6a, 0xbb7bcc84, 0xc7922c20, 
		0x9d3b71fd, 0x060e41c6, 0xd7590f15, 0x4e03bb47, 0x183c198e, 0x63eeb240, 
		0x2ddbf49a, 0x6d5cba54, 0x923750af, 0xf9e14236, 0x7838162b, 0x59726c72, 
		0x81b66760, 0xbb2926c1, 0x48a0ce0d, 0xa6c0496d, 0xad43507b, 0x718d496a, 
		0x9df057af, 0x44b1bde6, 0x054356dc, 0xde7ced35, 0xd51a138b, 0x62088cc9, 
		0x35830311, 0xc96efca2, 0x686f86ec, 0x8e77cb68, 0x63e1d6b8, 0xc80f9778, 
		0x79c491fd, 0x1b4c67f2, 0x72698d7d, 0x5e368c31, 0xf7d95e2e, 0xa1d3493f, 
		0xdcd9433e, 0x896f1552, 0x4bc4ca7a, 0xa6d1baf4, 0xa5a96dcc, 0x0bef8b46, 
		0xa169fda7, 0x74df40b7, 0x4e208804, 0x9a756607, 0x038e87c8, 0x20211e44, 
		0x8b7ad4bf, 0xc6403f35, 0x1848e36d, 0x80bdb038, 0x1e62891c, 0x643d2107, 
		0xbf04d6f8, 0x21092c8c, 0xf644f389, 0x0778404e, 0x7b78adb8, 0xa2c52d53, 
		0x42157abe, 0xa2253e2e, 0x7bf3f4ae, 0x80f594f9, 0x953194e7, 0x77eb92ed, 
		0xb3816930, 0xda8d9336, 0xbf447469, 0xf26d9483, 0xee6faed5, 0x71371235, 
		0xde425f73, 0xb4e59f43, 0x7dbe2d4e, 0x2d37b185, 0x49dc9a63, 0x98c39d98, 
		0x1301c9a2, 0x389b1bbf, 0x0c18588d, 0xa421c1ba, 0x7aa3865c, 0x71e08558, 
		0x3c5cfcaa, 0x7d239ca4, 0x0297d9dd, 0xd7dc2830, 0x4b37802b, 0x7428ab54, 
		0xaeee0347, 0x4b3fbb85, 0x692f2f08, 0x134e578e, 0x36d9e0bf, 0xae8b5fcf, 
		0xedb93ecf, 0x2b27248e, 0x170eb1ef, 0x7dc57fd6, 0x1e760f16, 0xb1136601, 
		0x864e1b9b, 0xd7ea7319, 0x3ab871bd, 0xcfa4d76f, 0xe31bd782, 0x0dbeb469, 
		0xabb96061, 0x5370f85d, 0xffb07e37, 0xda30d0fb, 0xebc977b6, 0x0b98b40f, 
		0x3a4d0fe6, 0xdf4fc26b, 0x159cf22a, 0xc298d6e2, 0x2b78ef6a, 0x61a94ac0, 
		0xab561187, 0x14eea0f0, 0xdf0d4164, 0x19af70ee ];		
	}

class MARSInfo {

public static var B : Array<UInt32> = [0xa4a8d57b , 0x5b5d193b , 0xc8a8309b , 0x73f9a978 ];

public static var S0 : Array<UInt32> = [

0x09d0c479, 0x28c8ffe0, 0x84aa6c39, 0x9dad7287, 0x7dff9be3, 0xd4268361,

0xc96da1d4, 0x7974cc93, 0x85d0582e, 0x2a4b5705, 0x1ca16a62, 0xc3bd279d,

0x0f1f25e5, 0x5160372f, 0xc695c1fb, 0x4d7ff1e4, 0xae5f6bf4, 0x0d72ee46,

0xff23de8a, 0xb1cf8e83, 0xf14902e2, 0x3e981e42, 0x8bf53eb6, 0x7f4bf8ac,

0x83631f83, 0x25970205, 0x76afe784, 0x3a7931d4, 0x4f846450, 0x5c64c3f6,

0x210a5f18, 0xc6986a26, 0x28f4e826, 0x3a60a81c, 0xd340a664, 0x7ea820c4,

0x526687c5, 0x7eddd12b, 0x32a11d1d, 0x9c9ef086, 0x80f6e831, 0xab6f04ad,

0x56fb9b53, 0x8b2e095c, 0xb68556ae, 0xd2250b0d, 0x294a7721, 0xe21fb253,

0xae136749, 0xe82aae86, 0x93365104, 0x99404a66, 0x78a784dc, 0xb69ba84b,

0x04046793, 0x23db5c1e, 0x46cae1d6, 0x2fe28134, 0x5a223942, 0x1863cd5b,

0xc190c6e3, 0x07dfb846, 0x6eb88816, 0x2d0dcc4a, 0xa4ccae59, 0x3798670d,

0xcbfa9493, 0x4f481d45, 0xeafc8ca8, 0xdb1129d6, 0xb0449e20, 0x0f5407fb,

0x6167d9a8, 0xd1f45763, 0x4daa96c3, 0x3bec5958, 0xababa014, 0xb6ccd201,

0x38d6279f, 0x02682215, 0x8f376cd5, 0x092c237e, 0xbfc56593, 0x32889d2c,

0x854b3e95, 0x05bb9b43, 0x7dcd5dcd, 0xa02e926c, 0xfae527e5, 0x36a1c330,

0x3412e1ae, 0xf257f462, 0x3c4f1d71, 0x30a2e809, 0x68e5f551, 0x9c61ba44,

0x5ded0ab8, 0x75ce09c8, 0x9654f93e, 0x698c0cca, 0x243cb3e4, 0x2b062b97,

0x0f3b8d9e, 0x00e050df, 0xfc5d6166, 0xe35f9288, 0xc079550d, 0x0591aee8,

0x8e531e74, 0x75fe3578, 0x2f6d829a, 0xf60b21ae, 0x95e8eb8d, 0x6699486b,

0x901d7d9b, 0xfd6d6e31, 0x1090acef, 0xe0670dd8, 0xdab2e692, 0xcd6d4365,

0xe5393514, 0x3af345f0, 0x6241fc4d, 0x460da3a3, 0x7bcf3729, 0x8bf1d1e0,

0x14aac070, 0x1587ed55, 0x3afd7d3e, 0xd2f29e01, 0x29a9d1f6, 0xefb10c53,

0xcf3b870f, 0xb414935c, 0x664465ed, 0x024acac7, 0x59a744c1, 0x1d2936a7,

0xdc580aa6, 0xcf574ca8, 0x040a7a10, 0x6cd81807, 0x8a98be4c, 0xaccea063,

0xc33e92b5, 0xd1e0e03d, 0xb322517e, 0x2092bd13, 0x386b2c4a, 0x52e8dd58,

0x58656dfb, 0x50820371, 0x41811896, 0xe337ef7e, 0xd39fb119, 0xc97f0df6,

0x68fea01b, 0xa150a6e5, 0x55258962, 0xeb6ff41b, 0xd7c9cd7a, 0xa619cd9e,

0xbcf09576, 0x2672c073, 0xf003fb3c, 0x4ab7a50b, 0x1484126a, 0x487ba9b1,

0xa64fc9c6, 0xf6957d49, 0x38b06a75, 0xdd805fcd, 0x63d094cf, 0xf51c999e,

0x1aa4d343, 0xb8495294, 0xce9f8e99, 0xbffcd770, 0xc7c275cc, 0x378453a7,

0x7b21be33, 0x397f41bd, 0x4e94d131, 0x92cc1f98, 0x5915ea51, 0x99f861b7,

0xc9980a88, 0x1d74fd5f, 0xb0a495f8, 0x614deed0, 0xb5778eea, 0x5941792d,

0xfa90c1f8, 0x33f824b4, 0xc4965372, 0x3ff6d550, 0x4ca5fec0, 0x8630e964,

0x5b3fbbd6, 0x7da26a48, 0xb203231a, 0x04297514, 0x2d639306, 0x2eb13149,

0x16a45272, 0x532459a0, 0x8e5f4872, 0xf966c7d9, 0x07128dc0, 0x0d44db62,

0xafc8d52d, 0x06316131, 0xd838e7ce, 0x1bc41d00, 0x3a2e8c0f, 0xea83837e,

0xb984737d, 0x13ba4891, 0xc4f8b949, 0xa6d6acb3, 0xa215cdce, 0x8359838b,

0x6bd1aa31, 0xf579dd52, 0x21b93f93, 0xf5176781, 0x187dfdde, 0xe94aeb76,

0x2b38fd54, 0x431de1da, 0xab394825, 0x9ad3048f, 0xdfea32aa, 0x659473e3,

0x623f7863, 0xf3346c59, 0xab3ab685, 0x3346a90b, 0x6b56443e, 0xc6de01f8,

0x8d421fc0, 0x9b0ed10c, 0x88f1a1e9, 0x54c1f029, 0x7dead57b, 0x8d7ba426,

0x4cf5178a, 0x551a7cca, 0x1a9a5f08, 0xfcd651b9, 0x25605182, 0xe11fc6c3,

0xb6fd9676, 0x337b3027, 0xb7c8eb14, 0x9e5fd030

];

public static var S1 : Array<UInt32> = [

0x6b57e354, 0xad913cf7, 0x7e16688d, 0x58872a69, 0x2c2fc7df, 0xe389ccc6,

0x30738df1, 0x0824a734, 0xe1797a8b, 0xa4a8d57b, 0x5b5d193b, 0xc8a8309b,

0x73f9a978, 0x73398d32, 0x0f59573e, 0xe9df2b03, 0xe8a5b6c8, 0x848d0704,

0x98df93c2, 0x720a1dc3, 0x684f259a, 0x943ba848, 0xa6370152, 0x863b5ea3,

0xd17b978b, 0x6d9b58ef, 0x0a700dd4, 0xa73d36bf, 0x8e6a0829, 0x8695bc14,

0xe35b3447, 0x933ac568, 0x8894b022, 0x2f511c27, 0xddfbcc3c, 0x006662b6,

0x117c83fe, 0x4e12b414, 0xc2bca766, 0x3a2fec10, 0xf4562420, 0x55792e2a,

0x46f5d857, 0xceda25ce, 0xc3601d3b, 0x6c00ab46, 0xefac9c28, 0xb3c35047,

0x611dfee3, 0x257c3207, 0xfdd58482, 0x3b14d84f, 0x23becb64, 0xa075f3a3,

0x088f8ead, 0x07adf158, 0x7796943c, 0xfacabf3d, 0xc09730cd, 0xf7679969,

0xda44e9ed, 0x2c854c12, 0x35935fa3, 0x2f057d9f, 0x690624f8, 0x1cb0bafd,

0x7b0dbdc6, 0x810f23bb, 0xfa929a1a, 0x6d969a17, 0x6742979b, 0x74ac7d05,

0x010e65c4, 0x86a3d963, 0xf907b5a0, 0xd0042bd3, 0x158d7d03, 0x287a8255,

0xbba8366f, 0x096edc33, 0x21916a7b, 0x77b56b86, 0x951622f9, 0xa6c5e650,

0x8cea17d1, 0xcd8c62bc, 0xa3d63433, 0x358a68fd, 0x0f9b9d3c, 0xd6aa295b,

0xfe33384a, 0xc000738e, 0xcd67eb2f, 0xe2eb6dc2, 0x97338b02, 0x06c9f246,

0x419cf1ad, 0x2b83c045, 0x3723f18a, 0xcb5b3089, 0x160bead7, 0x5d494656,

0x35f8a74b, 0x1e4e6c9e, 0x000399bd, 0x67466880, 0xb4174831, 0xacf423b2,

0xca815ab3, 0x5a6395e7, 0x302a67c5, 0x8bdb446b, 0x108f8fa4, 0x10223eda,

0x92b8b48b, 0x7f38d0ee, 0xab2701d4, 0x0262d415, 0xaf224a30, 0xb3d88aba,

0xf8b2c3af, 0xdaf7ef70, 0xcc97d3b7, 0xe9614b6c, 0x2baebff4, 0x70f687cf,

0x386c9156, 0xce092ee5, 0x01e87da6, 0x6ce91e6a, 0xbb7bcc84, 0xc7922c20,

0x9d3b71fd, 0x060e41c6, 0xd7590f15, 0x4e03bb47, 0x183c198e, 0x63eeb240,

0x2ddbf49a, 0x6d5cba54, 0x923750af, 0xf9e14236, 0x7838162b, 0x59726c72,

0x81b66760, 0xbb2926c1, 0x48a0ce0d, 0xa6c0496d, 0xad43507b, 0x718d496a,

0x9df057af, 0x44b1bde6, 0x054356dc, 0xde7ced35, 0xd51a138b, 0x62088cc9,

0x35830311, 0xc96efca2, 0x686f86ec, 0x8e77cb68, 0x63e1d6b8, 0xc80f9778,

0x79c491fd, 0x1b4c67f2, 0x72698d7d, 0x5e368c31, 0xf7d95e2e, 0xa1d3493f,

0xdcd9433e, 0x896f1552, 0x4bc4ca7a, 0xa6d1baf4, 0xa5a96dcc, 0x0bef8b46,

0xa169fda7, 0x74df40b7, 0x4e208804, 0x9a756607, 0x038e87c8, 0x20211e44,

0x8b7ad4bf, 0xc6403f35, 0x1848e36d, 0x80bdb038, 0x1e62891c, 0x643d2107,

0xbf04d6f8, 0x21092c8c, 0xf644f389, 0x0778404e, 0x7b78adb8, 0xa2c52d53,

0x42157abe, 0xa2253e2e, 0x7bf3f4ae, 0x80f594f9, 0x953194e7, 0x77eb92ed,

0xb3816930, 0xda8d9336, 0xbf447469, 0xf26d9483, 0xee6faed5, 0x71371235,

0xde425f73, 0xb4e59f43, 0x7dbe2d4e, 0x2d37b185, 0x49dc9a63, 0x98c39d98,

0x1301c9a2, 0x389b1bbf, 0x0c18588d, 0xa421c1ba, 0x7aa3865c, 0x71e08558,

0x3c5cfcaa, 0x7d239ca4, 0x0297d9dd, 0xd7dc2830, 0x4b37802b, 0x7428ab54,

0xaeee0347, 0x4b3fbb85, 0x692f2f08, 0x134e578e, 0x36d9e0bf, 0xae8b5fcf,

0xedb93ecf, 0x2b27248e, 0x170eb1ef, 0x7dc57fd6, 0x1e760f16, 0xb1136601,

0x864e1b9b, 0xd7ea7319, 0x3ab871bd, 0xcfa4d76f, 0xe31bd782, 0x0dbeb469,

0xabb96061, 0x5370f85d, 0xffb07e37, 0xda30d0fb, 0xebc977b6, 0x0b98b40f,

0x3a4d0fe6, 0xdf4fc26b, 0x159cf22a, 0xc298d6e2, 0x2b78ef6a, 0x61a94ac0,

0xab561187, 0x14eea0f0, 0xdf0d4164, 0x19af70ee ];

}

try MARS online

e-olymp 4000. Обход в глубину

24.04.2017 by Маша Лукьянова

Задача взята из e-olimp

Условие:

Имя входного файла: «input.txt»

Имя выходного файла: стандартный поток вывода

Ограничение по времени: 1 second

Ограничение по памяти: 122.17 мегабайт

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

Входные данные:

В первой строке содержится количество вершин графа [latex] n [/latex] и выделенная вершина [latex] s [/latex] [latex](1 ≤ s ≤ n ≤ 100) [/latex]. В следующих [latex] n [/latex] строках записано по [latex] n [/latex] чисел — матрица смежности графа, в которой цифра [latex] «0» [/latex] означает отсутствие ребра между вершинами, а цифра [latex] «1» [/latex] — его наличие. Гарантируется, что на главной диагонали матрицы всегда стоят нули.

Выходные данные:

Выведите искомое количество вершин.

Тесты:

№	Входные данные	Выходные данные
1	5 1 0 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 0	3
2	1 1 0	1
3	3 3 0 1 1 1 0 1 1 1 0	3
4	3 1 0 0 0 0 0 1 1 1 0	1

Решение:

Поскольку нам необходимо найти компоненту связности, запустим из исходной вершины поиск в глубину, запоминая посещенные вершины в массиве [latex] used [/latex]. Те вершины, которые мы посетили — принадлежат той же компоненте связности, что и исходная вершина. Таким образом, подсчитав кол-во посещенных вершин, мы решим задачу.

package;

import cpp.Lib;
import sys.io.*;

class Main 
{
	
	static function main() 
	{
		var inp = File.read("input.txt", false);
		var d = inp.readLine();
		var dd = d.split(' ');
		
		var n = Std.parseInt(dd[0]);
		var s = Std.parseInt(dd[1]);
		s--;
			
		var graph = new Array<Array>();
		var used = new Array  ();
		
		function DFS(v : Int){
			if (used[v])
				return;
				
			used[v] = true;
			for (i in 0...(graph[v].length)){
				DFS (graph[v][i]);
			}
		}
			
		for (i in 0...n){
			graph[i] = new Array();
			used[i] = false;
		}
		
		for (i in 0...n){
			var arr = inp.readLine().split(' ');
			for (j in 0...n){
				if (arr[j] == "1")
					graph[i].push(j);
			}
		}  
		
		DFS(s);
		
		var count = 0;
		
		for (i in 0...n){
			if (used[i])
				count ++; 
		}
		
		Sys.stdout().writeString(count + "");
	}
}

package;

import cpp.Lib;

import sys.io.*;

class Main

{

static function main()

{

var inp = File.read("input.txt", false);

var d = inp.readLine();

var dd = d.split(' ');

var n = Std.parseInt(dd[0]);

var s = Std.parseInt(dd[1]);

s--;

var graph = new Array<Array>();

var used = new Array ();

function DFS(v : Int){

if (used[v])

return;

used[v] = true;

for (i in 0...(graph[v].length)){

DFS (graph[v][i]);

}

for (i in 0...n){

graph[i] = new Array();

used[i] = false;

}

for (i in 0...n){

var arr = inp.readLine().split(' ');

for (j in 0...n){

if (arr[j] == "1")

graph[i].push(j);

}

DFS(s);

var count = 0;

for (i in 0...n){

if (used[i])

count ++;

}

Sys.stdout().writeString(count + "");

}

Алексей Маслеев	Сергей Завада	Анастасия Улановская
Владислав Козачков	Николай Яковлев	Даша Тарабаева
Денис Швецов	Лена Наумова	Артур Тарасов
Евгений Кравчук	Иоанна Васильева	Дарья Пиндус
Артём Мисесин	Даша Кивганова	Кирилл Автомонов
Алёна Ищук	Александр Зайченко	Маша Лукьянова
Игорь Варламов	Геннадий Муржи

haxe

Учебные материалы по программированию

Author Archives: Маша Лукьянова

e-olymp 4853. Кратчайший путь

Условие:

Входные данные:

Выходные данные:

Тесты:

Решение:

Алгоритм шифрования MARS

Cтруктура алгоритма:

Для работы алгоритма потребуется объявить некоторые элементы ([latex]S[/latex] и [latex]B[/latex] блоки) — они описаны в конце статьи.

Прямое перемешивание:

Криптографическое преобразование:

[latex]E[/latex]-функция

Обратное перемешивание:

Финальная реализиция класса Block:

Свойства [latex]S[/latex]-блоков:

Расширение ключа:

try MARS online

e-olymp 4000. Обход в глубину

Условие:

Входные данные:

Выходные данные:

Тесты:

Решение: