On the solutions of linear systems over additively idempotent semirings

2024/04/04 by Sánchez, Álvaro Otero, Camazón, Daniel, Ramos, Juan Antonio López · 2 citations
#15A80 #16Y60 #16Z05 #94A60 #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Rings and Algebras (math.RA)

paper · doi:10.48550/arxiv.2404.03294

Abstract

The aim of this article is to solve the system XA=Y where A=(a_ij)∈ M_{m× n}(S), Y∈ 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.

Cited by

• Weighted k-Path and Other Problems in Almost O^*(2^k) Deterministic Time via Dynamic Representative Sets
• Marginal sets in semigroups and semirings

Related

• On the Maximal Solution of A Linear System over Tropical Semirings
• Computing Least and Greatest Fixed Points in Absorptive Semirings
• Analysis of linear systems over idempotent semifields
• Universal algorithms, mathematics of semirings and parallel computations
• On key exchange protocol based on Two-side multiplication action