1. On the solutions of linear systems over additively idempotent semirings
- Author
-
Sánchez, Álvaro Otero, Camazón, Daniel, and Ramos, Juan Antonio López
- Subjects
Computer Science - Information Theory ,Mathematics - Rings and Algebras ,15A80, 16Y60, 16Z05, 94A60 - Abstract
The aim of this article is to solve the system $XA=Y$ where $A=(a_{ij})\in M_{m\times n}(S)$, $Y\in S^{m}$ and $X$ is an unknown vector of size $n$, being $S$ an additively idempotent semiring. If the system has solutions then we completely characterize its maximal one, and in the particular case where $S$ is a generalized tropical semiring a complete characterization of its solutions is provided as well as an explicit bound of the computational cost associated to its computation. Finally, when $S$ is finite, we give a cryptographic application by presenting an attack to the key exchange protocol proposed by Maze, Monico and Rosenthal., Comment: 24 pages
- Published
- 2024