ตัวสร้างเลขสุ่มเทียม

คำอธิบาย

ตัวสร้างเลขสุ่มเทียม หรือที่รู้จักกันในนาม ตัวสร้างบิตสุ่มแบบกำหนดได้ (Deterministic random bit generator: DRBG) เป็นขั้นตอนวิธีสำหรับใช้ในการสร้างลำดับของตัวเลขที่มีความใกล้เคียงกับคุณสมบัติของการสุ่ม ถึงแม้ว่าลำดับตัวเลขที่ได้จากขั้นตอนวิธีตัวสร้างเลขสุ่มเทียมนี้จะใกล้เคียงกับลำดับเลขสุ่มแท้จริงมากแค่ไหนแต่มันก็ไม่ได้เป็นลำดับตัวเลขแบบสุ่มที่แท้จริงเนื่องจากลำดับตัวเลขที่ได้ออกมาจากตัวสร้างเลขสุ่มเทียมทั้งหมดได้มาจากกลุ่มเล็กๆของค่าเริ่มต้นที่เรากำหนดให้เป็นตัวตั้งต้น (seed) ของตัวสร้างเลขสุ่มเทียม ถึงแม้ว่าเรามีตัวสร้างเลขสุ่มจากฮาร์ดแวร์ที่สามารถนำมาสร้างลำดับสุ่มแท้ได้ แต่ลำดับสุ่มเสมือนที่ได้จากตัวสร้างเลขสุ่มเทียมเองก็มีความสำคัญในทางปฏิบัติหลายๆอย่าง ทั้งในด้านการจำลอง เช่น ระบบกายภาพที่ใช้วิธีมอนติคาร์โล ในด้านการเข้ารหัส (cryptography) ในด้านการก่อกำเนิดกระบวนคำสั่ง (procedural generation) ส่วนใหญ่เกี่ยวข้องกับคอมพิวเตอร์กราฟิกส์ (โปรแกรมประยุกต์และวิดีโอเกมขั้นออกแบบ) ขั้นตอนวิธีเชิงสุ่มมากมายเองก็ได้อิทธิพลมาจากตัวสร้างเลขสุ่มเทียมเป็นส่วนหนึ่งในการแก้ปัญหา นอกจากการใช้งานแล้วการพิสูจน์ว่าตัวสร้างเลขสุ่มเทียมใช้งานได้จริงก็มีความสำคัญไม่แพ้กัน ซึ่งการพิสูจน์นี้ต้องอาศัยการวิเคราะห์ทางคณิตศาสตร์อย่างระมัดระวังในการทำให้แน่ใจได้ว่าตัวสร้างเลขสุ่มเทียมได้สร้างลำดับสุ่มเสมือนที่มีลักษณะสุ่มเพียงพอสำหรับการใช้งาน

ประวัติ

ตัวสร้างเลขสุ่มเทียมที่อาศัยคอมพิวเตอร์ ยุคแรกๆ คิดค้นโดย จอห์น ฟอน นอยมันน์ ในปี ค.ศ. 1946 รู้จักกันในนามของ วิธีมิดเดิลสแควร์ (middle-square method) ขั้นตอนวิธีนี้ง่ายมาก รับตัวเลขอะไรเข้ามาเป็น ตัวตั้งต้น ก็นำตัวเลขนั้นมายกกำลัง 2 แล้วนำหลักตรงกลางออกจากผลลัพธ์ที่ได้ ก็จะได้ตัวเลขสุ่มขึ้นมาตามต้องการ ซึ่งสามารถนำตัวเลขนี้มาเป็น ตัวตั้งต้น ในการสร้างตัวเลขสุ่มอื่นๆต่อไปได้เรื่อยๆ

รหัสเทียม

Input: ตัวเลข 
Output: ยกกำลังสอง Input ที่นำตัวเลขตำแหน่งกลางออก
 
 int main ()
 {
 int in;
 int tmp =in*in;
 int tmp2=tmp;
 //หาจำนวนหลัก
 int length=0;
 while (tmp2>0)
 {
 length++;
 tmp2/=10;
 }
 int tmp3=tmp/pow (10,length/2) ; //ดึงส่วนข้างหน้าหลักกลางออกมา
 int tmp4= (length%2==0) ?tmp-tmp3* pow (10,length/2) +1: tmp-tmp3* pow (10,length/2) ;//ดึงส่วนข้างหลังหลักกลางออกมา
 int out = tmp3* pow (10,length/2) +tmp4; ที่ นำหลักตรงกลางออกแล้ว
 return out;
 }
