Рекурентні алгоритми обчислення кореня довільного степеню у кільці лишків

Скорочена інформація про документ
dc.contributor.authorКовальчук, Людмила
dc.contributor.authorБеспалов, Олексій
dc.contributor.authorОгнєв, Павло
dc.contributor.authorKovalchuk, Ludmyla
dc.contributor.authorBespalov, Alexey
dc.contributor.authorOgnev, Pavel
dc.contributor.authorКовальчук, Людмила
dc.contributor.authorБеспалов, Алексей
dc.contributor.authorОгнев, Павел
dc.date.accessioned2014-09-08T12:24:58Z
dc.date.available2014-09-08T12:24:58Z
dc.date.issued2013
dc.description.abstractenIn this paper, the criterion of power element of finite field is obtained and simple algorithms for calculating the cubic root and recursive algorithms for calculating the roots of higher powers are constructed. Power recognition algorithm and rooting for composite module (particularly for modulo n=pq) are completely determined by the corresponding algorithms for a simple modules, provided that factorization is known. It is also interesting to note that for n=pq the factorization problem and rooting problem are polynomial equivalent relatively probabilistic algorithm. These algorithms are primarily interesting from a mathematical point of view, and their particular case – the cubic root extraction algorithm – can be used as aids in calculating the base point of the elliptic curve and for "imbedding" of plaintext into curve point, also if curve is defined over the residue rings instead of the field.uk
dc.description.abstractruВ данной работе получен критерий степенности элемента конечного поля и приведены простые алгоритмы вычисления кубичного коня и рекуррентные алгоритмы вычисления корней более высоких степеней из элемента поля, который является соответствующим степенным вычетом. Алгоритмы распознавания степенности и вычисления корня по составному модулю (например, по модулю n=pq) полностью определяются соответствующими алгоритмами для простого модуля, при условии, что известно разложение модуля на простые множители. Интересно также заметить, что задача разложения на простые множители и задача вычисления корня являются полиномиально эквивалентными относительно вероятностного алгоритма. Данные алгоритмы являются, прежде всего, интересными с математической точки зрения, а их частный случай – алгоритмы вычисления кубического корня – могут быть использованы как вспомогательные при вычислении базовой точки кривой и при "вложении" открытого текста в точку кривой, в том числе и если кривая задана над кольцом вычетов, а не над полем.uk
dc.description.abstractukУ даній роботі отримано критерій степеневості елемента скінченого поля та наведено прості алгоритми обчислення кубічного кореня та рекурентні алгоритми обчислення коренів більш високого степеню з елементу поля, який є відповідним степеневим лишком. Алгоритми розпізнавання степеневості та добування кореня за складеним модулем (наприклад, за модулем n=pq) повністю визначаються відповідними алгоритмами за простим модулем, за умови, що відомий розклад числа п на прості множники. Цікаво також зазначити, що задача розкладу на прості множники та задача добування кореня є поліноміально еквівалентними відносно імовірнісного алгоритму. Дані алгоритми є, перш за все, цікавими з математичної точки зору, а їх поодинокий випадок – алгоритми добування кубічного кореня – можуть бути використані як допоміжні при обчислення базової точки кривої та при "вкладанні" відкритого тексту у точку кривої, у тому числі і якщо крива задана над кільцем лишків, а не над полем.uk
dc.format.pagerangeС. 58-67uk
dc.identifier.citationКовальчук Л. Рекурентні алгоритми обчислення кореня довільного степеню у кільці лишків / Людмила Ковальчук, Олексій Беспалов, Павло Огнєв // Правове, нормативне та метрологічне забезпечення системи захисту інформації в Україні : науково-технічний збірник. – 2013. – Вип. 1(25). – С. 58–67. – Бібліогр.: 8 назв.uk
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/8568
dc.language.isoukuk
dc.publisherНТУУ "КПІ"uk
dc.publisher.placeКиївuk
dc.source.nameПравове, нормативне та метрологічне забезпечення системи захисту інформації в Україні: науково-технічний збірникuk
dc.status.pubpublisheduk
dc.subjectкільця лишківuk
dc.subjectдобування кореняuk
dc.subjectеліптичні кривіuk
dc.subject.udc512uk
dc.titleРекурентні алгоритми обчислення кореня довільного степеню у кільці лишківuk
dc.title.alternativeRecursive algorithms for computing the root of arbitrary power in residue ringsuk
dc.title.alternativeРекуррентные алгоритмы вычисления корня произвольной степени в кольце вычетовuk
dc.typeArticleuk
thesis.degree.levelmasteruk

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
25_p58.pdf
Розмір:
344.77 KB
Формат:
Adobe Portable Document Format
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
1.71 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Правове, нормативне та метрологічне забезпечення системи захисту інформації в Україні: науково-технічний збірник, Вип. 1(25)