Open AccessLogic program invertibility in cryptography problems
Author(s) -
N Avkhimovich
Publication year - 2021
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1902/1/012049
Subject(s) - invertible matrix , cryptography , computer science , inverse , completeness (order theory) , theoretical computer science , mathematics , discrete mathematics , algorithm , calculus (dental) , arithmetic , pure mathematics , medicine , mathematical analysis , geometry , dentistry
This work contains an analysis of problems those occur when the logic programs are used for cryptography problems. We explore the following problems: whether a logic program is invertible; whether one program is an inverse of the other. It was proved coNP-completeness for both problems. The size of logic programs also considered. We have found an instance of a program of linear length such that the length of the inverse program is exponential.