XOR

 (chiark.greenend.org.uk)
1 คะแนน โดย GN⁺ 2025-02-19 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • XOR คือการดำเนินการที่ให้ค่าเป็น 1 เมื่อบิตสองบิตแตกต่างกัน และสามารถทำความเข้าใจได้ว่าเชื่อมโยงแนวคิดของ OR แบบเอกสิทธิ์, การไม่เท่ากัน, การกลับค่าตามเงื่อนไข, และการบวก/ลบ mod 2 ไว้ในการทำงานเดียว
  • XOR แบบระดับบิตสำหรับจำนวนเต็มจะประมวลผลแต่ละหลักอย่างอิสระ ทำให้เห็น ความแตกต่างในแต่ละบิต และทำงานคล้ายการบวกเลขฐานสองแบบไม่มีการทด พร้อมคงสมบัติการสลับที่, การเปลี่ยนหมู่, เอกลักษณ์ 0, และอินเวอร์สของตัวเองไว้
  • ในงานเข้ารหัส มันถูกใช้เพื่อผสานข้อความปกติกับ keystream และในกราฟิกพิกเซลยุคก่อน ก็ใช้วิธีวาดภาพเดิมซ้ำเพื่อให้ลบออกได้ ช่วยลดภาระด้านหน่วยความจำและ CPU
  • สมบัติของ XOR ถูกนำไปใช้โดยตรงในงานคำนวณที่ สร้างความต่างแล้วหักล้างกลับได้ เช่น อัตลักษณ์ของ half adder, การสลับบิต, XOR swap สามครั้ง, และเงื่อนไขชนะของเกม Nim
  • มันเชื่อมโยงต่อไปถึง symmetric difference ของเซต, กลุ่มที่มีเลขชี้กำลัง 2, nim-sum, พีชคณิตเชิงเส้นและพหุนามบน GF(2) รวมถึงเทคนิคตรวจจับ/แก้ไขข้อผิดพลาดและการเข้ารหัสอย่าง Hamming code, CRC, AES, GCM และ Classic McEliece

ความหมายพื้นฐานของ XOR

  • XOR เป็น การดำเนินการแบบบูลีน ที่มีบิตอินพุตสองบิตและบิตเอาต์พุตหนึ่งบิต โดยตารางค่าความจริงคือ 00→0, 01→1, 10→1, 11→0
  • เมื่อมองเป็น “exclusive OR” มันจะให้ค่า 1 เมื่อมีเพียงอินพุตตัวใดตัวหนึ่งเท่านั้นที่เป็นจริง และถ้าทั้งคู่เป็นจริงจะได้ 0
  • เมื่อมองเป็น “not equals” จะได้ว่า a XOR b เท่ากับ a ≠ b จึงให้ค่า 1 เมื่อค่าบูลีนสองค่าต่างกัน
  • เมื่อมองเป็น การกลับค่าตามเงื่อนไข ถ้า a=0 จะคง b ไว้ตามเดิม และถ้า a=1 จะกลับค่าของ b
    • ด้วยเหตุผลเดียวกัน ยังตีความได้โดยให้ b เป็นอินพุตควบคุมและกลับค่าของ a
  • ในมุมมองของ parity มันบอกได้ว่าจำนวน 1 ในอินพุตเป็นจำนวนคี่หรือไม่
    • สำหรับสองบิต มันเท่ากับ a+b mod 2
    • และยังเท่ากับ a-b mod 2
    • เมื่อนำหลายค่ามา XOR กัน ก็จะบอกได้ว่าจำนวน 1 ในอินพุตทั้งหมดเป็นจำนวนคี่หรือคู่

สมบัติเชิงพีชคณิตของ XOR

  • XOR เป็นไปตาม กฎการสลับที่ และ กฎการเปลี่ยนหมู่
    • a XOR b = b XOR a
    • (a XOR b) XOR c = a XOR (b XOR c)
    • ในรายการ XOR ที่ยาว ลำดับและวิธีจัดกลุ่มไม่มีผลต่อผลลัพธ์
  • 0 เป็น เอกลักษณ์ ของ XOR
    • a XOR 0 = 0 XOR a = a
    • ในรายการ XOR ที่ยาว สามารถตัด 0 ออกได้
  • ทุกค่าคือ อินเวอร์สของตัวเอง
    • a XOR a = 0
    • ถ้าตัวแปรเดียวกันปรากฏสองครั้ง ก็สามารถตัดสองพจน์นั้นออกพร้อมกันได้
    • เช่นใน (a XOR b) XOR b = a เราสามารถ XOR พจน์ที่รู้ค่าอีกครั้งเพื่อกำจัดมันออกจากค่าที่ผสมอยู่แล้วได้

XOR แบบระดับบิตสำหรับจำนวนเต็ม

  • XOR แบบระดับบิตของจำนวนเต็มคือการนำจำนวนเต็มสองค่ามาเขียนเป็นเลขฐานสอง แล้ว XOR บิตแต่ละหลักอย่างอิสระ
  • สมบัติของ XOR สำหรับบิตเดี่ยวใช้กับจำนวนเต็มได้เช่นเดิม
    • a XOR b = b XOR a
    • (a XOR b) XOR c = a XOR (b XOR c)
    • a XOR 0 = a
    • a XOR a = 0
  • XOR แบบระดับบิตบอก ความแตกต่างของแต่ละบิต ระหว่างจำนวนเต็มสองค่า
    • ถ้า a=b จะได้ a XOR b = 0
    • ถ้า a≠b จะมีอย่างน้อยหนึ่งบิตที่ต่างกัน จึงได้ a XOR b ≠ 0
    • บิต 1 ในผลลัพธ์แสดงตำแหน่งที่อินพุตสองค่าต่างกัน
  • XOR แบบระดับบิตยังมองได้ว่าเป็น ตัวกลับค่าบิตตามเงื่อนไข
    • มันจะกลับบิตข้อมูลเฉพาะในตำแหน่งที่ค่าควบคุมมีบิตเป็น 1
    • ใน ASCII และ encoding ที่สืบทอดบางแบบ ตัวอักษรละตินพิมพ์ใหญ่กับพิมพ์เล็กต่างกันเพียงหนึ่งบิต จึงสามารถ XOR ค่าอักขระด้วย 32 เพื่อสลับตัวพิมพ์ได้
    • กฎนี้ใช้ไม่ได้กับอักขระ Unicode ทั้งหมด และมีอักขระจำนวนมากที่ไม่มีแนวคิดเรื่องตัวพิมพ์หรือไม่เป็นไปตามกฎนี้
  • XOR แบบระดับบิตเทียบได้กับ การบวกเลขฐานสองแบบไม่มีการทด
    • มันทำเพียงการบวก mod 2 ในแต่ละหลัก และไม่ส่งการทดไปยังหลักถัดไป

XOR ในงานเข้ารหัส

  • ในงานเข้ารหัส มักสร้าง keystream ที่มีความยาวเท่ากับข้อความปกติ แล้วนำไบต์หรือเวิร์ดของข้อความปกติมาผสานกับ keystream เพื่อสร้างข้อความเข้ารหัส
  • โดยทั่วไปขั้นตอนการผสานนี้ใช้ XOR
    • ฝั่งรับสามารถ XOR ด้วย keystream เดิมอีกครั้งเพื่อกู้คืนข้อความปกติเดิม
    • การที่ผู้ส่งและผู้รับใช้การดำเนินการเดียวกันก็สะดวกขึ้นเล็กน้อยด้วย
  • วิธีสร้าง keystream เองอาจซับซ้อนกว่านั้น
    • one-time pad ใช้ข้อมูลสุ่มจริงยาวเท่าข้อความทั้งหมดและไม่สามารถถอดรหัสได้ แต่แทบไม่สะดวกต่อการใช้งานส่วนใหญ่
    • โดยทั่วไปจะใช้ stream cipher หรือ block cipher ที่ทำงานใน counter mode เพื่อสร้าง keystream ตามความยาวที่ต้องการจากกุญแจขนาดเล็ก
  • วิธีนี้อาจให้ ความลับของข้อมูล ได้ถ้า keystream ดีพอ แต่ไม่ได้ให้ ความถูกต้องสมบูรณ์ของข้อมูล สำหรับตรวจจับการดัดแปลงข้อความ
    • การปกป้องความถูกต้องสมบูรณ์เป็นปัญหาอีกส่วนหนึ่ง
    • การละเลยเรื่องความถูกต้องสมบูรณ์เป็นความผิดพลาดที่พบบ่อยในการออกแบบระบบเข้ารหัสสำหรับผู้เริ่มต้น และยังทำให้เกิดผลลัพธ์ผิดพลาดในระบบเข้ารหัสที่ซับซ้อนกว่านั้นได้
  • ในฮาร์ดแวร์ XOR เรียบง่ายกว่าการบวก
    • การบวกต้องมีการแพร่การทดระหว่างบิต จึงใช้พื้นที่บนชิปและเวลามากกว่า
    • XOR ไม่มีการทด จึงมีต้นทุนต่ำกว่าในวงจรเฉพาะทาง

การวาดแบบ XOR และกราฟิกพิกเซล

  • คอมพิวเตอร์ตามบ้านในยุค 1980 มีจำนวนบิตต่อพิกเซลและ RAM จำกัด ทำให้เก็บภาพทั้งหน้าจอสองชุดได้ยาก
  • หากวาดวัตถุที่เคลื่อนที่ด้วย XOR ก็สามารถ กู้คืนหน้าจอเดิม ได้เพียงวาดวัตถุเดิมซ้ำอีกครั้ง
    • นำค่าพิกเซล S ของหน้าจอกับพิกเซล M ของวัตถุที่เคลื่อนที่มา XOR กันเพื่อสร้าง C และภายหลังก็นำ M เดิมมา XOR ซ้ำเพื่อกู้ S กลับคืน
  • ในหน้าจอที่พิกเซลหลายตัวถูก packed อยู่ในหนึ่งไบต์ หรือใช้โครงสร้างแบบ bit plane การผสมภาพด้วยการบวกทำได้ยาก
    • การบวกทั่วไปอาจทำให้การทดของพิกเซลหนึ่งล้นไปยังพิกเซลถัดไป
    • XOR ไม่มีการทดเลย จึงไม่เกิดปัญหานี้
  • ถ้าวาดเส้นด้วย XOR พิกเซลที่เส้นสองเส้นตัดกันจะถูกกลับค่าสองครั้งและกลับไปเป็นสีพื้นหลัง ทำให้ดูเหมือนมีตำหนิเล็ก ๆ
    • ตำหนินี้ถูกยอมรับว่าเป็นข้อแลกเปลี่ยนเพื่อให้ลบเส้นหนึ่งได้โดยไม่ทำลายอีกเส้น
  • การวาดแบบ XOR ยังเหมาะกับแอนิเมชันแบบง่าย
    • เพียงวาดเส้นใหม่หนึ่งเส้น และวาดเส้นเก่าซ้ำอีกหนึ่งเส้นเพื่อลบ ก็ได้เฟรมถัดไป
    • ไม่จำเป็นต้องวาดพิกเซลทั้งหมดบนหน้าจอหรือเส้นทั้งหมดใหม่ จึงใช้หน่วยความจำและ CPU น้อย
    • วิธีนี้ถูกใช้กับเส้นเคลื่อนที่ในเกม Qix ปี 1981 และเส้นขอบหน้าต่างขณะย้ายตำแหน่งใน GUI ยุคแรก ๆ

