On the solutions of linear systems over additively idempotent semirings
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911827652247552 |
|---|---|
| author | Sánchez, Álvaro Otero Camazón, Daniel Ramos, Juan Antonio López |
| author_facet | Sánchez, Álvaro Otero Camazón, Daniel Ramos, Juan Antonio López |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_03294 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the solutions of linear systems over additively idempotent semirings Sánchez, Álvaro Otero Camazón, Daniel Ramos, Juan Antonio López Information Theory Rings and Algebras 15A80, 16Y60, 16Z05, 94A60 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. |
| title | On the solutions of linear systems over additively idempotent semirings |
| topic | Information Theory Rings and Algebras 15A80, 16Y60, 16Z05, 94A60 |
| url | https://arxiv.org/abs/2404.03294 |