On the solutions of linear systems over additively idempotent semirings

The aim of this article is to solve the system $XA=Y$ where A=(aᵢⱼ)∈ Mm× n(S), Y∈ Sᵐ 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.