ปัญหาของ middle-square method คือท้ายที่สุดแล้ว จะมีการซ้ำกับลำดับสุ่มซึ่งสร้างขึ้นก่อนหน้า บางอันจะทำให้เกิดการวนซ้ำเร็วมากเช่น 00000 ซึ่งถ้านำไปทดลองทำตามวิธีนี้จะพบว่า ตัวเลขสุ่มที่ได้ทุกครั้งคือ 0000000000 ซึ่งฟอน นอยมันน์ ก็ตระหนักถึงปัญหาดังกล่าวเช่นกัน แต่เขาคิดว่ามันเพียงพอแล้วกับวัตถุประสงค์ในการใช้งานของเขา เขาได้ใช้กลวิธีการทางคณิตศาสตร์บางอย่างในการคาดเดาล่วงหน้าก่อนจะใส่เป็น ตัวตั้งต้น ซึ่งจะสามารถซ่อนข้อผิดพลาดดังกล่าวไว้ได้ ต่อมา middle-square method ถูกแทนที่จากวิธีการอื่นซึ่งซับซ้อนและมีความละเอียดอ่อนมากกว่าซึ่งลำดับสุ่มเสมือนที่ได้มีความใกล้เคียงลำดับสุ่มแท้จริงมากกว่า

คาบของการวนซ้ำของ ตัวสร้างเลขสุ่มเทียม

ตัวสร้างเลขสุ่มเทียม เริ่มต้นจากสถานะเริ่มต้นอะไรก็ได้โดยใช้สถานะ seed (สถานะเริ่มต้น) เป็นตัวเริ่มต้นของตัวสร้างเลขสุ่มเทียม ซึ่งทำให้เกิดการวนซ้ำของลำดับได้โดยความยาวสูงสุดของลำดับสุ่มเสมือนก่อนเกิดการซ้ำเกิดขึ้นถูกวัดจากขนาดของสถานะซึ่งวัดได้โดยความยาวของบิต ความยาวคาบของการวนซ้ำสูงสุดจะยาวเพิ่มเป็น 2 เท่าทุก 1บิตที่เพิ่มขึ้นจึงทำให้ง่ายที่จะสร้าง ตัวสร้างเลขสุ่มเทียม ที่มีคาบการวนซ้ำที่ยาวเพียงพอสำหรับหลายๆโปรแกรมในทางปฏิบัติ ถ้าสถานะของ ตัวสร้างเลขสุ่มเทียม มี n บิต คาบการวนซ้ำจะไม่ยาวเกินกว่า 2ⁿ เช่น เรจิสเตอร์เลื่อนป้อนกลับได้เชิงเส้นLinear Feedback Shift Registers (LFSRs) โดยปกติจะถูกทำให้มีคาบการวนซ้ำที่มีความยาวแน่นอนคือ2ⁿ−1. ตัวสร้างสมภาคเชิงเส้นLinear congruential generators มีคาบการวนซ้ำซึ่งสามารถคำนวณได้จากการหาตัวประกอบ มิกซ์ Mixes (ไม่มีข้อบังคับ) มีคาบการวนซ้ำโดยเฉลี่ย 2n/2 มิกซ์ Mixes (ซึ่งสามารถย้อนกลับได้) มีคาบการวนซ้ำโดยเฉลี่ย 2ⁿ ถึงแม้ว่า ตัวสร้างเลขสุ่มเทีย จะมีการซ้ำของผลลัพธ์หลังจากถึงคาบการวนซ้ำแต่การเจอตัวซ้ำไม่ได้หมายความว่ามันครบคาบการวนซ้ำเสมอไปเพราะคาบการวนซ้ำที่แท้จริงอาจจะยาวกว่านี้

ตัวสร้างเลขสุ่มเทียม (PRNG) กับการเข้ารหัส

