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

ตัวสร้างเลขสุ่มเทียม  คือตัวสร้างเลขสุ่มประเภทหนึ่ง มีความสำคัญในทางคณิตศาสตร์ การเข้ารหัส และการเสี่ยงโชค ตัวสร้างเลขสุ่มเทียมมีทั้งได้จากฮาร์ดแวร์ซึ่งเป็นการสุ่มแท้ และจากซอฟต์แวร์ซึ่งเป็นการสุ่มเทียม (pseudorandomness)
คำอธิบาย.
ตัวสร้างเลขสุ่มเทียมหรือที่รู้จักกันในชื่อตัวสร้างบิตสุ่มแบบกำหนดได้ (Deterministic random bit generator: DRBG) เป็นขั้นตอนวิธีสำหรับใช้ในการสร้างลำดับของตัวเลขที่มีความใกล้เคียงกับคุณสมบัติของการสุ่ม ถึงลำดับตัวเลขที่ได้จากขั้นตอนวิธีตัวสร้างเลขสุ่มเทียมนี้จะใกล้เคียงกับลำดับเลขสุ่มแท้จริง แต่ก็ไม่ได้เป็นลำดับตัวเลขแบบสุ่มที่แท้จริงเนื่องจากลำดับตัวเลขที่ได้ออกมาจากตัวสร้างเลขสุ่มเทียมทั้งหมดได้มาจากกลุ่มเล็ก ๆ ของค่าเริ่มต้นที่กำหนดให้เป็นตัวตั้งต้น (seed) ของตัวสร้างเลขสุ่มเทียม ถึงจะมีตัวสร้างเลขสุ่มจากฮาร์ดแวร์ที่สามารถนำมาสร้างลำดับสุ่มแท้ได้ แต่ลำดับสุ่มเสมือนที่ได้จากตัวสร้างเลขสุ่มเทียมเองก็มีความสำคัญในทางปฏิบัติหลาย ๆ อย่าง ทั้งในด้านการจำลอง เช่นระบบกายภาพที่ใช้วิธีมอนเตการ์โล ในด้านการเข้ารหัสลับ (cryptography) ในด้านการก่อกำเนิดกระบวนคำสั่ง (procedural generation) ส่วนใหญ่เกี่ยวข้องกับคอมพิวเตอร์กราฟิกส์ (โปรแกรมประยุกต์และวิดีโอเกมขั้นออกแบบ) ขั้นตอนวิธีเชิงสุ่มมากมายเองก็ได้อิทธิพลมาจากตัวสร้างเลขสุ่มเทียมเป็นส่วนหนึ่งในการแก้ปัญหา นอกจากการใช้งานแล้วการพิสูจน์ว่าตัวสร้างเลขสุ่มเทียมใช้งานได้จริงก็มีความสำคัญไม่แพ้กัน ซึ่งการพิสูจน์นี้ต้องอาศัยการวิเคราะห์ทางคณิตศาสตร์อย่างระมัดระวังในการทำให้แน่ใจได้ว่าตัวสร้างเลขสุ่มเทียมได้สร้างลำดับสุ่มเสมือนที่มีลักษณะสุ่มเพียงพอสำหรับการใช้งาน
ประวัติ.
ตัวสร้างเลขสุ่มเทียมที่อาศัยคอมพิวเตอร์ยุคแรก ๆ คิดค้นโดย จอห์น ฟอน นอยมันน์ ในปี ค.ศ. 1946 รู้จักกันในนามของ วิธีมิดเดิลสแควร์ (middle-square method) ขั้นตอนวิธีนี้คือ รับตัวเลขใดเข้ามาเป็นตัวตั้งต้นก็นำตัวเลขนั้นมายกกำลังด้วย 2 แล้วนำหลักตรงกลางออกจากผลลัพธ์ที่ได้ ก็จะได้ตัวเลขสุ่มขึ้นมาตามต้องการ ซึ่งสามารถนำตัวเลขนี้มาเป็นตัวตั้งต้นในการสร้างตัวเลขสุ่มอื่น ๆ ต่อไปได้
รหัสเทียม.
Input เป็นตัวเลข 
Output ยกกำลังสอง Input ที่นำตัวเลขตำแหน่งกลางออก
ปัญหาของ คือท้ายที่สุดแล้วจะซ้ำกับลำดับสุ่มซึ่งสร้างขึ้นก่อนหน้า บางอันจะทำให้เกิดการวนซ้ำเร็วมากเช่น 00000 ซึ่งถ้านำไปทดลองทำตามวิธีนี้จะพบว่าได้ 0000000000 ทุกครั้ง ซึ่งฟอน นอยมันน์ ก็ตระหนักถึงปัญหาดังกล่าวเช่นกัน แต่เขาคิดว่ามันเพียงพอแล้วกับวัตถุประสงค์ในการใช้งานของเขา เขาได้ใช้กลวิธีการทางคณิตศาสตร์บางอย่างในการคาดเดาล่วงหน้าก่อนจะใส่เป็นตัวตั้งต้นซึ่งจะสามารถซ่อนข้อผิดพลาดดังกล่าวไว้ได้ ต่อมา ถูกแทนที่จากวิธีการอื่นที่ซับซ้อนและมีความละเอียดอ่อนมากกว่าซึ่งลำดับสุ่มเสมือนที่ได้มีความใกล้เคียงลำดับสุ่มแท้จริงมากกว่า
คาบการวนซ้ำ.
ตัวสร้างเลขสุ่มเทียมเริ่มต้นจากสถานะเริ่มต้นอะไรก็ได้โดยใช้สถานะ seed (สถานะเริ่มต้น) เป็นตัวเริ่มต้นของตัวสร้างเลขสุ่มเทียม ซึ่งทำให้เกิดการวนซ้ำของลำดับได้โดยความยาวสูงสุดของลำดับสุ่มเสมือนก่อนเกิดการซ้ำเกิดขึ้นถูกวัดจากขนาดของสถานะซึ่งวัดได้โดยความยาวของบิต ความยาวคาบของการวนซ้ำสูงสุดจะยาวเพิ่มเป็น 2 เท่าทุก 1 บิตที่เพิ่มขึ้นจึงทำให้ง่ายที่จะสร้าง ตัวสร้างเลขสุ่มเทียมที่มีคาบการวนซ้ำที่ยาวเพียงพอสำหรับหลาย ๆ โปรแกรมในทางปฏิบัติ ถ้าสถานะของตัวสร้างเลขสุ่มเทียมมี n บิต คาบการวนซ้ำจะไม่ยาวเกินกว่า 2n เช่น เรจิสเตอร์เลื่อนป้อนกลับได้เชิงเส้น (LFSRs) โดยปกติจะถูกทำให้มีคาบการวนซ้ำที่มีความยาวแน่นอนคือ 2n−1 ตัวสร้างสมภาคเชิงเส้น มีคาบการวนซ้ำซึ่งสามารถคำนวณได้จากการหาตัวประกอบ มิกซ์ Mixes (ไม่มีข้อบังคับ) มีคาบการวนซ้ำโดยเฉลี่ย 2n/2 มิกซ์ Mixes (ซึ่งสามารถย้อนกลับได้) มีคาบการวนซ้ำโดยเฉลี่ย 2n ถึงแม้ว่าตัวสร้างเลขสุ่มเทียมจะมีการซ้ำของผลลัพธ์หลังจากถึงคาบการวนซ้ำแต่การเจอตัวซ้ำไม่ได้หมายความว่ามันครบคาบการวนซ้ำเสมอไปเพราะคาบการวนซ้ำที่แท้จริงอาจจะยาวกว่านี้
ปัญหา.
จุดบกพร่องเหล่านี้มีตั้งแต่ไม่สามารถสังเกตเห็นได้จนกระทั่งสามารถเห็นได้อย่างชัดเจน ตัวอย่างหนึ่งก็คือแรนดู ซึ่งเป็นขั้นตอนวิธีในการสร้างเลขสุ่มเทียมที่ใช้กันมากว่าทศวรรษบนคอมพิวเตอร์ ซึ่งไม่สมบูรณ์แบบ แต่เนื่องด้วยในสมัยนั้นวิทยาการในการตรวจสอบที่มียังมีไม่เพียงพอ ทำให้ความไม่สมบูรณ์แบบดังกล่าวไม่ถูกตรวจพบเป็นระยะเวลายาวนาน อีกตัวอย่างหนึ่งของปัญหาก็คือการวิจัยในหลาย ๆ สาขาในช่วงเวลาดังกล่าวซึ่งอาศัยการเลือกแบบสุ่ม การจำลองแบบวิธีมอนเตการ์โล หรือในทางอื่น ๆ ได้ผลการวิจัยที่มีความน่าเชื่อถือน้อยกว่าที่ควรจะเป็น
กับการเข้ารหัส.
ลำดับสุ่มเสมือนส่วนใหญ่ที่ได้จากขั้นตอนวิธีตัวสร้างเลขสุ่มเทียมเป็นหนึ่งในแกนกลางทั้งทางทฤษฏีและทางปฏิบัติของการเข้ารหัส  
ไม่ว่าจะมีวิธีการหรือไม่มีวิธีการในการจำแนกลำดับสุ่มเสมือนคุณภาพสูงของตัวสร้างเลขสุ่มเทียมออกจากลำดับสุ่มแท้จริงโดยที่ยังไม่รู้ขั้นตอนวิธีที่ใช้และยังไม่รู้สถานะเริ่มต้นที่ใช้ 
ความมั่นคงและระเบียบวิธีการในการเข้ารหัสของขั้นตอนวิธีตัวสร้างเลขสุ่มเทียม มีใช้กันส่วนมากตั้งอยู่บนสมมุติฐานที่ว่าเป็นไปไม่ได้ที่จะแยกลำดับสุ่มเสมือนจากการใช้งานของตัวสร้างเลขสุ่มเทียมที่เหมาะสมออกจากลำดับสุ่มแท้จริงได้ ตัวอย่างหนึ่งที่เห็นได้ชัดคือ กระแสข้อมูลรหัส  ซึ่งส่วนมากทำงานโดยใช้ตัวดำเนินการทางตรรกศาสตร์ (XOR) ระหว่างข้อความปกติกับผลลัพธ์จากตัวสร้างเลขสุ่มเทียมผลิตข้อความรหัส  ออกมา การออกแบบตัวสร้างเลขสุ่มเทียม ที่สามารถเข้ารหัสได้อย่างเพียงพอต่อความต้องการในปัจจุบันนี้เป็นสิ่งที่ยากอย่างสุดสุดเพราะว่า ตัวสร้างเลขสุ่มเทียม ที่ออกแบบนี้นอกจากจะต้องสอดคล้องกฎเกณฑ์ข้อกำหนดพื้นฐานสำหรับตัวสร้างเลขสุ่มเทียมทั่วไปที่ไม่ได้ใช้เข้ารหัสแล้วยังต้องสอดคล้องกับกฎเกณฑ์ข้อกำหนดต่าง ๆ เพิ่มเติมเพื่อเป็นเครื่องยืนยันว่าสามารถใช้เข้ารหัสได้อย่างเพียงพอ
ในการเข้ารหัสที่ปลอดภัย.
ตัวสร้างเลขสุ่มเทียมที่เหมาะสำหรับใช้งานในการเข้ารหัส เรียกว่าตัวสร้างเลขสุ่มเทียมที่มีความมั่นคงเชิงรหัส ขณะที่ตัวสร้างเลขสุ่มเทียมทั่ว ๆ ไปนั้นแค่ผ่านการทดสอบทางสถิติจำนวนหนึ่งก็พอ ส่วนตัวสร้างเลขสุ่มเทียมที่มีความมั่นคงเชิงรหัสต้องผ่านการทดสอบทางสถิติทั้งหมดและต้องอยู่ภายในเวลาแบบฟังก์ชันพหุนามกับขนาดของค่าเริ่มต้น (seed) ถึงแม้ว่าคุณสมบัติดังกล่าวจะไม่สามารถพิสูจน์ได้ในทางปฏิบัติก็ตาม เรายังสามารถแสดงหลักฐานข้อพิสูจน์ที่แข็งแรงเพียงพอให้เห็นได้ว่าตัวสร้างเลขสุ่มเทียมที่สร้างขึ้นมีความมั่นคงเชิงรหัสหรือไม่ โดยลดรูปคุณสมบัติดังกล่าวไปสู่ปัญหาที่ยากทางคณิตศาสตร์ที่เป็นที่รู้จักกันซึ่งเป็นหนึ่งในกลุ่มปัญหา เช่นการแยกตัวประกอบจำนวนเต็มที่มีหลาย ๆ หลัก โดยปกติแล้วต้องใช้เวลาหลายปีในการตรวจสอบกว่าจะสามารถยืนยันได้ว่าขั้นตอนวิธีตัวสร้างเลขสุ่มเทียมใด ๆ นั้นจะเป็นตัวสร้างเลขสุ่มเทียมที่มีความมั่นคงเชิงรหัสหรือไม่
BSI evaluation criteria.
หน่วยงานความมั่นคงทางสารสนเทศของเยอรมัน (BSI) ได้จัดตั้งกฎเกณฑ์ในการกำหนดคุณภาพของตัวสร้างเลขสุ่มเทียมขึ้นดังนี้
สำหรับโปรแกรมในการเข้ารหัสตัวสร้างเลขสุ่มเทียม (PRNG) ที่ครบตามเงื่อนไขของมาตรฐาน K3 หรือ K4 เท่านั้นที่ยอมรับได้ว่าเป็นตัวสร้างเลขสุ่มเทียมที่มีความมั่นคงเชิงรหัส (CSPRNG)
การใช้งาน.
การแจกแจงไม่เอกรูป (Non-Uniform Distribution).
ตัวเลขที่เลือกมาจากการแจกแจงความน่าจะเป็นที่ไม่เอกรูปสามารถสร้างโดยใช้การแจกแจงเอกรูป (uniform distribution) ตัวสร้างเลขสุ่มเทียม PRNG และ function ที่เกี่ยวข้องกับการแจกแจง 2 ประเภท
<math>F (b) =\int_{-\infty}^b f (b') db'</math>
1: <math>F (b) </math> ของ<math>f (b) </math>:.
<math>0=F (-\infty) \leq F (b) \leq F (\infty) =1</math>.
เลือก c แบบสุ่มจากการแจกแจงเอกรูปและหาความหนาแน่นของความน่าจะเป็นจะได้
<math>F (b) =c</math>
ดังนั้น
<math>b=F^{-1} (c) </math>
คือตัวเลขแบบสุ่มที่ได้จากการแจกแจง<math>f (b) </math>.
2: ตัวผกผัน Cumulative Gaussian distribution.
<math>\operatorname{erf}^{-1} (x) </math>
พร้อมกับ ตัวสร้างเลขสุ่มเทียม เอกรูปแบบอุดมคติในช่วง (0, 1) เป็น input x จะให้ลำดับของค่าบวกซึ่งเป็นการแจกแจงแบบ Gaussian distribution ออกมา