Ю. Е. Бояринова, П. В. Трубников



Скачать 75.01 Kb.
Дата08.11.2012
Размер75.01 Kb.
ТипЗадача

УДК 515.171; 681.3.053



Ю. Е. Бояринова, П. В. Трубников

Институт проблем регистрации информации НАН Украины

ул. Н. Шпака, 2, 03113 Киев, Украина

Расширение задачи разделения секрета

для случая использования двойных чисел



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

Ключевые слова: двойные числа, задача разделения секрета, изоморфизм, сравнение чисел, непозиционная система счисления.
Задача разделения секрета существует давно. Одним из первых примитивных решений этой задачи можно назвать способ разделения на части какой-либо известной информации (лист документа, игральной карты). Последующее восстановление полной информации может быть достигнуто сложением частей полного объекта. Отсутствие любой части не дает полного сохранения секрета. Также известна задача разделения секрета, представленного в области действительных чисел, которая состоит в том, чтобы некий секрет разделить так, чтобы можно было полностью восстановить исходное число. Просто разделение секрета на слагаемые не может дать хороших результатов. Поэтому одним из вариантов является представление секрета в виде совокупности остатков по модулям. Восстановление секрета по имеющимся остаточным представлениям осуществляется однозначно решением системы линейных сравнений, что известно как «китайская теорема» [1].

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

Рассмотрим множество чисел вида , где — действительные числа, — новый элемент. Введем на этом множестве две операции:

  1. сложение


;


  1. умножение


,

© Ю. Е. Бояринова, П. В. Трубников

где — некоторые вещественные числа.

Это множество чисел с определенными выше операциями является двумерной алгеброй над полем действительных чисел. Каждой паре вещественных чисел соответствует определенная алгебра .
Имеется только три различные алгебры второй степени над полем действительных чисел:

  1. комплексные числа ;

  2. дуальные числа ;

  3. двойные числа .

Ранее нами была представлена постановка задачи разделения секрета в комплексных числах [2]. Для комплексных чисел справедлива теория сравнения, можно построить систему остатков. Постановка задачи в таком виде усиливает сложность задачи, но и вычисления становятся более трудными. Однако, благодаря фундаментальной теореме Гаусса об изоморфизме, можно перейти из системы комплексных остатков к вещественным остаткам.

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

Рассмотрим свойства двойных чисел [3]. Обозначим алгебру двойных чисел , элемент этой алгебры назовем двойной единицей.

В алгебре двойных чисел вводим операцию сопряжения, сопоставляя каждому элементу сопряженный элемент , для которого выполняются следующие основные свойства:





Абсолютную величину квадратичной формы назовем нормой двойного числа и обозначим как
.
Очевидно, что и . Доказано, что .

Если и , то существует обратный элемент
,
причем .

Элементы , для которых , не имеют обратных элементов и являются делителями нуля. Таким образом, есть делитель нуля тогда и только тогда, когда , т.е. все делители нуля имеют вид или .

Двойное число назовем целым, если — целые вещественные числа.

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

Отношение делимости в кольце обладает такими свойствами:

1) для любого ;

2) для любого ;

  1. из следует ;

  2. из следует ;

  3. из , и не является делителем нуля, следует ;

  4. из следует для любых целых двойных чисел .

В кольце двойных чисел имеет место аналог алгоритма Евклида, поэтому справедливо, что для любых целых двойных чисел и и не является делителем нуля) существуют целые числа и такие, что , причем

Целые двойные числа, отличающиеся друг от друга множителем, равным делителю единицы, называются ассоциированными. Так, числами, ассоциироваными с числом , являются числа , , . Делители единицы и все числа, ассоциированные с целым двойным числом , называются тривиальными делителями.

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

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

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

Два целых двойных числа назовем сравнимыми по модулю целого двойного числа , если , т.е. существует целое двойное число такое, что .

Сравнение целых двойных чисел имеет следующие основные свойства:

  1. если, то ;

  2. ;

  3. если , , то ;

  4. если , , то ;

  5. если , , то ;

  6. если , , то ;

  7. если , то ;

  8. если и , то .

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