ลำดับสุ่มเสมือนส่วนใหญ่ที่ได้จากขั้นตอนวิธีตัวสร้างเลขสุ่มเทียมเป็นหนึ่งในแกนกลางทั้งทางทฤษฏีและทางปฏิบัติของการเข้ารหัส (Cryptography) 
ไม่ว่าจะมีวิธีการหรือไม่มีวิธีการในการจำแนกลำดับสุ่มเสมือนคุณภาพสูงของตัวสร้างเลขสุ่มเทียมออกจากลำดับสุ่มแท้จริงโดยที่ยังไม่รู้ขั้นตอนวิธีที่ใช้และยังไม่รู้สถานะเริ่มต้นที่ใช้ 
ความมั่นคงและระเบียบวิธีการในการเข้ารหัสของขั้นตอนวิธีตัวสร้างเลขสุ่มเทียม มี่ใช้กันส่วนมากตั้งอยู่บนสมมุติฐานที่ว่าเป็นไปไม่ได้ที่จะแยกลำดับสุ่มเสมือนจากการใช้งานของตัวสร้างเลขสุ่มเทียมที่เหมาะสมออกจากลำดับสุ่มแท้จริงได้  ตัวอย่างหนึ่งที่เห็นได้ชัดคือ กระแสข้อมูลรหัส (stream ciphers) ซึงส่วนมากทำงานโดยใช้ตัวดำเนินการทางตรรกศาสตร์ exclusive or (XOR) ระหว่างข้อความปกติกับผลลัพธ์จากตัวสร้างเลขสุ่มเทียม ผลิต ข้อความรหัส (ciphertext) ออกมา การออกแบบ ตัวสร้างเลขสุ่มเทียม  ที่สามารถเข้ารหัสได้อย่างเพียงพอต่อความต้องการในปัจจุบันนี้เป็นสิ่งที่ยากอย่างสุดสุดเพราะว่า ตัวสร้างเลขสุ่มเทียม ที่ออกแบบนี้นอกจากจะต้องสอดคล้องกฎเกณฑ์ข้อกำหนดพื้นฐานสำหรับตัวสร้างเลขสุ่มเทียมทั่วไปที่ไม่ได้ใช้เข้ารหัสแล้วยังต้องสอดคล้องกับกฎเกณฑ์ข้อกำหนดต่างๆเพิ่มเติมเพื่อเป็นเครื่องยืนยันว่าสามารถใช้เข้ารหัสได้อย่างเพียงพอ

ตัวสร้างเลขสุ่มเทียม (PRNG) ในการเข้ารหัสที่ปลอดภัย

ตัวสร้างเลขสุ่มเทียม ที่เหมาะสำหรับใช้งานในการเข้ารหัส ถูกเรียกว่า ตัวสร้างเลขสุ่มเทียมที่มีความมั่นคงเชิงรหัส cryptographically secure PRNG (CSPRNG)  ขณะที่ ตัวสร้างเลขสุ่มเทียม ทั่วๆไป แค่ผ่านการทดสอบทางสถิติจำนวนหนึ่งก็พอ ส่วน ตัวสร้างเลขสุ่มเทียมที่มีความมั่นคงเชิงรหัส ต้องผ่านการทดสอบทางสถิติทั้งหมดและต้องอยู่ภายในเวลาแบบ ฟังก์ชันพหุนาม กับขนาดของ ค่าเริ่มต้น (seed) ถึงแม้ว่าคุณสมบัติดังกล่าวจะไม่สามารถพิสูจน์ได้ในทางปฏิบัติก็ตาม เราก็ยังสามารถแสดงหลักฐานข้อพิสูจน์ที่แข็งแรงเพียงพอให้เห็นได้ว่าตัวสร้างเลขสุ่มเทียมที่สร้างขึ้นมีความมั่นคงเชิงรหัสหรือไม่ โดยลดรูปคุณสมบัติดังกล่าวไปสู่ปัญหาที่ยากๆทางคณิตศาสตร์ที่เป็นที่รู้ๆกันซึ่งเป็นหนึ่งในกลุ่มปัญหา NP เช่น การแยกตัวประกอบจำนวนเต็มที่มีหลายๆหลัก โดยปกติแล้วต้องใช้เวลาหลายปีในการตรวจสอบกว่าจะสามารถยืนยันได้ว่าขั้นตอนวิธีตัวสร้างเลขสุ่มเทียมใดๆนั้นจะเป็น ตัวสร้างเลขสุ่มเทียมที่มีความมั่นคงเชิงรหัสหรือไม่

การแจกแจงไม่เอกรูป (Non-Uniform Distribution)

ตัวเลขที่เลือกมาจากการแจกแจงความน่าจะเป็นที่ไม่เอกรูป สามารถสร้างโดยใช้การแจกแจงเอกรูป (uniform distribution ) ตัวสร้างเลขสุ่มเทียม PRNG และ function ที่เกี่ยวข้องกับการแจกแจง 2 ประเภท