Featured Post

Có một Biển Đông trên không gian mạng

Có một Biển Đông trên không gian mạng Thái Dương Mùa hè 2014, giữa lúc người Việt trong nước và hải ngoại đang sôi sục vì Trung Quốc đư...

Monday, November 30, 2015

Bò lên Half Dome

Giữa lưng chừng núi, tôi đoán nếu mà rớt từ đây xuống chắc cũng lâu lắm người ta mới tìm thấy xác mình. Tôi ráng hết sức bấu vô sợi dây cáp, ráng một hồi thì hết sức thiệt. Hai tay mỏi nhừ, chân trái chuột rút. Chưa bao giờ tôi thấy mệt và sợ chết như vầy. Giữa lúc ngàn cân treo sợi tóc, tự dưng tôi muốn tính xem từ đây mà rơi tự do, với chiều cao thế này, vận tốc thế này, gia tốc thế này, sức gió thế này, hướng gió thế này, không biết bao giờ mới chạm đất và cách chân núi bao xa.

--

Nhóm chúng tôi gồm 5 người, khởi hành từ trưa thứ bảy từ Bay Area, chạy một mạch đến chập choạng tối thì đến Yosemite, công viên quốc gia lớn nhất California cũng là công viên đầu tiên của nước Mỹ. Vô công viên không tìm được chỗ cắm trại, cả đám quay ra ngoài, may quá tìm được một nơi cách cổng chừng 10' lái xe. Hạ trại, ăn uống nhanh, đi ngủ sớm, mai hứa hẹn là một ngày dài. Bọn tôi sẽ trèo lên Half Dome.

Yosemite rộng kinh khủng, hơn 3.000 cây số vuông, cả một vùng đồi núi bạt ngàn, bao la mây trời sông nước, bao quanh một thung lũng nhỏ, vốn là nơi sinh sống của thổ dân da đỏ từ 3.000 năm trước, bây giờ trở thành trung tâm của các hoạt động du lịch và khám phá. Yosemite nổi tiếng bởi các thác nước hùng vĩ, cai trị bởi mấy ông hà bá năm nào cũng ăn mấy mạng người; bởi lũ gấu đen Bắc Mỹ thích ăn hamburger hơn là tổ ong, đêm nào cũng mò vô khu vực có người cắm trại tìm đồ ăn thừa; bởi mấy cây xồi khổng lồ mấy ngàn năm tuổi, thân cây lớn đến nỗi có thể đục lỗ để chạy xe xuyên qua; nhưng nổi bậc hơn cả là những dãy núi đá hoa cương (granite) cao sừng sững, thánh địa Macca của dân leo núi đá (rock climbing) và dù lượn các kiểu.

Cảnh thung lũng Yosemite, nhìn từ Glacier Point. Half Dome là cái núi dáng nửa máy vòm bên tay phải.
Tôi có anh đồng nghiệp chuyên đi leo mấy ngọn núi ở đây. Ảnh nói leo từ Yosemite Valley lên thẳng Half Dome mất khoảng 16 tiếng. Bọn tôi không phải siêu nhân như anh đó, nên chọn giải pháp dễ nhất là đi bộ từ chân núi lên (tiếng Mỹ gọi là hiking). 5h30' sáng cả đám lòm còm bò dậy, dọn trại, ăn sáng, chuẩn bị lên đường. 7h30' xe chạy. Cách cổng chỉ 10' nhưng mà cũng hơn cả tiếng mới vô được tới Yosemite Valley. Gần 9h chúng tôi đến được đường mòn để bắt đầu hình trành đi, đi nữa, đi mãi rồi đi thêm chút nữa mà vẫn chưa tới.

Half Dome, dựng đứng 2700m giữa Yosemite.
Bọn tôi chọn đi theo hướng thác Vernal, đường đi đẹp ơi là đẹp. Lúc bấy giờ đang là đầu mùa xuân, tuyết trên các đỉnh núi vẫn còn nhiều, nên thác nào cũng ầm ầm nước lũ. Gọi là đi nhưng thật ra phải leo dốc liên tục, ít có đường bằng. Tổng cộng phải leo lên gần 1.600 mét, cỡ bằng leo cầu thang lên một tòa nhà 500 tầng. Trước đó bọn tôi cũng có làm vài chuyến leo kiểu này rồi, dụng cụ đủ, nên cũng không mệt lắm.

Cả đám đi hoài đi hoài, đến khoảng 2h chiều thì bắt đầu thấy Half Dome. Càng đến gần càng thấy ớn. Đã biết là đoạn cuối phải trèo dây cáp lên, nhưng nhìn từ xa cái dây cáp nó treo thẳng đứng, sao mà leo lên trời!? Rồi cả đám nghĩ, àh chắc cái đó không phải dây cáp mà mình sẽ leo lên đâu, chắc phải có cái dây khác, nhưng rốt cuộc đúng là nó thật. Khoảng 3h thì bọn tôi mò lên đến được đinh Sub Dome để bắt đầu leo lên Half Dome. Đến gần hơn thì thấy cũng không đáng sợ lắm. Cả bọn đeo bao tay vô, mặc thêm áo vì gió, chụp hình lần cuối, để có gì còn có ảnh thờ. Nhìn đoàn người đi xuống không phải ai cũng cơ bắp lực lưỡng, tôi nghĩ bụng chắc cũng không sao đâu. Thiệt là lầm to.

Phải đi bộ 6 tiếng, 13 cây số mới tới được chỗ này. Còn một đoạn ngắn nữa thôi là lên đỉnh, nhưng... chút nữa là hết cười.
Đoạn cuối từ đỉnh Sub Dome lên Half Dome chỉ khoảng hơn 120 mét, nhưng dóc dựng đứng có đoạn từ 45 đến 60 độ, không thể đi bộ lên được. Người ta thiết lập một hệ thống dây cáp chạy dọc theo sườn núi, ai muốn leo lên thì đu dây đi từng bước, khoảng 2 mét thì có một miếng gỗ, có thể dừng lại để nghỉ. Chỉ có một đường duy nhất cho hai chiều, người đi lên và đi xuống phải tự nhường nhau. Muốn leo lên đây phải có giấy phép. Mỗi ngày chỉ có 400 giấy phép được xuất ra, nếu có nhiều người muốn đi hơn thì phải rút thăm. Nếu mò lên đây mà không có giấy phép bị phát hiện sẽ bị phạt lên đến 5.000 USD hoặc 6 tháng tù.