Пусть — произвольное целое двойное число, — модуль, причем и не является делителем нуля, т.е.. Тогда
.
Зададим некоторую полную систему вычетов по вещественному модулю .

Тогда имеем однозначное разложение

,
где ; .

В результате получаем

или
,
где , если , , если , и это разложение определено однозначно.

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

Если двойное число принадлежит полной системе вычетов по модулю двойного числа , то имеем тождество
,
так как в этом случае .

Полную систему вычетов по модулю двойного числа, определяемую формулой

,
будем называть полной системой наименьших вычетов по модулю двойного числа .

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

Для двойных чисел справедливо развитие теоремы Гаусса об изоморфизме.

Теорема.

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

При этом изоморфное соответствие между полной системой вычетов по модулю и полной системой вычетов по модулю задается формулой
,
где . Число назовем коэффициентом изоморфизма.

Назовем двойное число представимым в системе , если является наименьшим вычетом по модулю М, в противном случае не представимо в данной системе.

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

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

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

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


1. Берник В., Матвеев С., Харин Ю. Математические и компьютерные основы криптологии. — М.: Новое знание, 2003.

2. Синьков М.В., Бояринова Ю.Е., Калиновский Я.А., Трубников П.В. Развитие задачи разделения секрета // Реєстрація, зберігання і оброб. даних. — 2003. — Т 5, № 4. — С. 90–97.

3. Синьков М.В., Губарени Н.М. Непозиционное представление в многомерных числовых системах. — К.: Наук. думка, 1979.

Поступила в редакцию 12.03.2004

ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2004, Т. 6, № 1 47

Похожие:

Ю. Е. Бояринова, П. В. Трубников iconМ. В. Синьков, Ю. Е. Бояринова, Я. А. Калиновский, П. В. Трубников
Одним из методов защиты информации является метод, близкий к криптографии с открытым ключом, который сводится к задаче сохранения...
Ю. Е. Бояринова, П. В. Трубников iconПротоиерей Александр Трубников
В оригинале сноски находятся в конце соответствующей страницы, здесь сразу же за текстом!
Ю. Е. Бояринова, П. В. Трубников iconМ. В. Синьков, Я. А. Калиновский, Т. В. Синькова, Ю. Е. Бояринова
Рассмотрены новые применения квадриплексных чисел в таких важных областях как криптография с открытым ключом и цифровая фильтрация...
Ю. Е. Бояринова, П. В. Трубников iconМ. В. Синьков, Я. А. Калиновский, Ю. Е. Бояринова, Т. В. Синькова
Целью работы является повышение эффективности моделирования различных процессов, описываемых такими дифференциальными уравнениями...
Ю. Е. Бояринова, П. В. Трубников iconМ. В. Синьков, Ю. Е. Бояринова, Я. А. Калиновский, Т. В. Синькова
Рассмотрены алгоритмы проведения арифметических и алгебраических операций, построение таких нелинейностей как экспонента, тригонометрические...
Ю. Е. Бояринова, П. В. Трубников iconСловарь б/у труб Апельсиновая корка
Апельсиновая корка фруктовая ассоциация трубников (все признаки хронического авитаминоза). Много маленьких раковин, равномерно распределенных...
Ю. Е. Бояринова, П. В. Трубников iconНеприступную крепость дворец Тадж-Бек взяли штурмом две группы спецназа кгб СССР под руководством полковника Бояринова
Начальник Курсов усовершенствования офицерского состава полковник Бояринов (крайний слева) слева) групп
Ю. Е. Бояринова, П. В. Трубников iconАвтор: Коваленко В. А
Орёл, как и любой другой город, он развивался постепенно из века в век. Мне бы хотелось показать роль управленцев в жизни города...
Ю. Е. Бояринова, П. В. Трубников iconРасчетных сочетаний усилий в. Л. Лебедев, С. А. Трубников
Поэтому обычно при расчетах ограничиваются рассмотрением существенно меньшего количества сочетаний, выбираемых по различным критериям....
Ю. Е. Бояринова, П. В. Трубников iconП. А. Калантаев, к-т техн наук В. Д. Набивич, к-т техн наук В. М. Трубников
В докладе представлены структурная схема и модель данных гис «Дежурный генплан инженерных сетей ннц со ран». Предложено развитие...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org