อัตลักษณ์ของ half adder

  • ในการบวกหนึ่งบิต บิตต่ำของ a+b คือ a XOR b และบิตสูงคือ a AND b
  • ความสัมพันธ์เดียวกันนี้ใช้ได้กับการดำเนินการระดับบิตของจำนวนเต็มเช่นกัน
    • a + b = (a XOR b) + 2 × (a AND b)
    • a XOR b คือค่าที่ได้จากการบวกแบบไม่มีการทด และ a AND b เก็บบิตการทดที่ควรเกิดขึ้นในแต่ละหลัก
  • ความสัมพันธ์นี้มองได้ว่าเป็น อัตลักษณ์ของ half adder
    • half adder ในฮาร์ดแวร์ใช้เกต AND และ XOR เพื่อสร้างบิตการทดและบิตต่ำของการบวกสองบิต
    • มันไม่ได้สร้างการบวกจำนวนเต็มทั้งหมดด้วยการดำเนินการง่าย ๆ เพียงอย่างเดียว เพราะ + ในสมการด้านขวายังต้องทำหน้าที่จัดการการแพร่การทดให้เสร็จ
  • อัตลักษณ์นี้ใช้คำนวณค่าเฉลี่ยของจำนวนเต็มสองค่าโดยไม่เกิด overflow ได้
    • ถ้าแค่ทำ a+b แล้วเลื่อนขวา อาจสูญเสียบิตสูงสุดของผลรวมแบบ 33 บิต
    • บน CPU ที่ไม่มี carry flag หรือมีคำสั่งอย่าง RRX/RCR ที่ไม่มีหรือใช้งานไม่สะดวก รูปแบบ (a XOR b) >> 1 + (a AND b) เป็นทางเลือกได้
    • ตัวอย่างเช่น MIPS, RISC-V และ DEC Alpha ไม่มี carry flag ส่วน Arm Thumb รุ่นแรกไม่มี RRX
  • บน CPU ที่ไม่มีคำสั่ง XOR ก็สามารถกลับอัตลักษณ์นี้เพื่อสร้าง XOR ได้
    • a XOR b = (a + b) − 2 × (a AND b)
    • CPU ของ Data General ในยุค 1970 มี AND แต่ไม่มี bitwise XOR

การสลับบิตและค่า

  • ปัญหาการสลับบิตสองบิตลดรูปได้ว่า ถ้าบิตสองตัวเท่ากันก็ไม่ต้องทำอะไร และถ้าต่างกันก็แค่กลับค่าทั้งสองบิต
  • ด้วย XOR และ shift เราสามารถหาว่าบิตสองตำแหน่งต่างกันหรือไม่ และหากจำเป็นก็กลับค่าทั้งสองตำแหน่งพร้อมกันได้
    • diff_all = input XOR (input >> distance) ใช้คำนวณความต่างของคู่บิตที่ห่างกันตามระยะที่กำหนด
    • ใช้ AND เพื่อคัดเลือกเฉพาะตำแหน่งที่สนใจ
    • จากนั้นคัดลอกความต่างที่เลือกไปยังอีกตำแหน่ง แล้ว XOR กลับเข้าอินพุตเพื่อกลับค่าทั้งสองบิตเฉพาะเมื่อจำเป็น
  • วิธีเดียวกันนี้ยังใช้สลับคู่บิตหลายคู่ที่ห่างเท่ากันได้พร้อมกัน
    • ใช้ mask ที่มีหลายบิตแทน mask บิตเดียว
    • Beneš network สามารถแทนการเรียงสับเปลี่ยนแบบใดก็ได้ด้วยการสลับหลายคู่ที่มีระยะเท่ากันในหลายขั้นตอน
  • ยังสามารถสลับ ค่าทั้งหมดสองค่า ด้วย XOR swap สามครั้ง ได้
    • a = a XOR b
    • b = b XOR a
    • a = a XOR b
    • แม้ไม่มีตัวแปรชั่วคราว ค่าสองค่าก็จะถูกสลับกัน
  • XOR swap สามครั้งมีปัญหาเรื่อง aliasing
    • มันทำงานได้เมื่อสลับตัวแปรคนละตัว
    • แต่ถ้าชื่อสองชื่อชี้ไปยังตำแหน่งเก็บข้อมูลเดียวกัน เช่น การสลับสมาชิกตัวเดียวกันของอาร์เรย์กับตัวมันเอง ค่าอาจกลายเป็น 0 ได้

เกม Nim และ XOR

  • Nim เป็นเกมที่มีหลายกอง ผู้เล่นผลัดกันเลือกหนึ่งกองแล้วนำหมากออกได้ตั้งแต่ 1 ชิ้นขึ้นไปตามต้องการ และผู้ที่เดินต่อไม่ได้เป็นฝ่ายแพ้
  • ใน Nim แบบพื้นฐาน ตำแหน่งแพ้ คือตำแหน่งที่ XOR แบบระดับบิตของขนาดกองทั้งหมดเป็น 0
  • ในตำแหน่งที่ XOR เป็น 0 ถ้าเปลี่ยนขนาดกองหนึ่งจาก a เป็นค่าอื่น b ค่า XOR รวมจะเปลี่ยนไปเป็น a XOR b และเพราะ a≠b จึงไม่เป็น 0
  • ในตำแหน่งที่ XOR ไม่เป็น 0 ให้ดูบิต 1 ที่สูงที่สุดของค่า XOR รวม x แล้วเลือกกองที่มีบิตนั้นเป็น 1 จากนั้นลดขนาดเป็น pile XOR x ก็จะทำให้ XOR รวมกลายเป็น 0
  • ตัวอย่างเช่น ขนาดกอง 12, 10, 3 อยู่ในเลขฐานสองเป็น 1100, 1010, 0011 และ XOR กันได้ 0101
    • มีเพียงกองใหญ่สุด 12 ที่เมื่อ XOR กับ 0101 แล้วลดลงเป็น 9
    • ดังนั้นตาชนะคือเอาออก 3 ชิ้นจาก 12 ให้เหลือ 9

โครงสร้างทางคณิตศาสตร์ที่คล้าย XOR

  • ในทฤษฎีเซต symmetric difference X∆Y เป็นการดำเนินการที่รวมสมาชิกซึ่งอยู่ในสองเซตนั้นเพียงเซตเดียวเท่านั้น
    • ถ้ามองการเป็นสมาชิกของเซตเป็นค่าบูลีน symmetric difference ก็เท่ากับ XOR
    • ดังนั้นจึงมีสมบัติแบบเดียวกับ XOR เช่น กฎการสลับที่และกฎการเปลี่ยนหมู่
  • ในทฤษฎีกลุ่ม กลุ่มที่มีเลขชี้กำลัง 2 คือกลุ่มที่สมาชิกทุกตัวเป็นอินเวอร์สของตัวเอง
    • การดำเนินการของกลุ่มแบบนี้เป็นไปตามกฎการเปลี่ยนหมู่ และตามแบบฝึกหัดมาตรฐานยังตามด้วยกฎการสลับที่
    • การที่สมาชิกตัวเดิมสองตัวหักล้างกันได้ทำให้มันดูคล้าย XOR
    • กลุ่มที่มีเลขชี้กำลัง 2 ทุกกลุ่มสามารถทำความเข้าใจได้ว่าเป็น XOR แบบระดับบิตของฟังก์ชันที่ให้ค่า {0,1} บางชุด
  • ในการวิเคราะห์แบบ Sprague-Grundy ตำแหน่งของ impartial game จำนวนมากจะถูกกำหนด Grundy number
    • Grundy number ของเกมประกอบที่รวมหลายเกมย่อยเข้าด้วยกันคำนวณได้จากการทำ bitwise XOR ของ Grundy number ของแต่ละเกมองค์ประกอบ
    • ใน game theory บางครั้ง bitwise XOR ของจำนวนเต็มไม่ติดลบจะถูกเรียกว่า nim-sum
  • ฟิลด์ GF(2) เป็นฟิลด์จำกัดที่มีสมาชิกเพียง 0 และ 1
    • การบวกและการลบทำงานเหมือน XOR
    • การคูณทำงานเหมือน AND
    • ดังนั้น a AND (b XOR c) = (a AND b) XOR (a AND c) จึงเป็นจริง

พีชคณิตเชิงเส้นบน GF(2) และการแก้ไขข้อผิดพลาด

  • เวกเตอร์และเมทริกซ์บน GF(2) เป็นโครงสร้างที่แต่ละองค์ประกอบมีค่า 0 หรือ 1 และการบวกเวกเตอร์หรือเมทริกซ์คือ XOR รายองค์ประกอบ
  • การคูณเมทริกซ์ M กับเวกเตอร์ v เทียบได้กับการนำคอลัมน์ของ M ที่ถูกเลือกโดยองค์ประกอบ 1 ใน v มา XOR รวมกัน
  • รหัสแก้ไขข้อผิดพลาด จะขยายข้อความ m บิตให้เป็น codeword n บิตที่ยาวกว่า เพื่อให้สามารถตรวจจับหรือแก้ไขข้อผิดพลาดของบางบิตได้
    • ถ้า codeword ที่ถูกต้องต่างกันหลายบิต ข้อผิดพลาดเพียงไม่กี่บิตก็จะไม่เปลี่ยนมันให้กลายเป็น codeword ที่ถูกต้องอีกชุดหนึ่ง
    • ถ้า codeword ที่ถูกต้องสองชุดต่างกันอย่างน้อย k บิต ข้อผิดพลาดน้อยกว่า k บิตจะตรวจจับได้ และน้อยกว่า k/2 บิตจะสามารถแก้ไขได้โดยหา codeword ที่ใกล้ที่สุด
  • linear code ใช้ generator matrix และ check matrix บน GF(2)
    • ผู้ส่งใช้ generator matrix เพื่อขยายข้อความ m บิตให้เป็น codeword n บิต
    • ผู้รับใช้ check matrix เพื่อตรวจว่าข้อความที่รับมาเป็น codeword ที่ถูกต้องหรือไม่ และถ้ามีข้อผิดพลาดก็จะได้ syndrome
    • รูปแบบข้อผิดพลาดเดียวกันจะสร้าง syndrome เดียวกันโดยไม่ขึ้นกับข้อความเดิม
  • Hamming code เป็นตัวอย่างเมื่อความยาวโค้ด n มีค่าเป็น 2^d−1
    • เมื่อ n=15 จะกำหนดหมายเลขตำแหน่งบิต 15 ตำแหน่งด้วยเลขไบนารี 4 บิตที่ไม่เป็นศูนย์ตั้งแต่ 0001 ถึง 1111
    • ผู้รับจะ XOR ดัชนีของบิตทั้งหมดที่มีค่า 1 และถ้าผลลัพธ์เป็น 0 ก็เป็น codeword ที่ถูกต้อง
    • ถ้ามีบิตหนึ่งบิตถูกกลับค่า ผล XOR จะกลายเป็นดัชนีของบิตที่ผิดนั้นโดยตรง ทำให้แก้ข้อผิดพลาด 1 บิตได้โดยไม่ต้องมี lookup table
    • Hamming code ขนาด 15 บิตบรรจุข้อมูลได้ 11 บิต และใช้ 4 บิตสำหรับการแก้ไขข้อผิดพลาด

พหุนามบน GF(2), CRC และฟิลด์จำกัดที่ใหญ่กว่า

  • พหุนามบน GF(2) คือพหุนามเชิงรูปแบบที่สัมประสิทธิ์เป็น 0 หรือ 1 และการบวกเทียบได้กับการ XOR สัมประสิทธิ์ที่มีดีกรีเดียวกัน
  • การคูณพหุนามทำโดยสร้าง partial product แบบพหุนามทั่วไป แล้วลดสัมประสิทธิ์ด้วย mod 2
    • ถ้ามองรูปแบบนี้เป็นบิตสตริง มันคล้ายการคูณจำนวนเต็ม แต่ตอนรวม partial product จะใช้ XOR แบบไม่มีการทดแทนการบวกทั่วไป
    • x86 มีคำสั่งคูณแบบไม่มีการทดรวมถึง CLMUL และ Arm มีชุดคำสั่งสำหรับ polynomial multiplication
  • CRC คือวิธีใช้เศษจากการหารพหุนามบน GF(2) เป็น checksum
    • มองบิตสตริงของข้อความที่ส่งเป็นพหุนามขนาดใหญ่ M แล้วเก็บเศษ M mod P จากการหารด้วยพหุนามที่ตกลงกันไว้ P
    • มันถูกใช้ในการตรวจสอบแพ็กเก็ตเครือข่ายอย่าง Ethernet และเครือข่ายที่คล้ายกัน
    • CRC ไม่ได้แก้ไขข้อผิดพลาด แต่มีไว้เพื่อตรวจจับเท่านั้น และเหมาะกับสถานการณ์ที่การส่งส่วนใหญ่ถูกต้องตามปกติและมีการกลับบิตหรือสัญญาณรบกวนเกิดขึ้นไม่บ่อย
  • ฟิลด์จำกัดที่ใหญ่กว่าสามารถสร้างได้จากโครงสร้างเศษเหลือของพหุนามบน GF(p) เมื่อหารด้วย irreducible polynomial Q
    • ถ้าดีกรีของ Q เท่ากับ d ฟิลด์จำกัดใหม่จะมีสมาชิก p^d ตัว
    • ในกรณี p=2 irreducible polynomial สามารถเขียนเป็นรูปแบบบิตเหมือนจำนวนเต็มได้ และลำดับดังกล่าวถูกบันทึกไว้ใน OEIS A014580
  • ฟิลด์จำกัดที่มีขนาดเป็นกำลังของ 2 ปรากฏในเทคนิคการเข้ารหัสหลายแบบ
    • ฟิลด์จำกัดขนาด 2^8 เป็นองค์ประกอบหลักของ AES และ Twofish
    • ฟิลด์จำกัดขนาด 2^128 ถูกใช้ใน GCM ซึ่งรวมการเข้ารหัสข้อมูลจำนวนมากกับการปกป้องความถูกต้องสมบูรณ์ของข้อมูล
    • ฟิลด์จำกัดขนาดเป็นกำลังของ 2 ยังปรากฏใน elliptic-curve cryptography บางแบบ และในอัลกอริทึมถอดรหัสของ Classic McEliece ซึ่งเป็นวิธีแบบ post-quantum

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2025-02-19
ความคิดเห็นบน Hacker News

  • เทคนิค XOR ต้องสาปที่ผมชอบคือ XOR doubly linked list: https://en.m.wikipedia.org/wiki/XOR_linked_list
    แทนที่แต่ละโหนดจะเก็บพอยน์เตอร์ถัดไป/ก่อนหน้าแยกกัน มันเก็บค่าเดียวที่ได้จากการ XOR ทั้งสองค่าเข้าด้วยกัน แน่นอนว่ามันไม่ใช่พอยน์เตอร์ที่ถูกต้อง แต่ตอนวนลูป ถ้าเอาพอยน์เตอร์ของโหนดก่อนหน้ามา XOR กับพอยน์เตอร์รวม ก็จะได้พอยน์เตอร์ของโหนดถัดไปออกมา และยังวนได้สองทิศทางด้วย รู้สึกเหมือนอะไรที่ผิดกฎหมาย

    • เมื่อเทียบกับ doubly linked list ปกติ จะสูญเสีย ความสามารถในการลบรายการนั้น ในกรณีที่มีแค่แอดเดรสของรายการ หรือมีแค่ iterator ที่เสถียรต่อการแทรก/ลบเท่านั้น แต่บ่อยครั้งนี่แหละคือเหตุผลหลักที่ใช้ doubly linked list
      ข้อเสียที่เป็นสาระรองลงมาคือ การเขียน XOR linked list ใน C ที่เคร่งตามมาตรฐานนั้นยุ่งยากมาก มาตรฐานไม่ได้รับประกันว่าเมื่อ cast พอยน์เตอร์ตัวเดียวกันเป็นจำนวนเต็มแล้วจะได้จำนวนเต็มค่าเดียวกัน ดังนั้นในทางปฏิบัติจึงต้องทำทุกอย่างเป็น uintptr_t เพื่อคงเวอร์ชัน cast เป็นจำนวนเต็มที่ canonicalized ไว้
    • แม้บนโปรเซสเซอร์ 64 บิต ถ้าถือว่าแอปส่วนใหญ่ใช้ RAM ต่ำกว่า 4GB ก็เพียงพอแล้ว ก็สามารถลดพื้นที่จัดเก็บลงได้อีกด้วยการใช้แค่ address space 32 บิต
      ไกลกว่านั้น อาจใช้พอยน์เตอร์แบบ near/relative 16 บิตก็ได้ อาจเข้ากับ data-oriented design ได้ดี เช่นมีบล็อก 64K elements แล้วให้องค์ประกอบภายในชี้กันด้วย index แบบ uint16
    • ทำแบบนี้ garbage collector คงไม่ชอบ หรืออย่างน้อยก็คงตัดสินว่าโครงสร้างข้อมูลนี้เป็นขยะ
    • สงสัยว่าทำไมถึงอยากใช้เทคนิคนี้
    • นี่ไม่ได้ต่างจากการเก็บผลต่างของพอยน์เตอร์สองตัวมากนัก มากกว่าจะเป็นพอยน์เตอร์จริง ๆ ถ้าเก็บผลต่างก็แน่นอนว่าสามารถวนได้สองทิศทางเหมือนกัน

  • มีอย่างหนึ่งที่ตกหล่นไป XOR ยังเป็น ฟังก์ชันแฮชเชิงเส้นแบบ 3-wise independent ด้วย จึงใช้สำหรับการสุ่มตัวอย่างคำตอบของฟังก์ชันบูลีนแบบเกือบสม่ำเสมอเชิงความน่าจะเป็น และการนับจำนวนคำตอบได้ มันมีประโยชน์จริง ๆ และถูกใช้สร้างตัวนับที่ให้จำนวนแบบพิสูจน์ได้แม้จะเป็นเชิงความน่าจะเป็น ผมเขียนคำอธิบายที่เข้าใจง่ายกว่าไว้ที่นี่ https://www.msoos.org/2018/12/how-approximate-model-counting...
    โดยพื้นฐานแล้ว ทุกครั้งมันจะลดปริภูมิคำตอบลงเกือบพอดีครึ่งหนึ่ง ดังนั้นก็เพิ่มเงื่อนไข XOR ต่อไปเรื่อย ๆ จนเช่นเหลือคำตอบ 10 รายการ แล้วถ้าจำนวน XOR ที่เพิ่มเข้าไปคือ k ก็เอา 10 คูณ 2^k ได้เลย เพราะแต่ละครั้งลดครึ่งหนึ่ง จึงไปถึงระดับ 10 รายการได้เร็วและสเกลได้ดี
    งานวิจัยที่เกี่ยวข้องอยู่ที่ https://arxiv.org/abs/1306.5726 และ https://www.cs.toronto.edu/~meel/Papers/cav20-sgm.pdf ส่วนเครื่องมืออยู่ที่ https://github.com/meelgroup/approxmc และ https://github.com/meelgroup/unigen ในการแข่งขัน model counting ครั้งที่ผ่านมา เมื่อจับคู่กับตัวนับแบบ exact แล้ว มันเหนือกว่าคู่แข่งรายอื่นอย่างท่วมท้น สไลด์อยู่ที่ https://mccompetition.org/assets/files/2024/MC2024_awards.pd...

  • เกร็ดเรื่อง XOR ที่ผมชอบเรื่องหนึ่งคือเรื่องที่ Bryan Cantrill จาก Oxide, Joyent, Sun เล่าไว้ในพรีเซนเทชันนี้ https://speakerdeck.com/bcantrill/oral-tradition-in-software... และวิดีโอนี้ https://www.youtube.com/watch?v=4PaWFYm0kEw
    สรุปแบบไม่ต้องกดลิงก์คือ ตอนอยู่ที่ Sun เขาคุยกับเพื่อนร่วมงาน Roger Faulkner ว่าทำไม C ถึงไม่มี logical XOR แล้ว Faulkner บอกว่าเพราะมันทำ short-circuit evaluation ไม่ได้ Brian คิดว่ามันแปลก Roger เลยส่งอีเมลไปถาม Dennis Ritchie และ Ritchie ก็ยืนยันว่า Faulkner พูดถูก วิธีเล่าของ Cantrill ก็ตลกดี แต่ที่น่าทึ่งคือการที่เขาสามารถถามเจ้าตัวได้โดยตรง

    • DMR เป็นคนใจดี ช่วยเหลือดี และเข้าถึงง่ายอย่างน่าประหลาด ตอนเป็นนักศึกษาปริญญาตรีช่วงกลางยุค 80 ผมอ่านเรื่องการพอร์ต Unix v6 “ครั้งแรก” ไปยัง Interdata 8/32 ที่ไม่ใช่ PDP-11 แล้วก็ส่งอีเมลสุ่มไปที่ dmr@research.att.com เพื่อถามว่ามีข้อมูลสถาปัตยกรรมเพิ่มเติมไหม
      ตอนนั้นยังไม่มี Google และห้องสมุดมหาวิทยาลัยก็ไม่มีเอกสาร ไม่กี่วันต่อมาเขาถามที่อยู่จริง แล้วอีกไม่กี่สัปดาห์ถัดมา สำเนา คู่มือสรุปชุดคำสั่ง ก็มาถึงตู้ไปรษณีย์ มันให้ความรู้สึกเหมือนตระกูล IBM 360 และผมยังเก็บไว้จนถึงทุกวันนี้
    • C มี logical XOR อยู่แล้ว ก็คือโอเปอเรเตอร์ != นั่นเอง ต่างจาก logical operator อื่น ๆ ตรงที่ต้อง normalize อาร์กิวเมนต์ให้เป็นค่าความจริงเดี่ยว และเข้ากันได้ดีกับสำนวนการแปลงเป็นบูลีนของ C คือ !!
    • ไม่เข้าใจว่า “เพราะมันทำ short-circuit evaluation ไม่ได้” กลายเป็นอุปสรรคต่อการเพิ่มโอเปอเรเตอร์ได้อย่างไร อยากให้ใครช่วยอธิบาย
    • หัวข้อนั้นเริ่มที่ 37:18
    • C มี bitwise XOR operator ^ มานานกว่า 40 ปีแล้ว: https://www.geeksforgeeks.org/bitwise-operators-in-c-cpp/

  • วันนี้เพิ่งรู้ว่า ถ้านำอีโมจิรถยนต์ไป XOR กับ 0x20 หรือพูดอีกอย่างคือทำให้เป็น “ตัวพิมพ์เล็ก” มันจะกลายเป็น อีโมจิห้ามคนเดินเท้า ดูบังเอิญแบบพอดีเกินไป เลยสงสัยว่ามีใครรู้ไหมว่ามันตั้งใจทำหรือเปล่า
    ถ้าคิดเลยเถิดไปอีก ก็อาจได้ไอเดียประหลาดว่าอักษรตัวพิมพ์เล็กของอีโมจิรถยนต์คือป้าย “ห้ามคนเดินเท้า”

    • ถ้าจะเลี่ยงตัวจัดการคอมเมนต์ของ HN ที่ลบอีโมจิออก สามารถตรวจสอบแบบนี้ได้:
      >>> from unicodedata import lookup, name
      >>> name(chr(ord(lookup('AUTOMOBILE')) ^ 0x20))
      'NO PEDESTRIANS'
    • ตัวพิมพ์เล็กของรถยนต์น่าจะเป็น โกคาร์ต มากกว่า
    • :tada: → :tophat:, :rocket: → :mountain_cableway: ก็ทำได้เช่นกัน

  • อุปมาในโลกจริงที่ใช้説明 XOR ได้ดีคือ สวิตช์ไฟ บนบันไดในบ้าน มีสวิตช์ตัวหนึ่งอยู่ด้านล่าง อีกตัวอยู่ด้านบน และทั้งคู่ควบคุมไฟดวงเดียวกัน
    ตอนแรกทั้งคู่ อยู่ในตำแหน่งปิด พอเปิดสวิตช์ด้านล่าง ไฟก็ติด พอเดินขึ้นบันไดไปเปิดสวิตช์ด้านบน แม้สวิตช์ทั้งสองจะอยู่ในตำแหน่ง “เปิด” แต่ไฟกลับดับ ไฟจะติดก็ต่อเมื่อมีสวิตช์เพียงตัวเดียวที่ “เปิด” และอีกตัว “ปิด” เท่านั้น นอกนั้นไฟจะดับ

    • ช่างไฟที่ออฟฟิศเราอาจจะเดินสายผิดก็ได้ ในห้องมีสวิตช์สองตัว แต่พอคิดดูแล้วมันทำงานเหมือน AND gate มากกว่า XOR ส่วนสวิตช์สองตัวในห้องนั่งเล่นนี่ทำงานเหมือน XOR แน่นอน

  • ผมไม่ชอบเลยที่ฟังก์ชันตรรกะนี้มักถูกเรียกว่า XOR หรือ “exclusive OR” เพราะแทบทุกครั้งความหมายจริง ๆ คือ “ผลบวกโมดูโล 2” หรือ พาริตี ไม่ใช่ exclusive OR
    “ผลบวกโมดูโล 2”/พาริตี กับ “exclusive OR” เป็นฟังก์ชันตรรกะคนละตัวกัน และบังเอิญตรงกันเฉพาะตอนมีโอเปอแรนด์อินพุต 2 ตัวเท่านั้น เพราะมีจำนวนคี่ที่ไม่เกิน 2 อยู่แค่ค่าเดียว
    เมื่อมีอินพุต 3 ตัวขึ้นไป สิ่งที่คนส่วนใหญ่เรียกว่า XOR แท้จริงแล้วคือพาริตี ซึ่งให้ค่า 1 เมื่อมีอินพุตจำนวนคี่ตัวเป็น 1 ในทางตรงกันข้าม exclusive OR เมื่อมีอินพุต 3 ตัวขึ้นไป จะเป็นฟังก์ชันที่ให้ค่า 1 ก็ต่อเมื่อมีอินพุตเพียงตัวเดียวเท่านั้นที่เป็น 1 และที่เหลือทั้งหมดเป็น 0
    ในฮาร์ดแวร์คอมพิวเตอร์ พาริตีสำคัญกว่า exclusive OR มาก เหตุผลหลักคือการบวกโมดูโล 2 ถูกใช้เป็นองค์ประกอบสำหรับสร้างการบวกจำนวนที่ใหญ่กว่า ในทางกลับกัน ในคณิตศาสตร์ exclusive OR สำคัญกว่าพาริตีมาก
    เช่น ตัวบ่งปริมาณที่ใช้แสดงว่าภาคแสดงหนึ่งเป็นจริงสำหรับสมาชิกบางตัว สมาชิกทุกตัว หรือสมาชิกตัวเดียวเท่านั้นของเซต จะอิงกับ OR, AND และ exclusive OR ตามลำดับ “or” ในภาษาธรรมชาติมักหมายถึง inclusive OR หรือ exclusive OR เสมอ ไม่ได้หมายถึงพาริตีที่โปรแกรมเมอร์จำนวนมากเรียกว่า XOR
    ในการเขียนโปรแกรม โอกาสที่จะต้องคำนวณฟังก์ชันตรรกะ exclusive OR มีน้อย แต่ใช้บ่อยในการอธิบายพฤติกรรมของโปรแกรม เช่น เมื่อบอกว่าในคำสั่งผสม select/case/switch จะมีคำสั่งที่หนึ่ง หรือคำสั่งที่สอง หรือคำสั่งที่สามเพียงคำสั่งหนึ่งถูกเรียกใช้ หรือเมื่ออธิบายชนิดที่ค่าปัจจุบันของตัวแปรแบบ union/sum type อาจมีได้

    • มาตรฐานสัญลักษณ์ทางไฟฟ้า IEC 60617 จัดการเรื่องนี้ได้ถูกต้อง โดยแสดง XOR gate เป็น =1 และ parity gate เป็น 2k + 1 แต่เวลาใช้ซอฟต์แวร์ออกแบบวงจรสำหรับ PCB หรือ FPGA ก็ยังอาจโดนหลอกได้ เพราะได้สิ่งที่ต่างจากที่คาดไว้
    • สิ่งที่พูดถึงในคณิตศาสตร์เรียกว่า ตัวบ่งปริมาณการมีอยู่เพียงหนึ่งเดียว และมีสัญลักษณ์ของตัวเองคือ ∃!
    • คำอธิบายที่ว่าเมื่อมีอินพุต 3 ตัวขึ้นไป “exclusive OR” จะเป็นจริงเมื่อมีแค่ตัวเดียวเป็น 1 ต้องมีหลักฐานรองรับ
    • การตีความนี้ก็ถูกพูดถึงในเอสเซย์ต้นฉบับด้วย

  • ยังมี Kademlia distributed hash table ด้วย: kademlia distributed hash table ไอเดียใหญ่คือแต่ละโหนดได้รับบิตแบบสุ่มในช่วง [0, 2^m) และนิยามระยะทางด้วย XOR เป้าหมายคือหาอัลกอริทึมแบบกระจายศูนย์ที่ส่งข้อมูลจาก X ไปยัง Y ได้อย่างรวดเร็วโดยไม่ต้องรู้จักทั้งเครือข่าย
    แค่มองคณิตศาสตร์ก็พิสูจน์ได้ว่ามันทำงาน แต่สัญชาตญาณเชิงภาพที่ผมชอบคือแบบนี้ สมมติว่าโหนดเริ่มต้น X ต้องการหาโหนด k นิยาม “ต้นไม้ระยะทางจาก X” เป็นต้นไม้ไบนารีที่ดัชนีใบคือ 0, 1, 2... โดยติดป้ายแต่ละใบเป็น X^leaf_index เพื่อแทนระยะทางจาก X ตัวอย่างเช่น dist(x, x) = x^x = 0 ดังนั้นป้ายของโหนดเดิม X จะอยู่ที่ใบซ้ายสุด 0
    ช่วง [2^i, 2^(i+1)) คือซับทรีบางต้นในต้นไม้ระยะทางจาก X ถ้ารู้ว่าระยะของ k อยู่ในช่วงนั้น ก็จะสอบถามโหนด Y บางตัวในช่วงนั้นในฐานะเพื่อนบ้านโดยประมาณ
    ไม่ว่าจะเลือก Y ตัวไหน ในต้นไม้ระยะทางจาก Y ผลลัพธ์ส่วน prefix จะเป็นเพียงการเรียงสับเปลี่ยนบางแบบของซับทรี [2^i, 2^(i+1)) ที่เลือกไว้ในต้นไม้ระยะทางจาก X เสมอ พูดให้แม่นขึ้นคือมองได้ว่า labels_of_leaves_of_X([2^i, 2^(i+1))) == labels_of_leaves_of_Y([0, 2^i)) ดัชนีอิงตามระยะทาง แต่ป้ายอาจต่างกันได้
    สำหรับการเปรียบเทียบกับ distributed hash table แบบอื่นอย่าง Chord มีข้อมูลที่เข้มงวดกว่ามากทั้งเชิงคณิตศาสตร์และเชิงประสบการณ์ แต่สัญชาตญาณเชิงภาพนี้ทำให้เห็นว่า “สมมาตร” ของ Kademlia คืออะไร และให้ความรู้สึกว่าทุกคนมีเพื่อนบ้านในพื้นที่กับซับทรีของตัวเอง
    ในทางกลับกัน Chord แม้จะทำแบบสองทิศทาง หน่วยความจำก็เพิ่มเป็น 2 เท่า และการใช้งานก็ดูเสี่ยงกว่า อีกทั้งยากจะได้ “ความโดดเดี่ยว” ระดับนี้ หน้าต่างเลื่อนของเพื่อนบ้านขนาด S จะเคลื่อนตลอดเวลา และมีเพื่อนบ้านที่ต่างกัน 2^m ตัวต่อบิต แม้เพื่อนบ้านส่วนใหญ่จะดูคล้ายกัน แต่ก็ไม่เรียบร้อยนัก
    Kademlia มีเพื่อนบ้าน 1 + 2 + 4 ... + 2^m-1 ตัว และทั้งระบบถูกจัดวางอย่างเป็นระเบียบ

  • เสริมเผื่อใครสงสัย คนนี้คือ Simon Tatham คนเดียวกับใน Simon Tatham's Portable Puzzle Collection ถ้ายังไม่รู้จัก ก็เหมาะไว้เล่นตอนเบื่อ ๆ แบบออฟไลน์
    สมัยมัธยมผมเสียเวลาไปกับของพวกนี้เยอะมาก: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/

    • และยังเป็น Simon Tatham คนเดียวกับที่สร้าง PuTTY ด้วย: https://www.chiark.greenend.org.uk/~sgtatham/putty/
    • จุดที่ดีที่สุดคืออัลกอริทึม Minesweeper ทำให้ได้ เกมที่ไม่ต้องเดา

  • ทุกวันนี้ตัวแก้ปัญหาแบบปรับแต่งเฉพาะทางจำนวนมาก เช่น Ising Machine ใช้ปัญหา XOR เป็นเบนช์มาร์ก ในทางปฏิบัติ การแก้อนุประโยค XOR หลาย ๆ อันสามารถทำได้ในเวลาพหุนามด้วยวิธีกำจัดแบบเกาส์ จึงมีประโยชน์ลดลงอยู่บ้าง แต่เนื่องจากตัวแก้ปัญหาทั้งหมดแสดงการขยายตัวแบบเอ็กซ์โปเนนเชียล มันจึงยังเป็นวิธีที่ดีในการประเมินประสิทธิภาพ
    การนำไปใช้อีกแบบที่น่าสนใจแบบที่สองเกี่ยวข้องกับ ระบบเข้ารหัส McEliece ซึ่งเป็นการเข้ารหัสกุญแจสาธารณะจากยุค 70 และช่วงนี้กลับมาได้รับความสนใจอีกครั้งเพราะทนทานต่อควอนตัม การโจมตีเพื่อถอดรหัสคือปัญหาการหาคำตอบของชุดสมการ XOR ซึ่งก็เป็นเวลาแบบพหุนามเช่นกัน แต่มีเงื่อนไขเพิ่มเติมว่าระยะทางแฮมมิงต้องเท่ากับค่าบางอย่างที่รวมอยู่ในกุญแจสาธารณะ

  • ตอนเรียน Z80 Assembly เพื่อเขียนโปรแกรมบน TI-83 ทุกไบต์ของภาษาเครื่องล้วนสำคัญ เพราะพื้นที่เก็บข้อมูลทั้งหมดของเครื่องคิดเลขมีเพียง 24KB
    หากต้องการเริ่มต้นรีจิสเตอร์ตัวสะสมหลัก a ให้เป็น 0 จะใช้ XOR a แทน LD a, 0 ในคำสั่งทางคณิตศาสตร์ a เป็นตัวถูกดำเนินการโดยอัตโนมัติ ดังนั้น XOR a จึง XOR a กับตัวมันเอง และคำสั่งทั้งหมดมีขนาดเพียง 1 ไบต์ ในทางกลับกัน หากจะโหลดค่า 0 เข้าไปใน a อย่างชัดเจน ค่า literal 0 ต้องอยู่ใน opcode ทำให้ LD a, 0 เป็นคำสั่งขนาด 2 ไบต์