Nhìn lên không thấy đỉnh, nhìn xuống thì cỡ... 20 giây.

---

Không biết tôi đã dừng lại bao lâu, có một đoàn dài đang chờ phía sau. Lần đâu tiên trong đời tôi sợ mình sẽ chết vì chơi ngu. Chỗ này cũng đã có vài người chết. Tôi nhẩm nếu rơi tự do chắc mất khoảng 20 giây mới chạm đất. Đứng một hồi tôi thấy đỡ hơn, nhưng cứ đi một bước là tay lại mỏi nhừ. Có vẻ chỉ có mình tôi là bị như vậy, những người khác trong đoàn đều ổn. D. đi ngay phía sau nói chắc do tôi đi sai cách. Do khớp quá nên tôi ôm cả hai tay vào dây cáp bên tay trái, rồi leo lên giống như là người ta đu dây. Mệt không thể tả được, mà càng mệt thì càng sợ sẽ sơ sẩy. Tôi đã đánh giá thấp đoạn đường này, nên bị sốc khi thấy đã rất cố gắng mà vẫn trèo lên không nổi. D. nói phải dùng cả hai dây cáp, dùng sức đè dây cáp xuống, chùng người một chút rồi bước đi. Tôi làm theo thì thấy đúng là hiệu quả và đỡ mất sức hơn hẳn. Nhưng quan trọng nhất là tinh thần lên trở lại, vì đã thấy được đường ra khỏi tình thế ngặt nghèo đó.

Dùng cả hai tay, chùng người xuống và bước đi. May là qua đoạn dốc không nhìn thấy đỉnh thì đường dễ đi hơn.
Cuối cùng tôi cũng bò lên được tới nơi. Chắc mất khoảng 45' cho một đoạn đường 120 mét. Đỉnh Half Dome bằng phẳng, hồi xưa còn được cắm trại, bây giờ người ta cấm do trên đấy không có nhà vệ sinh. Nằm trên đỉnh, thò đầu ra ngoài vách đá, nhìn thẳng xuống thung lũng, gió thốc thẳng lên mặt, bay như chim, có lẽ là một cảm giác mà tôi sẽ không bao giờ quên.

Bọn tôi ở trên đỉnh chỉ khoảng 20'-30' rồi phải đi xuống vì từ xa có một đám mây đang kéo đến, nếu mà mưa hoặc có sét đánh thì rất nguy hiểm. Ban đầu tôi cũng lo không biết đi xuống thế nào, nhưng hóa ra dễ hơn nhiều, do không phải dùng sức. Chỉ cần làm theo cách D. chỉ là cứ đi xuống nhẹ nhàng. Sống rồi. Phew!

Từ đỉnh Sub Dome, bọn tôi phải cuốc bộ thêm 13 cây số đường núi nữa mới xuống lại thung lũng. Trời tối, đường toàn đá khó đi, trơn trượt khi đi ngang mấy cái thác, nhưng so với đoạn leo lên Half Dome thì chỉ là muỗi. Cả đám đến được chỗ đậu xe lúc hơn 9h30' tối, mệt lã, nhưng vui!


Monday, November 23, 2015

Tìm người tổ chức sự kiện

Tôi đang cần tìm người tổ chức sự kiện để hỗ trợ việc tổ chức TetCon 2016. Nếu có ai biết công ty hoặc cá nhân nào chuyên tổ chức các sự kiện như TetCon thì làm ơn để lại lời nhắn hoặc email cho tôi ở thaidn@gmail.com.

Cảm ơn nhiều.

Thursday, November 19, 2015

Trượt tuyết

Hồ Tahoe, nhìn từ một đỉnh núi nào đó ở Heavenly
Mùa đông ở đây cuối tuần không đi trượt tuyết cũng không biết làm gì khác. Trời tối sớm và lạnh, về nhà chỉ muốn rú ở trong nhà. Đọc sách riết cũng chán, may là còn có món này để giải trí.

Con nít ở đây trượt tuyết từ 4-5 tuổi, đến tầm 10 tuổi là coi như đã rành sáu câu. Còn dân nhiệt đới gió mùa như tôi, hăm mấy mới bắt đầu tập, không có năng khiếu, học mãi không vô. Định bỏ cuộc rồi ai dè có "thần đồng" chỉ cho vài chiêu, thế là ghiền.

Trượt tuyết khác với tất cả các món thể thao mà tôi từng chơi. Trước hết là mắc mỏ, đồ đạc sắm đủ cũng cả ngàn Obama. Đủ thứ món: giày, ski, pole, mắt kiếng, nón bảo hiểm, găng tay, quần áo ấm đặc biệt chống thấm, v.v. Giày với ski là hai thứ mắc nhất, nhưng cũng là hai thứ quan trọng nhất cần phải đầu tư nếu muốn đi lâu dài. Được cái đồ bền, một lần sắm có thể đi năm bảy mùa, sau đó còn có thể bán lại gỡ được chút vốn.

Bộ tam sên: boot, ski và pole
Có đồ rồi, cứ xem dự báo thời tiết là đi thôi. Từ nhà tôi chạy xe cỡ hơn 3 tiếng là đến chỗ hồ Tahoe, nơi có nhiều khu trượt tuyết tốt. Àh còn phải mua vé. Mấy năm đầu chưa biết có đi được không, tôi toàn mua vé lẻ, rốt cuộc tốn còn nhiều tiền hơn mua vé nguyên mùa. Vé nguyên mùa (season pass) được bán từ mấy tháng trước. Giá cả cũng tùy loại, nhưng nếu muốn đi được chỗ ngon thì cũng phải 400-500 Obama.

