Упрощение системы разрядных уравнений на основе модифицированной функции разрядного переноса
Going near simplification of the system of bit equalizations is examined by introduction of new function which is the changed variant of function of bit transfer.
Gespeichert in:
| Datum: | 2009 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2009
|
| Schriftenreihe: | Збірник наукових праць Інституту проблем моделювання в енергетиці ім.Г.Є.Пухова НАН України |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/26952 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Упрощение системы разрядных уравнений на основе модифицированной функции разрядного переноса / А.В. Жилин // Збірник наукових праць Інституту проблем моделювання в енергетиці ім.Г.Є.Пухова НАН України. — К.: ІПМЕ ім. Г.Є.Пухова НАН України, 2009. — Вип. 51. — С. 47-51. — Бібліогр.: 4 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-26952 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-269522011-09-30T12:14:29Z Упрощение системы разрядных уравнений на основе модифицированной функции разрядного переноса Жилин, А.В. Going near simplification of the system of bit equalizations is examined by introduction of new function which is the changed variant of function of bit transfer. 2009 Article Упрощение системы разрядных уравнений на основе модифицированной функции разрядного переноса / А.В. Жилин // Збірник наукових праць Інституту проблем моделювання в енергетиці ім.Г.Є.Пухова НАН України. — К.: ІПМЕ ім. Г.Є.Пухова НАН України, 2009. — Вип. 51. — С. 47-51. — Бібліогр.: 4 назв. — рос. XXXX-0067 http://dspace.nbuv.gov.ua/handle/123456789/26952 511 ru Збірник наукових праць Інституту проблем моделювання в енергетиці ім.Г.Є.Пухова НАН України Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| description |
Going near simplification of the system of bit equalizations is examined by
introduction of new function which is the changed variant of function of bit transfer. |
| format |
Article |
| author |
Жилин, А.В. |
| spellingShingle |
Жилин, А.В. Упрощение системы разрядных уравнений на основе модифицированной функции разрядного переноса Збірник наукових праць Інституту проблем моделювання в енергетиці ім.Г.Є.Пухова НАН України |
| author_facet |
Жилин, А.В. |
| author_sort |
Жилин, А.В. |
| title |
Упрощение системы разрядных уравнений на основе модифицированной функции разрядного переноса |
| title_short |
Упрощение системы разрядных уравнений на основе модифицированной функции разрядного переноса |
| title_full |
Упрощение системы разрядных уравнений на основе модифицированной функции разрядного переноса |
| title_fullStr |
Упрощение системы разрядных уравнений на основе модифицированной функции разрядного переноса |
| title_full_unstemmed |
Упрощение системы разрядных уравнений на основе модифицированной функции разрядного переноса |
| title_sort |
упрощение системы разрядных уравнений на основе модифицированной функции разрядного переноса |
| publisher |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| publishDate |
2009 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/26952 |
| citation_txt |
Упрощение системы разрядных уравнений на основе модифицированной функции разрядного переноса / А.В. Жилин // Збірник наукових праць Інституту проблем моделювання в енергетиці ім.Г.Є.Пухова НАН України. — К.: ІПМЕ ім. Г.Є.Пухова НАН України, 2009. — Вип. 51. — С. 47-51. — Бібліогр.: 4 назв. — рос. |
| series |
Збірник наукових праць Інституту проблем моделювання в енергетиці ім.Г.Є.Пухова НАН України |
| work_keys_str_mv |
AT žilinav uproŝeniesistemyrazrâdnyhuravnenijnaosnovemodificirovannojfunkciirazrâdnogoperenosa |
| first_indexed |
2025-07-02T22:18:50Z |
| last_indexed |
2025-07-02T22:18:50Z |
| _version_ |
1836575339225022464 |
| fulltext |
47© А.В. Жилин
УДК 511
А.В. Жилин, ИССЗИ НТУУ “КПИ”, Киев
УПРОЩЕНИЕ СИСТЕМЫ РАЗРЯДНЫХ УРАВНЕНИЙ НА ОСНОВЕ
МОДИФИЦИРОВАННОЙ ФУНКЦИИ РАЗРЯДНОГО ПЕРЕНОСА
Going near simplification of the system of bit equalizations is examined by
introduction of new function which is the changed variant of function of bit transfer.
Стойкость асимметрического шифрования основана на вычислительной
сложности задачи факторизации больших чисел [4]. Как пример, можно
привести всемирно известный алгоритм RSA.
Проведенный ранее анализ существующих методов факторизации [1,3]
показывает, что существуют две основные группы методов факторизации
больших целых чисел, которые имеют экспоненциальную и
субэкспоненциальную сложности. Практически все методы основываются на
нахождении НОД с ограничением области перебора возможных значений
делителей. Т.е. они оперируют свойствами простых целых чисел, используя
как обычную, так и модулярную алгебру.
Представленный в работе [1] метод факторизации предполагает работу
со структурой числа, которое представлено в двоичной форме, и
основывается на единственности разложения числа на простые сомножители
и правиле умножения чисел в двоичной системе счисления.
Факторизуемое число представляется в двоичной форме:
0 1 2 3 4 ... nZ z z z z z z= , где 0z - старший разряд числа, nz - младший разряд числа.
Оно является произведением двух простых чисел 1 2 3 4 ... kX x x x x x= и
1 2 3 4 ... kY y y y y y= , где 1 1,x y - старшие разряды, ,k kx y - младшие разряды
чисел X и Y соответственно:
*Z X Y= .
{ }0 1 0 1 ( 1) 2i j jz ,x , y , ,i ...n, j ...k,k n /∈ = = = +
Умножаем число X на Y , которые имеют по 5 разрядов ( 1 2 3 4 5x x x x x
и 1 2 3 4 5y y y y y ) согласно правилам умножения чисел:
1x 2x 3x 4x 5x
1y 2y 3y 4y 5y
5y 1x 5y 2x 5y 3x 5y 4x 5y 5x
4y 1x 4y 2x 4y 3x 4y 4x 4y 5x
3y 1x 3y 2x 3y 3x 3y 4x 3y 5x
2y 1x 2y 2x 2y 3x 2y 4x 2y 5x
1y 1x 1y 2x 1y 3x 1y 4x 1y 5x
0z 1z 2z 3z 4z 5z 6z 7z 8z 9z
48
Основываясь на этих правилах, получаем приведенную ниже систему
уравнений:
1 1 1 2z y x P= +
2 1 2 2 1 3z y x y x P= + +
3 1 3 2 2 3 1 4z y x y x y x P= + + +
4 1 4 2 3 3 2 4 1 5z y x y x y x y x P= + + + +
5 1 5 2 4 3 3 4 2 5 1 6z y x y x y x y x y x P= + + + + + (1)
6 2 5 3 4 4 3 5 2 7z y x y x y x y x P= + + + +
7 3 5 4 4 5 3 8z y x y x y x P= + + +
8 4 5 5 4 9z y x y x P= + +
9 5 5z y x=
где nP - разрядный перенос.
Определим, что система в заданном виде будет иметь старшие и
младшие разрядные уравнения. Старшинство уравнений определяется между
ними в соответствии тому, к какому разряду факторизируемого числа оно
приравнивается.
Необходимо заметить, что последние разряды чисел X и Y всегда равны
1 ( 5y , 5x =1), так как эти числа простые, а простые числа нечетные и в
двоичной системе счисления заканчиваются на единицу (кроме числа 2, но
согласно условия берутся большие простые числа). 0z будет принимать
однозначное значение 0 или 1 (зависит от значения составных чисел).
Система уравнений (1) имеет вид системы с N (где N – разрядность
факторизуемого числа), в общем случае, нелинейных алгебраических
уравнений с N неизвестными, имеющими характер булевых переменных. При
этом сами нелинейности имеют характер произведений неизвестных. Следует
сразу отметить, что получаемая система уравнений является не совсем
обычной. Ее необычность состоит, во-первых, в том, что, в зависимости от
структуры факторизуемого числа, между уравнениями могут существовать
дополнительные связи, обусловленные наличием переносов nP из младших
разрядов в старшие. При этом характер таких связей очень сильно зависит от
структуры факторизуемого числа. Именно по этой причине положение
каждого уравнения в системе должно быть строго зафиксированным и не
может быть изменено. Т.е. решение системы уравнений не является
нвариантным к перестановке строк ее матрицы, и они являются
взаимосвязанными, начиная с последнего. Во вторых количество нелинейных
членов в каждом уравнении системы и степень самой нелинейности так же
существенно зависит от структуры факторизуемого числа.
Решение такой системы уравнений известными способами
49
затруднительно, так как наличие переносов из младших разрядов в старшие
требует того, что бы положение каждого уравнения в системе должно быть
строго зафиксированным и не может быть изменено. Для преодоления
данных трудностей и представления системы уравнений в несвязанном виде
предлагается ввести функцию nat(x), которая возвращает количество единиц
переноса в зависимости от значения, что принимает низшее разрядное
уравнение. Тогда к каждому разрядному уравнению системы, начиная с
младшего 81=−nz , прибавляется функция nat(x), где x будет значение
предыдущего, по старшинству, уравнения. После добавления функции в
старшее разрядное уравнение, младшее разрядное уравнение берется по
модулю 2, так как переносы нивелируются, и значение правой части
уравнения, взятое по модулю 2, будет равно левой части.
{ }0 0,1z =
1 1 1 2( ( )) mod 2z y x nat z= +
2 1 2 2 1 3( ( )) mod 2z y x y x nat z= + +
3 1 3 2 2 3 1 4( ( )) mod 2z y x y x y x nat z= + + +
4 1 4 2 3 3 2 4 1 5( ( )) mod 2z y x y x y x y x nat z= + + + +
5 1 5 2 4 3 3 4 2 5 1 6( ( )) mod 2z y x y x y x y x y x nat z= + + + + + (2)
6 2 5 3 4 4 3 5 2 7( ( )) mod 2z y x y x y x y x nat z= + + + +
7 3 5 4 4 5 3 8( ( )) mod 2z y x y x y x nat z= + + +
8 4 5 5 4 9( ( )) mod 2z y x y x nat z= + +
9 5 5z y x=
Числено функция nat(x) возвращает, например, 1 если в младшей
разрядной строке в ходе вычисления после подстановки значений было
получено 2 или 3. При получении 3, в младшей разрядной строке остается
единица, а две единицы переносятся в старшую разрядную строку как одна.
Ниже представлено примеры численных значений функции nat(x).
Таблица 1
Значения функции учета переноса nat(x)
x 0 1 2 3 4 5 6 7
nat(x) 0 0 1 1 2 2 3 3
После добавлении функции nat(x) в каждое разрядное уравнение, в
системе (2) исчезают разрядные связи, которые обусловлены наличием
переносов из младших разрядов в старшие. Т.е. уравнения системы могут
рассматриваться отдельно, и переставляться в рамках системы между собой.
Но при дальнейшем решении системы уравнений возникает задача
упрощения функции nat(x). В ходе проведенных аналитических исследований
была получена следующая зависимость:
1 2 1 2 1 2( ) ( ) ( ) ( * ) mod 2nat a a nat a nat a a a+ = + + (3)
50
Выведенная зависимость справедлива не только для неизвестных,
которые имеют булевой характер, но и для любых натуральных чисел.
Если значение переменной под функцией будет иметь три слагаемых, то
формула (3) примет вид:
1 2 3 1 2 3 1 2 3( ) ( ) ( ) ( *( )) mod 2nat a a a nat a nat a a a a a+ + = + + + + =
1 2 3 1 2 3 2 3mod 2 mod 2nat(a ) nat(a ) nat(a ) (a * (a a )) (a * a )+ + + + +
В дальнейшем, при увеличении количества слагаемых в функции, ее
упрощение реализуется путем условного разбития суммы на две подсуммы и
упрощения уже этих подсумм. Если после упрощения оказывается, что в
полученном выражении имеется функция nat(x) с суммой неизвестных, то
разбитие и последующие упрощение функции повторяется.
В общем случае, когда под функцией имеется больше двух слагаемых,
равенство (3) приобретает следующую форму:
1
1 2 11 1
( .. ) ( ) ( )
n n n
n i i jj ii i
nat a a a nat a a a
−
= +
= =
+ + + = + ∗ ⊕∑ ∑
В системе уравнений неизвестные согласно условия могут принимать
значения только или 0 или 1. Это дает возможность сокращать
1
( )
n
i
i
nat a
=
∑ при
условии, что выражением под функцией являются или данные неизвестные,
или их произведение, или их сума по модулю 2. Если это не так, то возможно
упрощение функции описанным выше способом.
По своей сути слагаемое
1
11
( )
n n
i jj ii
a a
−
= +
=
∗ ⊕∑ равенства (4) является
обобщенной функцией сигнала переноса на выходе одноразрядного
сумматора, который используется при построении многоразрядных
сумматоров и матричных умножителей [5]. В одноразрядном сумматоре
значение выхода переноса 1iC + в зависимости от входных сигналов ,i iA B и
входного сигнала переноса iC равно
1 ( )*i i i i i iC A B A B C+ = ∗ + ⊕ . (5)
Обобщенная формула сигнала выхода переноса от многих входных
сигналов на многоразрядный сумматор не используется, так как
многоразрядный сумматор синтезируется из набора одноразрядных, которые
используются как минимальные логические составляющие. Сигналы выхода
переноса одноразрядных сумматоров в составе многоразрядных сумматоров
или умножителей являются входными для других одноразрядных
сумматоров в составе этих логических схем.
Используя функцию ( )nat a для преобразования исходной системы
уравнений (1), получается система, которая уже не имеет разрядных связей
между уравнениями, а сами уравнения имеют вид сумм вариантов
произведений неизвестных по модулю два. Ниже приводится пример
51© Н.Я.Шингера, Л.М.Щербак
системы для конкретного значения факторизируемого числа, где a, b, c, d ,f
разряды простого числа:
afdbc bac b bc ac fdc fbd afd afdb badc bdc⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ +
1afdb afdbc bac afdbc⊕ + ⊕ =
1 afdbc bac b bc ac fdc fbd afd afdb badc⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ 0bdc =
1 0fd c b ac afd fdc badc bdc fbdc bac⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ =
0fdc bc bdc c b afdbc acd badc ac⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ =
0ac fdc bdc acfd afdbc afd fbd bc bac d acd⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ =
1 1bd fbd afd afdb b bac fbdc acfd bc⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ =
ac bc fbc fb bac ba fdc bd acfd afd afdb⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕
1d fd bdc fbdc fbd⊕ ⊕ ⊕ ⊕ =
0c a cd b ac f fd afd fc fdc⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ =
В отличии от формулы (5) введенная функция (4) дает возможность
представить исходную систему уравнений в несвязанном виде, что упрощает
дальнейшее ее решение.
1. Жилин А.В., Мохор В.В. Структурный метод факторизации больших целых чисел//
Моделювання та інформаційні технології. Спец. випуск зб. наук. пр. ІПМЕ НАН
України – спец випуск - К.:2008. - С.49 – 57
2. Рабинер Р., Гоулд Б. Теория и применения цифровой обработки сигналов. – М.:
Издательство «МИР», 1978. – 836 с.
3. Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. — М.:МЦНМО,
2003.—328 с.
4. Шнайер Б. Прикладная криптография. – М.: Издательство ТРИУМФ, 2003 – 816 с.:
ил.
Поступила 5.02.2009р.
УДК 624.046.5
Н.Я.Шингера, ТДТУ, м. Тернопіль
Л.М.Щербак, д-р. техн. наук, ТДТУ, м. Тернопіль
СТАТИСТИЧНИЙ АНАЛІЗ РОБОТИ
ЗВАРНИХ КОНСТРУКЦІЙ ПРИ НАВАНТАЖЕННЯХ
The author has compared and analysed the results of machine computation of
welded girder load-carrying capacity by the finite-element method and experimental
observation of a girder under static load. Satisfactory coincidence of the results at light
load and essential divergence of the results at high load were revealed.
|