Browse
Recent Submissions
Item Застосування медового шифрування до схеми цифрового підпису Шнорра(2021) Олійник, МаріяСтійкість криптосистем значною мірою залежить від надійності захисту секретних ключів, які в них використовуються. Зокрема, процедура генерування останніх повинна повертати достатньо різноманітні ключі, щоб їх не можна було підібрати за допомогою атаки повного перебору (brute-force attack). Медове шифрування використовують як додатковий бар’єр захисту ключів криптосистем для сповільнення атаки повного перебору. Як і для "криптографії білої скриньки" (White box cryptography), існують різні схеми медового шифрування залежно від того, на що спрямовано додатковий захист. Потреба додатково захищати таємні ключі виникає у системах віддаленого доступу, у контексті надання доступу до інформації авторизованим користувачам. У цій статті побудовано схеми додаткового захисту ключів системи цифрового підпису Шнорра, наведено псевдокод відповідних алгоритмів, проаналізовано складність атаки повним перебором.Item Diameter Search Algorithms for Directed Cayley Graphs(2021-05) Olshevskyi, MaksymIt is considered a well known diameter search problem for finite groups. It can be formulated as follows: find the maximum possible diameter of the group over its system of generators. The diameter of a group over a specific system of generators is the diameter of the corresponding Cayley graph. In the paper a closely related problem is considered. For a specific system of generators find the diameter of corresponding Cayley graph. It is shown that the last problem is polynomially reduced to the problem of searching the minimal decomposition of elements over a system of generators. It is proposed five algorithms to solve the diameter search problem: simple down search algorithm, fast down search algorithm, middle down search algorithms, homogeneous down search algorithm and homogeneous middle down search algorithm.Item Поліноміальне представлення двійкових дерев ентропійних бінарних кодів(2021) Морозов, ДенисВажливою складовою потокового обміну великими об’ємами інформації є алгоритми стискання інформаційного потоку, які своєю чергою поділяють на алгоритми стискання без втрат (ентропійні) — Шепопа, Хафмана, арифметичне кодування, умовно стискаючі — LZW та інші бієкції інформаційного конусу, алгоритми стискання з втратами, наприклад, mp3, jpeg та низка інших. Під час побудови алгоритму стискання з втратами важливим є дотримуватись певної формальної стратегії. Сформулювати її можна таким чином: після опису множини об’єктів, які є атомарними елементами обміну в інформаційному потоці, необхідно побудувати абстрактну схему цього опису, що дозволить визначити межу для абстрактних зрізів цієї схеми, за якою починаються допустимі втрати. Підходи до виявлення абстрактної схеми, що породжує алгоритми стискання з допустимими втратами, можуть бути отримані з контексту предметної області. Наприклад, алгоритм стискання аудіопотоку може розділяти сигнал на прості гармоніки та залишає серед них ті, що розташовані в певному діапазоні сприйняття. Таким чином, отриманий на виході сигнал є певною абстракцією вхідного, що містить важливу інформацію згідно з контекстом слухового сприйняття аудіопотоку та представлений меншою кількістю інформації. Подібний підхід використовується в форматі mp3, який є стискаючим представленням. На відміну від алгоритмів стискання з втратами, ентропійні алгоритми стискання не вимагають аналізу контексту, а можуть бути побудовані згідно з частотною картиною. Серед відомих алгоритмів побудови таких кодів можна згадати алгоритм Шеннона Фано, алгоритм Хафмана та арифметичне кодування. Знаходження інформаційної ентропії для заданого коду Шеннона є тривіальною задачею. Обернена задача, а саме пошук відповідних кодів Шеннона, що мають наперед задану ентропію та з невизначеними ймовірностями, що є від’ємними цілими степенями двійки, є достатньо складною. Вона може бути вирішена прямим перебором, але суттєвим, недоліком цього підходу є його обчислювана складність. У цій cm am т і запропоновано альтернативний підхід до пошуку таких кодів. Описана техніка поліноміального представлення двійкових дерев бінарних кодів Шеннона з імовірностями, що є від’ємними цілими степенями двійки, дає змогу будувати відповідні коди за відомим значенням інформаційної ентропії.Item Побудова пари коспектральних 5-регулярних графів, один з яких має досконале парування, а інший – ні(2021) Соболєв, Владислав; Соломко, ВікторіяУ цій статті розглядаються тільки прості неоріентовні графи. Проблема пошуку досконалого парування у довільному простому графі є відомою і популярною в теорії графів. Її застосовують у різноманітних сферах, таких як хімія, комбінаторика, теорія ігор тощо. Паруванням М у простому графі О називають множину попарно несуміжних ребер, тобто таких, що не мають спільних вершин. Парування називають досконалим, якщо воно покриває усі вершини графа, тобто кожна з вершин графа інцидентна рівно одному з ребер у досконалому паруванні. За теоремою Кеніга, регулярні дводольні графи додатного степеня завжди мають досконале парування. Проте графи, які не є дводольними, потребують додаткових досліджень. Мультимножину власних значень матриці суміжності називають спектром графа. Окремою цікавою задачею теорії графів є пошук попарно неізоморфних коспектральних графів, тобто неізоморфних графів з однаковим спектром. У цьому напрямі проводились дослідження щодо пошуку конкретних конструкцій коспетральних пар графів. Крім того, цікавими є знаходження коспектральних графів, які мають додаткові властивості, наприклад, знаходження коспектральних графів, для одного з яких існує досконале парування, а для другого — ні. Блазік, Камінгс і Гамерс дослідили, що для кожного к > 5 існує пара коспектральних зв’язних к-регулярних графів, де один має досконале парування, а інший — ні. При доведенні цієї теореми автори використали конструкцію перемикання Годзіла Маккея. За допомогою цієї конструкції у нашій роботі покроково описано побудову пари коспектральних зв’язних 5-регулярних графів. Для одного з побудованих графів існує досконале парування, яке наведене в цій статті. Для другого побудованого графа досконалого парування не існує. Побудовані графи мають 42 вершини і складаються з 5 блоків, що з’єднані між собою мостами. За допомогою комп’ютерних засобів обчислено спектр побудованих графів. Таким чином перевірено, що пара справді є коспектральною.Item Risk modelling approaches for student-like models with fractal activity time(2021) Solomanchuk, Georgiy; Shchestyuk, NataliiaThe paper focuses on value at risk (V@R) measuring for Student-like models of markets with fractal activity time (FAT). The fractal activity time models were introduced by Heyde to try to encompass the empirically found characteristics of read data and elaborated on for Variance Gamma, normal inverse Gaussian and skewed Student distributions. But problem of evaluating an value at risk for this model was not researched. It is worth to mention that if we use normal or symmetric Student‘s models than V@R can be computed using standard statistical packages. For calculating V@R for Student-like models we need Monte Carlo method and the iterative scheme for simulating N scenarios of stock prices. We model stock prices as a diffusion processes with the fractal activity time and for modeling increments of fractal activity time we use another diffusion process, which has a given marginal inverse gamma distribution. The aim of the paper is to perform and compare V@R Monte Carlo approach and Markowitz approach for Student-like models in terms of portfolio risk. For this purpose we propose procedure of calculating V@R for two types of investor portfolios. The first one is uniform portfolio, where d assets are equally distributed. The second is optimal Markowitz portfolio, for which variance of return is the smallest out of all other portfolios with the same mean return. The programmed model which was built using R-statistics can be used as to the simulations for any asset and for construct optimal portfolios for any given amount of assets and then can be used for understanding how this optimal portfolio behaves compared to other portfolios for Student-like models of markets with fractal activity time. Also we present numerical results for evaluating V@R for both types of investor portfolio. We show that optimal Markowitz portfolio demonstrates in the most of cases the smallest possible Value at Risk comparing with other portfolios. Thus, for making investor decisions under uncertainty we recommend to apply portfolio optimization and value at risk approach jointly.Item Алгоритм пошуку кількості рухомих точок підстановок із силовських 2-підгруп Syl2(S2n) симетричних груп S2n(2021) Ольшевська, ВітаУ статті запропоновано алгоритм пошуку кількості рухомих точок підстановок силовських 2-підгруп Syl2(S2n) симетричних груп S2n, n є N. Для побудови цього алгоритму використано ізоморфізм між групою Syl2(S2n) та групою бінарних кореневих дерев з мітками. Також обчислено складність запропонованого алгоритму та його середню кількість кроків для силовської 2-підгрупи симетричної групи S2n. Обраховано кількість підстановок із Syl2(S2n), що мають максимальну кількість рухомих точок.Item Стійкість у симетричній моделі гри видобутку ресурсів із коаліційною структурою(2021-05) Силенко, ІлляГра видобутку ресурсів / накопичення капіталу є стохастичною грою з ненульовою сумою і необмеженим горизонтом, що утворена розширенням економічної моделі оптимального росту (optimal growth) на m стратегічно конкуруючих між собою агентів, у спільному володінні яких опиняється відновлювальний ресурс. У науковій літературі з тематики велику увагу приділено існуванню рівноваги за Нешем в окремих моделях цієї гри, зокрема симетричних. У цій статті пропонується долучити до розгляду симетричної гри видобутку ресурсів коаліційну складову. А саме, досліджується стійкість відносно коаліційних відхилень у грі з фіксованою коаліційною структурою. Припускається, що на множині гравців задано розбиття на коаліції, що не перетинаються і залишаються сталими протягом усієї тривалості гри. При цьому, учасники однієї коаліції здатні узгоджувати дії, здійснюючи спільні кооперативні відхилення. Таким чином, впроваджується природний концепт наявності соціальних взаємозв'язків між агентами, що може відтворювати потенційний контекст у практичному застосуванні. Поняття стійкості в межах статті визначається як положення, від якого жодна зі встановлених коаліцій не здатна відхилитись, одночасно збільшивши сумарний виграш усіх її членів. Існування такої стійкості розглядається в рамках конкретної симетричної моделі гри видобутку ресурсів з необмеженими функціями корисності гравців. Ця модель раніше досліджувалася у роботах [12; 13], де було виведено існування Стаціонарної Марковської Ідеальної Рівноваги в рамках симетричної та несиметричної структури гри. Першою особливістю моделі є те, що функції корисності гравців покладено степеневими та строго опуклими вгору, тобто, згідно з економічною термінологією, ізоеластичними. По-друге, в якості закону переходу між станами взято геометричне випадкове блукання, параметром якого є спільні інвестиції гравців. Доводиться, що в описаній постановці задачі існує стійкість відносно коаліційних відхилень для будь-якого розбиття множини агентів на коаліції. Метод доведення цього факту одночасно окреслює алгоритм побудови відповідних стійкому положенню стаціонарних стратегій, що можна використовувати в практичних цілях. Наприкінці розглянуто два приклади з різною числовою постановкою, що ілюструють можливі варіанти залежності індивідуальних виграшів гравців від того, яку коаліційну структуру встановлено на початку гри.