Mò lên được tới nơi, mang được giày vô, vác cái ski ra đến lift, nhiều lúc mệt muốn xỉu. Giày nhìn vậy, chứ mỗi chiếc cũng nặng cả kg, mang vô rồi đi lại mệt mỏi, chân cẳng tê hết. Nhưng khó nhất là lúc xỏ giày vô chân. Đôi của tôi hiện giờ mang vô dễ, nhưng mà lần nào cũng đổ mồ hôi hột với nó. Hồi xưa đi mướn giày, có khi phải mất cả nửa tiếng mới mang được. Có lúc ngày hôm trước mang được, hôm sau chẳng hiểu sao chẳng mang vừa nữa, thế là phải đi mướn đôi khác.

Xong rồi té. Tôi té không biết bao nhiêu lần. Té kiểu nào cũng có. Té rách cả quần. Có lúc còn té xém rớt xuống hồ nước. Té mà nản luôn. Nhiều lúc đứng trên núi, tự hỏi sao mình ngu quá, bỏ tiên ra để tự hành hạ bản thân như vầy, leo lên đây chi, giờ xuống làm sao. Nhưng mà xuống được tới nơi lại leo lên đi tiếp. Người ta nói là ngu mà lì.

Ski dễ đi, nhưng mà khó thạo. Tôi có thể đi không té từ mấy năm nay rồi, nhưng mà vẫn chưa thạo, kỹ thuật vẫn chưa tốt, mặc dù cũng đã đi học trường lớp này nọ. Chắc chưa đủ 10 ngàn giờ? Nhìn người ta đi thấy dễ lắm, nhưng lúc bước lên rồi mới thấy ngán. Dốc nhìn vậy chứ tốc độ có thể lên đến 70-80km/h hoặc hơn. Dễ mất bình tĩnh, run chân không điều khiển được ski.

Cảnh đẹp người cũng đẹp
Được cái ski resort nào cũng đẹp, cảnh nào cũng như lấy từ bưu thiếp ra. Lên núi rồi là đầu ốc tự dưng rỗng tuếch, chỉ còn biết mỗi trượt và trượt thật nhanh. Người nóng dần lên, mồ hôi túa ra, lướt băng băng qua các đỉnh đèo, tuyết bay mịt mù sau lưng, sướng không gì tả được.

Monday, November 9, 2015

TetCon updates

I'm finally back from a long vacation, and now, as usual, going to rush to make a few updates and announcements with regard to TetCon 2016. Please forgive my bad organizing!

First and foremost, Vietnamese hackers, why don't you submit anything to TetCon? We've got only a handful of submissions so far, and most of them are from oversea researchers. BTW if you submitted in the past few weeks, you'll get a yes/no response within one or two days.

We can always send the CFP to Twitter, DailyDave, etc., and I'm sure we'll see a lot of good submissions. But we want to save the spotlight for the new bloods in our local community. We also want to see women researchers and those from other minority groups. So if you have an idea or have done something cool in the past year or so, please drop us a line as soon as possible! The program committee, cfp@tetcon.org, can help evaluate and improve your works.

Secondly, we'll move to a new venue. I've had troubles raising sponsorships, so we'll move to something more affordable. It's a brand new hotel along the Ben Nghe channel. Perhaps not as fancy as Majestic, but it's still a four star and has good reputation. Parking will be better too!

And finally tickets for conf and sign ups for training will be announced this week!

Friday, November 6, 2015

Tales of The Cryptographer

Once upon a time most people thought that RSA encryption was unbreakable, until a cryptographer demonstrated a plaintext-recovery attack. The attack, a.k.a the million message attack, became instant classic and is the root of all error oracle attacks including padding oracle. It was 20 years ago.

There were a lot of criticisms against the Digital Signature Algorithm when it was introduced in the early 90s, but nobody actually came up with any concrete attacks, until a cryptographer demonstrated a private key-recovery attack. The attack, which exploits a leakage of a fraction of a bit, became legendary, and still works against most naive implementations. It was 15 years ago.

Hal Finney, who was probably the person that designed or co-designed Bitcoin, was once excited about a signature-forging attack against RSA. The attack was discovered by a cryptographer, who developed an exploit using only paper and pencil. It turned out that the attack can be used to forge CA certificates, which could be used, you know, to own the Internet. It was 10 years ago.

There were a lot of complaints against JavaScript crypto, but most of them don’t actually show any concrete pitfalls, until a cryptographer showed a key-recovery attack against a JavaScript implementation of AES. The same cryptographer went on disclosing multiple key-recovery or plaintext-recovery attacks against several well-known JavaScript implementations of OpenPGP. It was 5 or 4 years ago.

Like it or not, people love rolling their own crypto. They read Bruce Schneier, and they know the fact that themselves being incapable of breaking their own schemes does not give any security guarantee, so they go to StackOverflow, and challenge random strangers on the Internet to prove them wrong. Most answers are usually just as "OK, look good to me," but every once in a while there’s a cryptographer who'd reply with their secret keys. The cryptographer was upset because his answer didn’t get the most upvotes, but he keeps coming back because he just can’t stop breaking crypto. It was just last week, or perhaps, yesterday.

You might have guessed that I’ve been talking about the same cryptographer: Daniel Bleichenbacher. I didn’t know anyone else whose last name has almost become synonymous with most creative crypto attacks.

Thursday, November 5, 2015

A Whirlwind Tour of Galois Theory

translatedfor a. and j.

A few years ago I found an abstract algebra book at a used book sale. Although I knew I'd probably never read it I bought it anyway, 'cause it costed just one buck and I can't never say no to cheap books! Said book stayed quietly on my bookshelf for many months, and I'd totally forget about its existence if one day I didn't suddenly found myself wanting to solve a pretty cool problem, which is proving that 26 is the only natural number preceded by a square (25) and succeeded by a cube (27). People on Yahoo! Answers told me that it's a theorem by Fermat, and if I wanted to prove it I needed to know more about Unique Factorization Domain, but this is exactly the title of one of the chapters in that \$1 book!

I started reading it, and immediately got hooked to its chatty tone, and soon spent many evenings solving the exercises or searching for solutions. Eventually I got to prove that unique property of 26 (yay!), but the book offers more than that -- its second half is devoted to Galois and the theory named after him. I first heard about Galois when I was a kid, and always been inspired by his life story ever since. I was so excited having a chance getting to understand Galois's ideas, but the chapters became, however, more and more confusing. Perhaps the informal style, which has worked well for elementary stuff, backfires somewhat when it comes to an advanced theory that has many layers of abstraction. Perhaps it's just me not smart enough.

I kept pushing anyway, even doubling down after learning that Galois theory is also used in the theory of elliptic curves, another topic that I really want to master. Eventually things became clearer. I guess it's true that one can make oneself smarter by working harder. I got to understand the individual theorems, but didn't see the big picture until I tried to do this simple looking exercise:

Exercise: find the minimal polynomial $f(x) \in \mathbb{Q}[x]$ (i.e., its coefficients are rational) that accepts $\epsilon= 1 + \sqrt[3]{2} + \sqrt[3]{4}$ as a root.

An elementary solution is to set $f(x) = x^3 + ax^2 +bx + c$, and turn the equation $f(\epsilon) = 0$ into a system of equations in $a$, $b$, and $c$. That's actually my first attempt, but the calculation was so laborious that I abandoned it after a few minutes. I'm going to show you a more elegant elegant solution, which should also demonstrate some of the ideas behind Galois theory.

Galois discovered that if one knows a root of $f(x)$ one can easily calculate the other roots. Let $\delta$ và $\omega$ be the other two roots, we have

\[
\begin{equation}
f(x) = (x - \epsilon) (x - \delta) (x - \omega)
\end{equation}
\label{eq:f(x)}
\]

thus, the coefficients can be computed

$$
\begin{align*}
- a &=  \epsilon+ \delta+ \omega \\
b &=  \epsilon\delta+ \epsilon\omega + \omega\delta\\
-c & = \epsilon\delta\omega
\end{align*}
$$

Because $\epsilon \notin \mathbb{Q}$ in order to reduce $f(x)$ into linear polynomials as in $\eqref{eq:f(x)}$, we have to extend $\mathbb{Q}$. If you're not familiar with field extension, the following example might help.

Example 1: Consider $g(x) = x^2 - 2$. We can prove that $g(x)$ is an irreducible polynomial in $\mathbb{Q}$. In other words, it's impossible to reduce $g(x)$ into multiplicity of linear polynomials with rational coefficients. If we, however, extend $\mathbb{Q}$ by adjoining $\sqrt{2}$ to create $\mathbb{Q}(\sqrt{2})$, $g(x)$ is no long irreducible

$$
\begin{equation*}
g(x) = (x - \sqrt{2})(x + \sqrt{2})
\end{equation*}
$$

$\mathbb{Q}$ is a field, and

$$
\mathbb{Q}(\sqrt{2}) = \{a + b\sqrt{2}\ |\ a,\ b \in \mathbb{Q}\}
$$

is, too. Note that $\mathbb{Q}(\sqrt{2})$ is a 2-dimensional vector space over $\mathbb{Q}$. Because $\mathbb{Q} \subset \mathbb{Q}(\sqrt{2})$, we say that $\mathbb{Q}(\sqrt{2})$ is an extension of degree 2 over $\mathbb{Q}$. Because $-\sqrt{2} \in \mathbb{Q}(\sqrt{2})$,  $\mathbb{Q}(\sqrt{2})$ contains all the roots of $g(x)$, and thus is the splitting field of $g(x)$. The name comes from the fact that $g(x)$ splits completely into linear polynomials over $\mathbb{Q}(\sqrt{2})$. In other words, the splitting field of a polynomial contains all its roots.

Galois discovered that the group of automorphisms of the splitting field of a polynomial permutes its roots. Let $G = \{\sigma_0, \sigma_1,...,\sigma_n\}$, where $\sigma_i$ is an automorphism of the splitting field of $f(x)$ (we're going to define it in the next paragraph.) If we know $G$ and a root $\epsilon$, we can compute all other roots by computing $\sigma_i(\epsilon)$.

Let's go back to example 1. $\mathbb{Q}(\sqrt{2})$ is the splitting field of $g(x)$. Let $\sigma$ là be an automorphism of $\mathbb{Q}(\sqrt{2})$. By definition, $\sigma$ is a bijective $\sigma:\ \mathbb{Q}(\sqrt{2}) \rightarrow \mathbb{Q}(\sqrt{2})$ satisfying

$$
\begin{align*}
&\sigma(\alpha + \beta) = \sigma(\alpha) + \sigma(\beta) \\
&\sigma(\alpha\beta) = \sigma(\alpha)\sigma(\beta)
\end{align*}
$$

for all $\alpha,\ \beta \in \mathbb{Q}(\sqrt{2})$. Thus, $\sigma$ is an isomorphism from $\mathbb{Q}(\sqrt{2})$ to itself.

It's trivial to prove that $\sigma(0) = 0$ and $\sigma(1) = 1$, thus $\sigma(a) = a$ với mọi $a \in \mathbb{Q}$. We say that $\sigma$ fixes $\mathbb{Q}$. Consider $\sigma(a + b\sqrt{2})$, for $a,\ b \in \mathbb{Q}$

$$
\begin{align*}
\sigma(a + b\sqrt{2}) &= \sigma(a) + \sigma(b\sqrt{2}) \\
&= a + \sigma(b)\sigma(\sqrt{2}) \\
&= a + b\sigma(\sqrt{2})
\end{align*}
$$

Hence, the action of $\sigma$ on $\mathbb{Q}(\sqrt{2})$ completely depends on its action on $\sqrt{2}$.

Observation: $\sigma(\sqrt{2})$ is a root of $g(x)$. Indeed, we have $g(\sqrt{2}) = 0$, applying $\sigma$ against two sides of the equation

$$
\begin{align*}
\sigma(g(\sqrt{2})) &= \sigma(0) \\
\rightarrow \sigma(\sqrt{2})^2 - 2) &= 0 \\
\rightarrow \sigma(\sqrt{2})^2) - \sigma(2) &= 0 \\
\rightarrow (\sigma(\sqrt{2}))^2 - 2 &= 0
\end{align*}
$$

Because $g(x)$ has two roots $\pm\sqrt{2}$, thus $\sigma(\sqrt{2}) = \pm\sqrt{2}$. That means the set of automorphisms of $\mathbb{Q}(\sqrt{2})$, denote as $AUT(\mathbb{Q}(\sqrt{2}))$, consists of two elements

$$
\begin{align*}
\sigma_0(a + b\sqrt{2}) &= a + b\sqrt{2} \\
\sigma_1(a + b\sqrt{2}) &= a - b\sqrt{2}
\end{align*}
$$

$\sigma_0$ is the identity automorphism, because $\sigma_0(\alpha) = \alpha$ for all $\alpha \in \mathbb{Q}(\sqrt{2})$. Thus $AUT(\mathbb{Q}(\sqrt{2}))$ is isomorphic to $\mathbb{Z}/2\mathbb{Z}$.

Example 2: find the minimal polynomial with integer coefficients that takes $\alpha_0 = 1 + \sqrt{2}$ as a root. As we've identified that $AUT(\mathbb{Q}(\sqrt{2})) = \{\sigma_0, \sigma_1\}$ and a root, we can immediately compute the other root which is $\alpha_1 = \sigma_1(1 + \sqrt{2}) = 1 - \sqrt{2}$, so $h(x) = x^2 - (\alpha_0 + \alpha_1)x + \alpha_0\alpha_1 = x^2 - 2x + 2$ is the answer.

I hope that the last example has demonstrated somewhat the beauty of Galois theory. Our original problem can be solved in the same way. Let me restate it here so that you don't have to scroll up:

Exercise: find the minimal polynomial $f(x) \in \mathbb{Q}[x]$ (thus, its coefficients are rational) that takes $\epsilon= 1 + \sqrt[3]{2} + \sqrt[3]{4}$ as a root.

Let $\mathbb{K}$ be the splitting field of $f(x)$. $\mathbb{K}$ is a finite extension of $\mathbb{Q}$ by adjoining roots of $f(x)$. In other to find the other roots, we need to know $AUT(\mathbb{K})$, but in order to compute $AUT(\mathbb{K})$, we need to know $\mathbb{K}$. How do we obtain $\mathbb{K}$ without knowing roots of $f(x)$?

Galois showed that because $\epsilon \in \mathbb{Q}(\sqrt[3]{2})$, $f(x)$ will split completely in the splitting field $\mathbb{E}$ of $r(x) = x^3 - 2$. In other words, $\mathbb{K}$ is a subfield of $\mathbb{E}$.

Theorem: all irreducible $p(x) \in \mathbb{Q}[x]$ having a root in $\mathbb{E}$ has all its roots in $\mathbb{E}$.

Let $\alpha$ be a root of $f(x)$ in $\mathbb{E}$. Consider the series $\alpha_0, \alpha_1,...,\alpha_n$ in which $\alpha_i = \sigma_i(\alpha)$ and $AUT(\mathbb{E}) = \{\sigma_i\}$. $\alpha_i$ are the result of the group of automorphisms of E acting on $\alpha$. Let $A = \{\alpha_0, \alpha_1,...,\alpha_r\}$ be the set of the unique elements amongst $\alpha_i$. We can prove that

$$
\begin{equation*}
p(x) = (x - \alpha_0)(x - \alpha_1)...(x - \alpha_r)
\end{equation*}
$$

This is the result that we use in Example 2. This trick is so important that I'm going to repeat it one more time: for a polynomial, if we know one of its roots and the group of automorphisms of its splitting field, we can compute all other roots. We already know $\epsilon$, we just need to obtain $AUT(\mathbb{E})$.

Note that $\mathbb{E} \neq \mathbb{Q}(\sqrt[3]{2})$. In fact $\mathbb{Q}(\sqrt[3]{2})$ is a proper subset of $\mathbb{E}$. According to the fundamental theorem of algebra $r(x)$ has 3 roots in the field of complex numbers, but $\mathbb{Q}(\sqrt[3]{2})$ contains only one real root, which is $\sqrt[3]{2}$, but not the other two complex roots:

$$
\begin{align*}
\zeta_0 &= \sqrt[3]{2}\mu \\
\zeta_1 &= \sqrt[3]{2}\mu^2
\end{align*}
$$

in which $\mu = \frac{-1 + 3i}{2}$ is the 3rd primitive root of unity. Because $\zeta_0$ and $\sqrt[3]{2}$ are in $\mathbb{E}$, its quotient which is $\mu$ is also in $\mathbb{E}$. Thus, $\mathbb{E} = \mathbb{Q}(\sqrt[3]{2}, \mu)$, in other words $\mathbb{E}$ is an extension of $\mathbb{Q}$ by adjoining $\sqrt[3]{2}$ và $\mu$.

Now we can compute $AUT(\mathbb{E})$, as we did in Example 1. With that we can compute the other roots of $f(x)$ by computing the result of the automorphisms acting on $\epsilon$. But there is a shortcut!

Observe that because $\epsilon \in \mathbb{Q}(\sqrt[3]{2})$, $f(x)$ is at most degree 3. $f(x)$ can't have degree 1 because $\epsilon \not\in \mathbb{Q}$. It can't have degree 2 because its degree must divide 3. Thus, $f(x)$ has degree 3 and, thus has 3 roots.

Because $\epsilon= 1 + \sqrt[3]{2} + \sqrt[3]{4}$, the results of $AUT(\mathbb{E})$ acting on $\epsilon$ are completely determined by the actions of the automorphisms on $\sqrt[3]{2}$. But $AUT(\mathbb{E})$ acting on $\sqrt[3]{2}$ permutes the roots of $x^3 - 2 = 0$, thus we can immediately compute the other two roots of $f(x)$:

$$
\begin{align*}
\delta&= 1 + \zeta_0 + \zeta_0^2 \\
\omega &= 1 + \zeta_1 + \zeta_1^2
\end{align*}
$$

Using the facts that $\mu^3 = 1$, and $\mu$ and $\mu^2$ are roots of $\phi(x) = x^2 + x + 1$, we can see that $f(x) = x^3 - 3x^2 - 3x - 1$. Wolfram Alpha seems to agree with us, fortunately!

Based on these ideas and with some calculations one can come up with the scary-looking formulas of general solutions of polynomials of degree three and four, and also prove that there are no general solutions for polynomials of degree five or higher. If you want to learn how to do that yourself, I recommend reading A First Course In Abstract Algebra, the book that I bought for one buck. I also found Abstract Algebra of Dummit and Foote easy to understand.

---

Last September marked four years the day I joined Google. I thought I was hot shit when I started, but the longer I work there the more I see how crappy was I. I've probably learned more in the past four years than all previous combined. In my weirdest dreams, I wouldn't think that one day I'd understand Galois theory, let alone using it to do something useful, like crypto!

Happy times.

Wednesday, November 4, 2015

Đường đến Galois

Hai tháng nay tôi đi vòng vòng chơi ở Châu Âu, vác theo mấy cuốn sách, định bụng sáng đi chơi, tối về đọc toán cho sang. Rốt cuộc toàn chơi, chẳng đọc được mấy chỉ có lâu lâu mở ra đọc được vài trang để cho dễ ngủ. Nghĩ bụng đọc kiểu này chắc chẳng thu được gì, ai dè lại hiểu được lý thuyết Galois. Có lẽ nhờ ăn đồ Pháp?

Tôi đọc về lý thuyết Galois mấy tháng rồi, nhưng chỉ hiểu lờ mờ. Tôi chỉ nhận ra sức mạnh của Galois cho đến khi làm bài tập đơn giản này:

Bài tập: tìm đa thức nhỏ nhất (minimal polynomial) $f(x)$ thuộc $\mathbb{Q}[x]$ (tức có các hệ số hữu tỉ) nhận $\epsilon= 1 + \sqrt[3]{2} + \sqrt[3]{4}$ là nghiệm.

Có một cách giải sơ cấp là dự đoán $f(x)$ sẽ có bậc 3 ở dạng $f(x) = x^3 + ax^2 + bx + c$, thế $\epsilon$ vô, khai triển rồi quy về hệ phương trình theo $a$, $b$ và $c$. Mới đầu tôi làm cũng vậy, nhưng sau đó thấy "cơ bắp" quá nên dẹp sang một bên. Vậy áp dụng Galois thế nào?

Galois chỉ ra rằng chỉ cần biết một nghiệm của $f(x)$ là có thể tính được các nghiệm còn lại. Gọi hai nghiệm còn lại của $f(x)$ là $\delta$ và $\omega$, lúc đó

\[
\begin{equation}
f(x) = (x - \epsilon)(x - \delta)(x - \omega)
\end{equation}
\label{eq2:f(x)}
\]

và ta có thể tính được hệ số như sau

$$
\begin{align*}
- a &=  \epsilon+ \delta+ \omega \\
b &=  \epsilon\delta+ \epsilon\omega + \omega\delta\\
-c &= \epsilon\delta\omega
\end{align*}
$$

Nếu muốn phân tích $f(x)$ thành các thừa số như $\eqref{eq2:f(x)}$, ta phải mở rộng $\mathbb{Q}$, vì rõ ràng $\epsilon \notin \mathbb{Q}$. Nếu như bạn chưa quen với khái niệm trường mở rộng (field extension), có thể xem ví dụ sau đây.

Ví dụ 1: Xét đa thức $g(x) = x^2 - 2$. Nhận xét $g(x)$ là một đa thức bất khả quy (irreducible polynomial) trên $\mathbb{Q}$. Nói cách khác, không thể phân tích $g(x)$ thành tích của các đa thức có hệ số hữu tỉ, tức thuộc $\mathbb{Q}[x]$, có bậc nhỏ hơn 2. Nhưng nếu ta mở rộng $\mathbb{Q}$ bằng cách cho thêm vào phần tử $\sqrt{2}$, ký hiệu tập mở rộng là $\mathbb{Q}(\sqrt{2})$, thì $g(x)$ không còn là bất khả quy nữa, mà có thể phân tích thành

$$
\begin{equation*}
g(x) = (x - \sqrt{2})(x + \sqrt{2})
\end{equation*}
$$

$\mathbb{Q}$ là một trường và có thể chứng minh được

$$
\mathbb{Q}(\sqrt{2}) = \{a + b\sqrt{2}\ |\ a,\ b \in \mathbb{Q}\}
$$

cũng là một trường. Có thể thấy $\mathbb{Q}(\sqrt{2})$ là một không gian vector trên $\mathbb{Q}$ có chiều bằng 2. Vì $\mathbb{Q} \subset \mathbb{Q}(\sqrt{2})$, ta nói $\mathbb{Q}(\sqrt{2})$ là một trường mở rộng bậc 2 của $\mathbb{Q}$. Ngoài ra, do $-\sqrt{2} \in \mathbb{Q}(\sqrt{2})$ ta thấy $\mathbb{Q}(\sqrt{2})$ chứa hết tất cả các nghiệm của $g(x)$ và được gọi là trường phân rã (splitting field) của $g(x)$. Gọi là trường phân rã vì $g(x)$ phân rã hoàn toàn thành các đa thức tuyến tính (bậc 1) trên $\mathbb{Q}(\sqrt{2})$. Nói cách khác, trường phân rã của một đa thức chứa tất cả các nghiệm của đa thức đó.

Galois phát hiện ra rằng tác động của nhóm các tự đẳng cấu của trường phân rã (group of automorphisms of the splitting field) của một đa thức lên các nghiệm của đa thức đó tạo thành hoán vị của các nghiệm. Gọi $G = \{\sigma_0, \sigma_1,...,\sigma_n\}$, trong đó $\sigma_i$ là một tự đẳng cấu của trường phân rã của $f(x)$. Nếu xác định được $G$ và một nghiệm $\alpha$ của $f(x)$, chúng ta có thể xác định được các nghiệm còn lại bằng cách tính $\sigma_i(\alpha)$.

Quay trở lại ví dụ 1. Như nhận xét ở trên, $\mathbb{Q}(\sqrt{2})$ là trường phân rã của $g(x)$ trên $\mathbb{Q}$. Xét $\sigma$ là một tự đẳng cấu của $\mathbb{Q}(\sqrt{2})$. Theo định nghĩa, $\sigma$ là một song ánh $\sigma:\ \mathbb{Q}(\sqrt{2}) \rightarrow \mathbb{Q}(\sqrt{2})$ thỏa mãn

$$
\begin{align*}
&\sigma(\alpha + \beta) = \sigma(\alpha) + \sigma(\beta) \\
&\sigma(\alpha\beta) = \sigma(\alpha)\sigma(\beta)
\end{align*}
$$

với mọi $\alpha,\ \beta \in \mathbb{Q}(\sqrt{2})$.

Ta có thể chứng minh được $\sigma(0) = 0$ và $\sigma(1) = 1$ và do đó $\sigma(a) = a$ với mọi $a \in \mathbb{Q}$. Ta nói $\sigma$ bảo toàn $\mathbb{Q}$. Xét $\sigma(a + b\sqrt{2})$, trong đó $a,\ b \in \mathbb{Q}$

$$
\begin{align*}
\sigma(a + b\sqrt{2}) &= \sigma(a) + \sigma(b\sqrt{2}) \\
&= a + \sigma(b)\sigma(\sqrt{2}) \\
&= a + b\sigma(\sqrt{2})
\end{align*}
$$

Do đó tác động của $\sigma$ lên $\mathbb{Q}(\sqrt{2})$ phụ thuộc hoàn toàn vào tác động của $\sigma$ lên $\sqrt{2}$.

Nhận xét: $\sigma(\sqrt{2})$ là nghiệm của $g(x)$. Thật vậy, ta có $g(\sqrt{2}) = 0$, áp dụng $\sigma$ vào hai vế của biểu thức

$$
\begin{align*}
\sigma(g(\sqrt{2})) &= \sigma(0) \\
\rightarrow \sigma(\sqrt{2})^2 - 2) &= 0 \\
\rightarrow \sigma(\sqrt{2})^2) - \sigma(2) &= 0 \\
\rightarrow (\sigma(\sqrt{2}))^2 - 2 &= 0
\end{align*}
$$

Trên $\mathbb{Q}(\sqrt{2})$ $g(x)$ có hai nghiệm là $\pm\sqrt{2}$, suy ra $\sigma(\sqrt{2}) = \pm\sqrt{2}$. Như vậy tập các tự đẳng cấu trên $\mathbb{Q}(\sqrt{2})$, ký hiệu $AUT(\mathbb{Q(\sqrt{2})})$, bao gồm hai phần tử

$$
\begin{align*}
\sigma_0(a + b\sqrt{2}) &= a + b\sqrt{2} \\
\sigma_1(a + b\sqrt{2}) &= a - b\sqrt{2}
\end{align*}
$$

$\sigma_0$ là đẳng cấu đơn vị với $\sigma_0(\alpha) = \alpha$ với mọi $\alpha \in \mathbb{Q}(\sqrt{2})$.

Ví dụ 2: tìm đa thức nhỏ nhất với hệ số nguyên nhận $\alpha_0 = 1 + \sqrt{2}$ là nghiệm. Chúng ta đã xác định được $AUT(\mathbb{Q(\sqrt{2})}) = \{\sigma_0, \sigma_1\}$ và một nghiệm, nên ngay lập tức chúng ta có thể xác định được nghiệm còn lại chính là $\alpha_1 = \sigma_1(1 + \sqrt{2}) = 1 - \sqrt{2}$, do đó đa thức cần tìm là $h(x) = x^2 - (\alpha_0 + \alpha_1)x + \alpha_0\alpha_1 = x^2 - 2x + 2$.

Hi vọng ví dụ vừa rồi đã cho thấy sức mạnh của Galois và lý giải được phần nào tại sao chúng ta phải đi lòng vòng nãy giờ =). Bài toán mà chúng ta cần giải cũng có thể giải được bằng phương pháp tương tự.

Bài tập: tìm đa thức nhỏ nhất (minimal polynomial) $f(x)$ thuộc $\mathbb{Q}[x]$ (tức có các hệ số hữu tỉ) nhận $\epsilon= 1 + \sqrt[3]{2} + \sqrt[3]{4}$ là nghiệm.

Gọi trường phân rã của $f(x)$ là $\mathbb{K}$. Ta thấy $\mathbb{K}$ là một mở rộng hữu hạn của $\mathbb{Q}$ bằng cách thêm vào các nghiệm của $f(x)$. Để tìm các nghiệm còn lại, chúng ta cần phải xác định $AUT(\mathbb{K})$. Để tính $AUT(\mathbb{K})$, chúng ta cần biết $\mathbb{K}$. Nhưng làm thế nào để xác định $\mathbb{K}$ khi không biết nghiệm của $f(x)$?

Galois chỉ ra rằng do $\epsilon \in \mathbb{Q}(\sqrt[3]{2})$, $f(x)$ sẽ phân rã hoàn toàn trên trường phần rã $\mathbb{E}$ của $r(x) = x^3 - 2$. Nói cách khác, $\mathbb{K}$ là tập con của $\mathbb{E}$.

Định lý: mọi đa thức bất khả quy $p(x) \in \mathbb{Q}[x]$ có một nghiệm thuộc $\mathbb{E}$ sẽ phân rã hoàn toàn trên $\mathbb{E}$. Nói cách khác, mọi nghiệm của một đa thức bất khả quy sẽ thuộc $\mathbb{E}$ nếu một nghiệm của nó thuộc $\mathbb{E}$.

Gọi $\alpha$ là nghiệm thuộc $\mathbb{E}$ của $f(x)$. Xét dãy $\alpha_0, \alpha_1,...,\alpha_n$ trong đó $\alpha_i = \sigma_i(\alpha)$ và $AUT(\mathbb{E}) = \{\sigma_i\}$. Nói cách khác, dãy $\alpha_i$ là kết quả tác động của nhóm các tự đẳng cấu của E lên $\alpha$. Sắp xếp lại thứ tự nếu cần, đặt $A = \{\alpha_0, \alpha_1,...,\alpha_r\}$ là tập các phần tử độc nhất của dãy $\alpha_i$. Ta có thể chứng minh rằng

$$
\begin{equation}
p(x) = (x - \alpha_0)(x - \alpha_1)...(x - \alpha_r)
\end{equation}
$$

Đây chính là kết quả mà chúng ta sử dụng ở ví dụ 2. Nhắc lại, chỉ cần xác định được một nghiệm và tập các đẳng cấu, ta có thể xác định được tất cả các nghiệm còn lại. Ta đã có nghiệm cho trước là $\epsilon$, nhiệm vụ bây giờ là xác định $AUT(\mathbb{E})$.

Lưu ý $\mathbb{E} \neq \mathbb{Q}(\sqrt[3]{2})$, thực tế $\mathbb{Q}(\sqrt[3]{2})$ chỉ là một tập con của $\mathbb{E}$, vì theo định lý cơ bản của đại số, $r(x)$ phải có 3 nghiệm trên trường số phức, nhưng $\mathbb{Q}(\sqrt[3]{2})$ chỉ chứa một nghiệm thực duy nhất, tức $\sqrt[3]{2}$, mà không chứa hai nghiệm phức còn lại. Ngoài nghiệm thực $\sqrt[3]{2}$, $r(x)$ còn có hai nghiệm phức

$$
\begin{align*}
\zeta_0 &= \sqrt[3]{2}\mu \\
\zeta_1 &= \sqrt[3]{2}\mu^2
\end{align*}
$$

Trong đó $\mu = \frac{-1 + 3i}{2}$ và được gọi là căn bậc ba nguyên sơ của đơn vị (3rd primitive root of unity). Do cả $\zeta_0$ và $\sqrt[3]{2}$ đều thuộc $\mathbb{E}$, thương của chúng, chính là $\mu$, cũng thuộc tập hợp này. Từ đó suy ra $\mathbb{E} = \mathbb{Q}(\sqrt[3]{2}, \mu)$, tức là $\mathbb{E}$ là mở rộng của $\mathbb{Q}$ bằng cách thêm vào hai phần tử $\sqrt[3]{2}$ và $\mu$.

Tới đây chúng ta có thể tính được $AUT(\mathbb{E})$ như đã làm ở ví dụ 1. Sau khi đã xác định được các tự đẳng cấu, ta có thể tính được hai nghiệm còn lại của $f(x)$ bằng cách tính tác động của các tự đẳng cấu lên $\epsilon$. Nhưng có một cách ngắn hơn!

Nhận xét: $\epsilon \in \mathbb{Q}(\sqrt[3]{2})$, do đó $f(x)$ tối đa sẽ có bậc là 3. Bậc của $f(x)$ không thể là 1 vì $\epsilon \not\in \mathbb{Q}$ và không thể là 2 vì bậc của $f(x)$ phải chia hết cho 3. Do đó $f(x)$ sẽ có 3 nghiệm.

Vì $\epsilon= 1 + \sqrt[3]{2} + \sqrt[3]{4}$, nên tác động của các tự đẳng cấu của $\mathbb{E}$ lên nó được xác định hoàn toàn bởi tác động của chúng lên $\sqrt[3]{2}$. Nhưng tác động của  $AUT(\mathbb{E})$ lên $\sqrt[3]{2}$ chính là tác động hoán vị lên các nghiệm của $r(x)$, do đó có thể suy ra được ngay hai nghiệm còn lại của $f(x)$ là

$$
\begin{align*}
\delta&= 1 + \zeta_0 + \zeta_0^2 \\
\omega &= 1 + \zeta_1 + \zeta_1^2
\end{align*}
$$

Lợi dụng quan sát $\mu$ và $\mu^2$ là hai nghiệm của đa thức $\phi(x) = x^2 + x + 1$ và $\mu^3 = 1$, sau một hồi tính toán tè le ta có thể tính được $f(x) = x^3 - 3x^2 - 3x - 1$. Rất may Wolfram Alpha đồng ý với kết quả này, phẻ quá!

Trên đây chỉ là phát họa cho sức mạnh của Galois. Ai muốn tìm hiểu thêm có thể tìm đọc bài viết "Nghiệm của phương trình một ẩn số" của giáo sư Ngô Bảo Châu đăng trên tập chí Epsilon số 2. Ngoài ra tôi thấy cuốn Abstract Algebra của Dummit và Foote giảng giải rất dễ hiểu. Cuốn A First Course In Abstract Algebra cũng đáng đọc.

---

Tháng 9 vừa rồi là tôi làm cho Google được bốn năm. Hồi tôi mới vô đây, tôi tưởng tôi ngon lắm, càng làm càng mới thấy mình dở ẹc. Bốn năm vừa rồi có lẽ tôi học được nhiều hơn cả bao nhiêu năm trước đó cộng lại. Lý thuyết Galois là một trong số đó. Vài năm trước đây ai nói với tôi là tôi sẽ hiểu được tại sao không thể biểu diễn nghiệm của phương trình bậc 5 tổng quát bằng căn thức chắc tôi sẽ không tin đâu, mặc dù cũng tò mò lắm.

Mà tại sao nghề của tôi lại cần học Galois? Vì mật mã hiện đại toàn là đại số. Hi vọng sẽ có dịp quay trở lại chủ đề này.

Ổi thơm (pineapple guava)


Lần đầu tiên ăn được trái ổi thơm. Ngon ve sầu! Vị ngọt thanh, có chút xíu chua, pha lẫn mùi của ổi xá lị, bơ và thơm. Ăn cứ như là chè cocktail.

Trong một diễn biến khác, năm nay táo mất mùa nhưng lại được mùa hồng giòn. Trái chín cây, trái nào ăn cũng tươi, giòn, vị không quá ngọt như mua ngoài chợ. Cây lùn xủn, mà cũng được khoảng 200 trái như vầy: