[Blockchain] ตัวสร้างเลขสุ่มเทียม
คำนิยาม
ค่าเริ่มต้น (seed) คือข้อมูลดิจิทัลใด ๆ ซึ่งทำหน้าที่เป็นต้นกำเนิดในการสร้างผลลัพธ์
เอนโทรปี (entropy) คือตัวชี้วัดของความผิดปกติของระบบใด ๆ
เลขสุ่มเทียม (pseudorandom number) คือข้อมูลตัวเลขที่เกิดจากการนำค่าเริ่มต้นมาผ่านฟังก์ชันทางคอมพิวเตอร์แบบดีเทอมินิสติก
คาบ (period) คือจำนวนครั้งในการสุ่มก่อนที่จะได้ผลลัพธ์ที่ซ้ำกัน
สมการเวียนเกิด (recurrence relation) คือการนิยามฟังก์ชันโดยใช้นิพจน์ที่มีความสัมพันธ์นั้นปรากฏอยู่
ดีเทอมินิสติก (deterministic) คือทุกเหตุการณ์ที่เกิดขึ้นมีปัจจัยที่สามารถกำหนดได้โดยสมบูรณ์
ตัวสร้างตัวเลขสุ่มเทียมมีความสำคัญในทางคณิตศาสตร์ การเข้ารหัส และการเสี่ยงโชค ตัวสร้างเลขสุ่มอาจได้จากฮาร์ดแวร์ซึ่งเป็นการสุ่มแท้ หรือเกิดจากซอฟต์แวร์ซึ่งเป็นการสุ่มเทียม โดยในที่นี้จะกล่าวถึงตัวสร้างเลขเทียมที่ได้จากการสุ่มโดยใช้ซอฟต์แวร์
ความแตกต่างระหว่างเลขสุ่มแท้และเลขสุ่มเทียมสามารถแบ่งแยกได้ตามตารางที่ 1
จากตารางที่ 1 จะเห็นว่าการเลือกใช้วิธีในการสร้างเลขสุ่มจะขึ้นอยู่กับวัตถุประสงค์หรือเป้าหมายที่แตกต่างกัน ยกตัวอย่างเช่น หากต้องการสร้างเลขสุ่มโดยใช้ต้นทุนน้อย มีความรวดเร็วสูง สามารถทดสอบซอฟต์แวร์โดยการทำซ้ำได้ และผลลัพธ์ที่ได้ไม่ส่งผลให้เกิดความร้ายแรงมาก สามารถเลือกใช้วิธีการสร้างเลขสุ่มเทียมซึ่งจะเหมาะสมกว่า ในทางกลับกัน หากผลลัพธ์ที่ได้ส่งผลต่อสิ่งที่จะตามมาอย่างยิ่งยวด เช่นการจ่ายรางวัลในการเสี่ยงโชค และไม่ได้มีความจำเป็นที่ต้องการความรวดเร็วทันทีทันใด ควรพิจารณาเลือกสร้างเลขสุ่มแท้
ปัญหาของตัวสร้างเลขสุ่มเทียม
1. คาบเวลาการซ้ำสั้นกว่าที่คาดไว้สำหรับค่าเริ่มต้นบางค่า
2. ขาดเอกรูป (non-uniform) ในเลขสุ่มเทียมเมื่อสร้างตัวเลขสุ่มมาแล้วเป็นจำนวนมาก
3. เกิดความสัมพันธ์กับค่าที่อยู่ติดกันซึ่งอาจทำให้ผู้โจมตีสามารถคาดเดาตัวต่อไปได้
4. การแจกแจงมีลิมิตหรือขอบเขตที่ไม่ดี (poor dimension)
อัลกอริทึมสำหรับการสร้างเลขสุ่มเทียมในอดีต
ในที่นี้จะขอนำเสนออัลกอริทึมสำหรับสร้างเลขสุ่มเทียม 2 อัลกอริทึมดังต่อไปนี้
1. ตัวสร้างความสอดคล้องแบบเชิงเส้น (Linear Congruential Generators : LCG)
2. วิธีมิดเดิลสแควร์ (Middle-square method)
ตัวสร้างความสอดคล้องแบบเชิงเส้น
ตัวสร้างความสอดคล้องแบบเชิงเส้นเป็นหนึ่งในขั้นตอนวิธีที่นิยมใช้งานของตัวสร้างเลขสุ่มเทียม ซึ่งเป็นการสร้างตัวสุ่มโดยใช้สมการเวียนเกิด ที่มีความสัมพันธ์ดังต่อไปนี้
โดยที่
สังเกตเห็นว่า ตัวเลขสุ่มที่ได้จากความสัมพันธ์ข้างต้น คือค่าของ Xn+1 ซึ่งเป็นผลที่ได้มาจากค่าของตัวเลขสุ่มลำดับก่อนหน้า (Xn) แสดงว่าทุกตัวเลขสุ่มที่สุ่มได้ออกมานั้น เป็นผลลัพธ์ที่ได้จากเลขสุ่มตัวก่อนหน้าเสมอ ดังนั้น X1 คือ เลขสุ่มตัวแรกที่ได้ออกมาจากความสัมพันธ์นี้ โดยที่มี ค่าเริ่มต้น คือ (X0)
จากข้อสังเกตข้างต้น เราจะสรุปได้ว่า ถ้าเราเริ่มต้นด้วยค่าเริ่มต้นเดียวกัน ลำดับของตัวเลขสุ่มที่มาจาก ความสัมพันธ์นี้ ที่มีค่า X0 , a, c และ m เป็นตัวเลขชุดเดียวกัน จะมีลำดับเหมือนกันเสมอ ซึ่งถ้าดูจากความสัมพันธ์ Xn+1 = (aXn + c) mod m แล้ว จะเห็นว่าเป็นความสัมพันธ์ที่ทำความข้าใจได้ง่าย ไม่ซับซ้อน และสามารถนำไปเขียนโค้ดได้ง่าย จึงเป็นนิยมใช้กันอย่างแพร่หลาย
ขนาดของคาบจะมีค่าได้สูงสุดเกือบเท่ากับ m แต่ก็มีบางส่วนที่มีค่าต่ำกว่านั้นมาก ถ้าเรากำหนดให้ c เป็นจำนวนเต็มที่มีค่ามากกว่า 0 แล้ว ตัวสร้างความสอดคล้องแบบเชิงเส้นจะมีคาบแบบสูงในทุก ๆ ค่าเริ่มต้นก็ต่อเมื่อมีเงื่อนไขต่อไปนี้
1. c และ m ไม่มีตัวร่วมร่วมกัน
2. ตัวประกอบที่เป็นจำนวนเฉพาะทุกตัวของ m จะสามารถหาร a-1 ได้ลงตัว
3. a จะเป็นพหุคูณของ 4 ถ้า m เป็นพหุคูณของ 4 ด้วย
แม้ว่าตัวสร้างความสอดคล้องแบบเชิงเส้น จะมีความสามารถในการสร้างตัวเลขสุ่มเทียมได้เป็นอย่างดีก็ตาม แต่ว่ามันก็มีความละเอียดอ่อนมากในการเลือกค่าของ a , c และ m ดังนั้นเราต้องเลือกค่าต่าง ๆ ดังกล่าวให้ดี เพื่อที่จะให้ตัวสร้างความสอดคล้องแบบเชิงเส้นทำงานได้ดีตามที่ต้องการ
ตัวอย่างค่าของ a, c และ m ที่ใช้กันทั่วไป
โดยมาก ค่าของ m ที่ใช้ในการสร้างตัวสร้างความสอดคล้องแบบเชิงเส้น จะมีค่าเปนค่าที่เป็นค่า 2 ยกกำลัง ซึ่งส่วนใหญ่เป็นค่า 232 หรือ 264 เพราะสามารถคำนวณผ่านคอมพิวเตอร์ได้โดยการชิฟขวาไป 32 หรือ 64 บิตตามลำดับ โดยตารางที่ 2 จะแสดงถึงค่าที่ใช้กันโดยทั่วไป รวมทั้งค่าที่อยู่ในรันไทม์ไลบรารีของคอมไพเลอร์ต่าง ๆ
รหัสเทียม
วิธีมิดเดิลสแควร์
วิธีมิดเดิลสแควร์ คือกระบวนการสร้างเลขสุมเทียมที่ง่าย ถูกคิดค้นเมื่อปี ค.ศ. 1949 โดย John von Neumann ซึ่งวิธีนี้ไม่ใช่วิธีทีดีนัก เนื่องจากคาบค่อนข้างน้อย เป็นเหตุให้เกิดค่าผลลัพธ์ที่ซ้ำกันเมื่อโปรแกรมทำงานไปสักระยะ ทำให้สามารถทำนายผลลัพธ์ได้ง่าย
โดยที่
ตัวอย่าง เมื่อกำหนดค่าเริ่มต้นเป็น 675248 นำไปยกกำลังสองจะได้ 455959861504 จากนั้นสำตัวเลข 4 ตัวตรงกลาง (กรณีผลลัพธ์มีจำนวนหลักไม่ถึง 8 หลัก ให้เพิ่มเลข 0 ด้านหน้า) เพื่อกลับไปเป็นค่าเริ่มต้นในการวนซ้ำดังแสดงดังภาพที่ 1
รหัสเทียม
อ้างอิง
Barker, Elaine, Larry Feldman, and Gregory Witte. Recommendation for Random Number Generation Using Deterministic Random Bit Generators. National Institute of Standards and Technology (2015).
Devroye, Luc. “Sample-Based Non-Uniform Random Variate Generation.” Paper presented at the Proceedings of the 18th conference on Winter simulation, 1986.
Knuth, Donald E. Art of Computer Programming, Volume 2: Seminumerical Algorithms. Addison-Wesley Professional, 2014.
Von Neumann, John. “13. Various Techniques Used in Connection with Random Digits.” Appl. Math Ser 12, no. 36–38 (1951): 5.
