Message Boards Message Boards

[WSS18] Algebraic Computations over Tropical Semi-Ring

Posted 7 years ago
POSTED BY: Anjali Raj
11 Replies

This is very nice. I wonder if it would make sense to do the linear algebra using Inner, with the plus and times arguments suitably altered?

POSTED BY: Daniel Lichtblau
Posted 3 years ago

Has this evolved? Is this the current "best code"? Are there test cases?

POSTED BY: Jamie Lawson
Posted 3 years ago

Also, this is for min-plus algebra. Is there a list of what needs to be changed for max-plus algebra (the other Tropical Algebra)?

POSTED BY: Jamie Lawson
Posted 3 years ago

Hi Jamie, this project has not been updated.

POSTED BY: Anjali Raj
Posted 3 years ago

To create similar functionalities for max-plus algebra, one can redefine the addition operator of the semi-ring to max operator and verify all the conditions for semi-ring (associativity, commutativity, distributivity, etc).
I haven't checked for corner cases or test cases for max-plus algebra so maybe you can explore that area.

POSTED BY: Anjali Raj

enter image description here -- you have earned Featured Contributor Badge enter image description here Your exceptional post has been selected for our editorial column Staff Picks http://wolfr.am/StaffPicks and Your Profile is now distinguished by a Featured Contributor Badge and is displayed on the Featured Contributor Board. Thank you!

POSTED BY: EDITORIAL BOARD
Posted 3 years ago

The Max-Plus operators themselves are not the problem here. The issues are in the linear algebra. For instance, do any changes need to be made to TropicalSingularityQ to support Max-Plus? I'm guessing not. Then there's the TropicalAdjoint. There is a call to Identity, and the identity matrices are different for Min-Plus and Max-Plus, so presumably that needs to be changed, and the right additive identity, but is that all? For TropicalDeterminant, do we just need to apply the right addition operator for Max-Plus? What about TropicalRank? I guess we need the right identity matrix, and hopefully the rest of the changes (if any) are covered by the changes (if any) to TropicalSingularityQ. But I might be missing something. Then there's the overall issue of tropical rank. There are three different forms of rank for a tropical matrix. Which of those three is implemented here? It's unclear.

POSTED BY: Jamie Lawson

Hello Anjali,

As the Stickel KEP protocol for obtaining a common key is developed in your code (see [1]), it does not work. Sorry.

Can you give the complete Mathematica code (i.e. TropicalMatrixTimes was not defined) with which you obtained the published numerical matrix?

Did you publish or prepublish (arXiv, eprint,..) your results?

The way you present it seems interesting but it is useless because it is not possible to follow your steps, something essential in scientific research. Thank you.

[1] 2014-Grigoriev & Shpilrain-Tropical cryptography.pdf

cheers! Peter

POSTED BY: Peter Hecht

Some data missing but the idea is good.

POSTED BY: Peter Hecht
Posted 1 year ago

Hi Peter, my bad, TropicalMatrixTimes is defined as following:

TropicalMatrixTimes[a_List,b_List]:=Inner[Plus,a,b,Min]

I forgot to add the mathematica package that was developed along with this project. I've added the link to github repository now. Please note that I'm no longer maintaining the code.

POSTED BY: Anjali Raj

Thanks! but more functions didnt work like TropicalPolynomial[x,y]. It would be nice if you try your own code like I did to get a numeric key but with no result, surelly you have a functional workinq notebook to share. Thx.

PUBLIC PARAMETERS GENERATION A = {{1, 5}, {-2, 7}} B = {{5, 0}, {-3, 4}}

ALICE p1[A] = TropicalPolynomial[p1, A] p2[B] = TropicalPolynomial[p2, B] p = TropicalMatrixTimes[p1[A], p2[B]

BOB q1[A] = TropicalPolynomial[q1, A] q2[B] = TropicalPolynomial[q2, B] q = TropicalMatrixTimes[q1[A], q2[B]]

KEYS keyA = TropicalMatrixTimes[TropicalMatrixTimes[p1A, q], p2B] keyB = TropicalMatrixTimes[TropicalMatrixTimes[q1A, p], q2B]

Best Peter

POSTED BY: Peter Hecht
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract