..

Tropical geometry and cryptography

Tropical semiring

Đầu tiên ta có khái niệm về nửa vành (semiring). Một tập hợp $S$ với hai phép toán hai ngôi kí hiệu là $(S, \oplus, \otimes)$ được gọi là một nửa vành nếu như nó thỏa mãn các tính chất sau:

  1. $(S, \oplus)$ là một vị nhóm giao hoán, với phần tử không kí hiệu là $0$
  2. $(S, \otimes)$ là một nửa nhóm.
  3. Phép nhân phân phối hai phía đối với phép cộng, tức là:
$\begin{gather*} x\otimes ( y\oplus z) =x\otimes y\oplus x\otimes z\\ ( y\oplus z) \otimes x=y\otimes x\oplus z\otimes x \end{gather*}$
  1. $0 \otimes x=x\otimes 0=0$ với mọi $x\in S$.

Mọi vành đều là nửa vành. Trong khi đó một nửa vành mà không phải là vành được gọi là nửa vành thực sự.

Bây giờ, đối với nửa vành nhiệt đới (tropical semiring) được kí hiệu là $(\mathbb{R} \cup \lbrace \infty\rbrace, \oplus, \otimes)$ với các phép toán được định nghĩa như sau:

$\begin{gather*} x \oplus y = \min(x,y) \\ x \otimes y = x+y \end{gather*}$

Tổng nhiệt đới của hai số thực $x$ và $y$ là giá trị nhỏ hơn trong hai số đó còn tích nhiệt đới của hai số lại là tổng của chúng (lấy tổng thông thường như ta làm việc trên tập số thực).

Chẳng hạn: $4 \oplus 9 = 4$ và $4 \otimes 9 = 13$.

Hai phép toán trên thỏa mãn luật phân phối của một nửa vành và đồng thời có các phần tử trung hòa tương ứng. Đối với phép cộng thì phần tử trung hòa là $\infty$ vì $x \oplus \infty = \min(\infty,x)=x$, còn phép nhân sẽ là $0$ vì $x \otimes 0 = x + 0 = x$.

Trong sage ta sẽ sử dụng lớp TropicalSemiring để làm việc với nửa vành nhiệt đới. Lớp gồm 2 tham số đầu vào là base và use_min. Ở đây ta sẽ có hai tropical semiring khác nhau tùy thuộc vào việc ta muốn sử dụng $\min$ hay $\max$ làm phép cộng, nếu như là $\min$ thì ta có tập hợp là $\mathbb{R} \cup \lbrace \infty\rbrace$ còn nếu như là $\max$ thì ta có tập hợp là $\mathbb{R} \cup \lbrace -\infty\rbrace$.

Cả hai sẽ đẳng cấu với nhau thông qua phép biến đổi $x \mapsto -x$ và trong bài này ta sẽ thống nhất sử dụng $\min$.

Tính toán:

sage: T = TropicalSemiring(base=QQ, use_min = true)
sage: T(4) + T(9)
4
sage: T(4) * T(9)
13
sage: T(2)/T(1)
1
sage: T(2) ^(-3/7)
-6/7
sage: