Tìm nghịch đảo theo phép đồng dư

Mình thật có duyên với cái thuật toán Euclide mở rộng để tìm nghịch đảo theo phép đồng dư và giải phương trình Diophantus tuyến tính này. Cứ mỗi lần trước khi thi cử là lại vác quyển Số học ra để gạo nó, mà gạo từ năm lớp 8 đến 12 vẫn không thuộc. Và bây giờ đến năm thứ tư vẫn lại phải gạo nó T_T.

Vào chủ đề chính. Tình hình là vừa mới kiếm được cách tìm nghịch đảo theo phép đồng dư để chuẩn bị thi mật mã. Mà môn này mình thì cúp, còn hai đồng minh chiến lược thì ngủ, và khả năng là có một số anh em khác vừa ngủ vừa cúp, nên tranh thủ post lại cách giải lên đây.

Cách giải này tìm thấy trong chính quyển sách giáo khoa Cryptography and Network Security Principles and Practices 🙂 (đừng đọc Wiki). Ta giả vờ nghiên cứu thuật toán đã.

Tìm nghịch đảo của b (tức là b-1) modulo m. Bắt buộc đưa về 0 < b < m.

EXTENDED EUCLID(m, b)
1. (A1, A2, A3) (1, 0, m); (B1, B2, B3) (0, 1, b)
2. if B3 = 0 return A3 = gcd(m, b); no inverse
3. if B3 = 1 return B3 = gcd(m, b); B2 = b1 mod m
4. Q = thương của A3 / B3.
5. (T1, T2, T3) <- (A1 – QB1, A2 – QB2, A3 – QB3)
6. (A1, A2, A3) <- (B1, B2, B3)
7. (B1, B2, B3) <- (T1, T2, T3)
8. goto 2

Ta luôn có mT1 + bT2 = T3 mA1 + bA2 = A3 mB1 + bB2 = B3.

Tất nhiên sinh viên BK làm gì có thời gian mà đọc cái này. Ta ví dụ luôn với b = 550, m = 1759 như sách giáo khoa, nhưng mình sửa lại cách kẻ bảng chút ít cho nó nhanh hơn :”>.

Hàng đầu là 1, 0, m. Hàng hai là 0, 1, b. Chú ý hàng đầu là m. Và nhắc lại, bắt buộc đưa về 0 < b < m.

Q 1 0 1759
  0 1 550

Lấy hàng trên cột cuối chi hàng dưới cột cuối, tức là 1759 / 550. Thương là Q.

Q 1 0 1759
3 0 1 550

Lấy Q nhân với hàng dưới (tức là 3 nhân với các số cùng hàng), rồi lấy hàng trên trừ đi kết quả, cột theo cột, được hàng tiếp.

Q 1 0 1759
3 0 1 550
  1 -3 109

Và lại tính Q = 550 / 109. Làm thế cho đến khi số ở cột cuối là 1.

Q 1 0 1759
3 0 1 550
5 1 -3 109
21 -5 16 5
1 106 -339 4
  -111 355 1

Và số cạnh số 1 đó (số 355) là nghịch đảo của 550 modulo 1759, hay 355 * 550 = 1 (mod 1759).

Tất nhiên nếu bạn chưa gặp số 1 mà đã gặp 0 rồi thì tức là không có nghịch đảo.

Q 1 0 15
1 0 1 12
4 1 -1 3
  -4 5 0

Khi đó số trên số 0 là ước chung lớn nhất (tức là 3), và hai số cùng hàng với 3 là 1 và –1 có tính chất 15 * 1 + 12 * (-1) = 3.

Trường hợp 1759 mà làm tiếp thì cũng sẽ gặp 0, có điều việc làm tiếp là không cần thiết. Dĩ nhiên 1759 * (-111) + 550 * 355 = 1.

Word 2007 – bullet, numbering, multilevel list

(Cập nhật một cách sửa lỗi ở dưới)

Khỏi cần nói thì ai cũng biết bullet, numbering, và multilevel list (gọi chung là list) là một trong những thứ khá khó chịu trong Word. Hôm nay chỉ nói list dạng bullet.

Di chuyển trong list

Cái này quá đơn giản. Muốn item trở thành cấp con, dùng Tab. Muốn item trở thành cấp cao hơn, khi item trống, ấn Enter (xem hình), đừng dùng nút Decrease. Muốn đưa một item đã có lên cấp cao hơn, dùng Shift + Tab. Cũng dùng Enter để tắt chế độ list, đừng dùng nút Bullets (xem hình).

image

Enter liên tục:

image image image

Tạo list

Tạo list bằng nút Bullets. Với list có sẵn, tạo item mới bằng cách Enter (xuống dòng) từ item cũ, đừng dùng Bullets. Chỉ dùng nút Bullets khi tạo list mới.

Tất nhiên, tạo list kiểu này sẽ gây ra một số vấn đề rắc rối. Đó là khi sau này bạn muốn sửa lại bullet thành hình khác, hoặc muốn tăng giảm khoảng cách của bullet với chữ, v.v. Điều này hiếm khi cần thiết, tuy nhiên nếu bạn quan tâm, xin đọc tiếp.

Tạo list (kiểu 2)

Để có thể thay đổi định dạng list dễ dàng trong tương lai, chúng ta sẽ tạo một list style. Mặc định Word không có một list style nào hết (hơi dở).

Bước 1:

image

Bước 2: Mục Name đặt tên cho style mới, sau đó bấm vào nút Format chọn Numbering để đổi bullet.

image

Bước 3: Nếu không ưng ý với bullet có sẵn, chọn New Bullet.

image

Nên chọn bullet từ font Symbol:

image

Sau đó, OK, OK và OK. Bây giờ chọn style mới tạo (My style) và thử thôi:

image

Vì là LaTeX fanboy nên mình sẽ bắt chước bullet trong LaTeX (tròn, gạch, hoa thị). Có vẻ đẹp hơn mặc định của Word :-).

image

Bây giờ giả sử bạn muốn sửa. Ấn chuột phải vào style của bạn và chọn Modify:

image

Cửa sổ này y hệt ở bước 2 thôi, trừ cái tên.

image

Sau khi sửa style, tất cả các list sẽ tự động thay đổi theo:

image

Tạo list kiểu này thật đơn giản và tiện dụng. Cái này không thấy sách ghi, phải đào bới trong mục Help và thử nghiệm rất vất vả mới thành công :P.

(Cập nhật) Dưới đây là một cách sửa cho vấn đề của bạn trang ở dưới, thao tác theo hình chụp:

1

2

4

5

Unicode tổ hợp hay dựng sẵn trong Word 2007

Có lẽ bạn chỉ cần Unicode tổ hợp khi bạn muốn xài style có kiểu chữ dạng ? (không biết tên, LaTeX gọi là smallcap, dạng giống như chữ “Dựng sẵn” và “Tổ hợp” trong hình dưới).

image

Word tạo ra chữ smallcap bằng cách thu các chữ in hoa nhỏ lại một chút. Ví dụ, chữ “Dựng sẵn” trong style thường là “Dựng sẵn”, khi bạn (theo ý thích) chuyển sang smallcap, Word sẽ lấy chữ viết hoa tương ứng (ví dụ, dạng viết hoa tương ứng của “ự” là “Ự”) thu nhỏ lại, nhưng vì Word không biết chữ “ự” (gồm chữ “ư” và dấu nặng) viết hoa sao, cho nên nó vẫn để “ự” thay vì “Ự”. Với Unicode tổ hợp, Word sẽ viết hoa chữ cái (“ư” thành “Ư”), rồi ghép thêm dấu nặng vào, cho nên smallcap cho tổ hợp chạy tốt.

Nếu bạn thấy rắc rối, thì nên dùng Unicode dựng sẵn và tránh xa các template có kiểu chữ smallcap ra. Hơn nữa, các chương trình gõ tiếng Việt thường mặc định dùng Unicode dựng sẵn, nếu bạn muốn dùng Unicode tổ hợp thì phải lưu ý cả những người cùng soạn thảo.

Vài lưu ý khi soạn thảo với Word 2007

Tình hình là thấy có người google “trích nguồn trong word” và nhảy vô trúng bài này. Thật vui khi bài viết của mình hữu ích cho ai đó :D. Đã vậy thì tiện đây sẽ làm luôn một loạt bài về Word 2007, đằng nào thì cũng phải luyện để làm đồ án cho ngon lành. Nội dung là các kinh nghiệm đơn giản để giúp soạn thảo bằng Word vừa nhanh vừa đẹp (đẹp về cấu trúc trước, thẩm mĩ sau). Chú ý ai đó nếu đọc thì phải nhớ đây chỉ là “kinh nghiệm”, tức là có tốt, có xấu, và có thể không cho cùng kết quả với bạn. Để cho an toàn thì các bạn nên có chút gì đó phòng thân, như “Micrsoft Word 2007 bible” và “Special edition using Microsoft Office Word 2007” (chữ “Special edition” đi kèm tên sách chứ không phải mình ghi thừa). Và tất nhiên, không thể bỏ qua chức năng Help của Word.

Trước hết, nếu muốn tạo một văn bản xịn trong Word thì các bạn phải quên mục Font trong tab Home đi đã. Chính xác hơn là đừng có ngứa tay tô đậm, làm nghiêng, gạch chân màu mè hoa lá gì đó. Có hai lí do cho điều này (mà ai đọc về HTML rồi thì cũng hiểu ngay là tại sao). Thứ nhất, định dạng của mình chắc chắn là xấu hơn định dạng có sẵn. Thứ hai, là nếu sau này có hối hận và muốn sửa thì cũng chả sửa được, trừ khi siêng năng soát lại toàn bộ văn bản. Nếu các bạn muốn nhấn mạnh một đoạn văn bản (thường sẽ là in nghiêng), hãy định nghĩa một style “nhấn mạnh” và gán style này cho đoạn văn bản đó. Nếu sau này có đổi ý muốn nhấn mạnh văn bản bằng chứ in đậm thì chỉ cần định nghĩa style là xong. (Nói thêm là Word cũng có sẵn kiểu “nhấn mạnh” rồi, đó là “Emphasis”.)

Vậy, điều đầu tiên là chỉ dùng cái bảng dưới đây để định dạng thôi, và chỉ dùng đến mục Font để định nghĩa style (và tốt hơn hết không nên làm việc này lúc đầu, tập trung vào nội dung đã).

image

Tuân thủ điều này 100%, và việc đổi cách trình bày văn bản sẽ chỉ cần một hai cú chuột (để chọn style phù hợp). Toàn style làm sẵn, nên rất đẹp:

Untitled1

Untitled2

Điều cần làm thứ hai là vào mục Show/Hide trong tab View và bật Document Map lên. Nó sẽ cho bạn một bảng mục lục tài liệu bên tay trái để nhảy qua nhảy lại trong văn bản rất là tiện lợi. (Nhìn hình ở trên.)

Tiếp theo xuống góc dưới bên phải và chọn Web Layout (biểu tượng quả cầu xanh). Như thế bạn sẽ không phải bận tâm về header, footer, qua trang, lề trái phải, v.v. Như đã nói, tập trung vào nội dung đã. Giờ chỉ còn một băng giấy dài với độ rộng bằng bề ngang cửa sổ thôi. (Cũng có trong hình ở trên.)

Bây giờ chúng ta có thể bắt tay vào soạn thảo được rồi.

Cách thêm nguồn trích dẫn trong Word 2007

Mới tìm ra một bộ style trích nguồn cho Word 2007 cực ngon nên phải chia sẻ ngay cho anh em. Với cái này thì có thể để LaTeX yên nghỉ được rồi.

Xem hướng dẫn cài đặt và tải xuống ở đây (chỉ nên tải BibWord styles thôi). Trong này có IEEE là style thường thấy trong các paper.

—————-

Phần này dành cho ai chưa từng xài tính năng citation trong Word 2007. Trước hết xem hình đã.

image

Nếu gõ cái đoạn vừa rồi bằng tay thì vừa xấu vừa mất công, mà mỗi lần trích dẫn phải tra lại, còn xóa hoặc chèn thêm thì chắc là không tưởng (ví dụ sửa [4] thành [3] đồng nghĩa với việc phải lục lại toàn bộ tài liệu).

Thêm nguồn tham khảo

Vào References > Manage Sources (trong cụm Citations & Bibliography). Nó ra cái bảng này:

image

Muốn thêm thì chọn New. Dễ tới mức không cần hướng dẫn thêm. Có mấy “Type of Source” hay gặp là “Book”, “Web site”, “Report”, “Conference Proceedings”, v.v

Có một chú ý nhỏ là để nhập tên tác giả nên dùng chức năng “Edit” để nhập riêng tên, họ, chữ lót. Chức năng này cũng cần thiết khi phải nhập nhiều tác giả.

Chèn trích dẫn

image

Với Style IEEE, có một chú ý nhỏ. Nếu trích dẫn cùng lúc nhiều nguồn, thì thay vì để “[1][2]” thì nên để là “[1, 2]” bằng cách chèn “[1]” rồi để con trỏ vào trong “[1]” chèn “[2]”. Nó sẽ tự chuyển thành “[1, 2]”.

Tạo danh sách

image