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

ตัวสร้างเลขสุ่มเทียม (อังกฤษ: pseudorandom number generator: PRNG) มีความสำคัญในทางคณิตศาสตร์ การเข้ารหัส และการเสี่ยงโชค ตัวสร้างเลขสุ่มเทียมมีทั้งได้จาก ฮาร์ดแวร์ ซึ่งเป็นการสุ่มแท้ และจากซอฟต์แวร์ซึ่งเป็นการสุ่มเทียม (pseudorandomness) ในที่นี้จะกล่าวถึงแต่ตัวสร้างเลขสุ่มเทียมจากซอฟต์แวร์

คำอธิบาย

ตัวสร้างเลขสุ่มเทียม หรือที่รู้จักกันในนาม ตัวสร้างบิตสุ่มแบบกำหนดได้ (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 (ไม่มีข้อบังคับ) มีคาบการวนซ้ำโดยเฉลี่ย 2^n/2 มิกซ์ Mixes (ซึ่งสามารถย้อนกลับได้) มีคาบการวนซ้ำโดยเฉลี่ย 2ⁿ ถึงแม้ว่า ตัวสร้างเลขสุ่มเทีย จะมีการซ้ำของผลลัพธ์หลังจากถึงคาบการวนซ้ำแต่การเจอตัวซ้ำไม่ได้หมายความว่ามันครบคาบการวนซ้ำเสมอไปเพราะคาบการวนซ้ำที่แท้จริงอาจจะยาวกว่านี้

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

 

ตัวอย่างของตัวสร้างเลขสุ่มเทียม Pseudo Random Generator Shift register

 

4 บิต Fibonacci LFSR พร้อมกับแผนภาพแสดงสถานะ

 

16 บิต Fibonacci LFS

 

16 บิต Galois LFSR

• ตัวสร้างเลขสุ่มเทียมแบบบลัมบลัมชับ
• Inversive congruential generator
• ISAAC
• Lagged Fibonacci generator
• Linear congruential generators
• Linear Feedback Shift Registers (LFSRs)
• Mersenne twister
• Multiply-with-carry
• Naor-Reingold Pseudorandom Function
• Park–Miller random number generator
• Maximal periodic reciprocals
• Well Equidistributed Long-period Linear
• Xorshift Xorshift

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

• Block_ciphers in counter mode
• Cryptographic hash function in counter mode
• Stream ciphers

PRNG APIS ที่มีชื่อเสียง

• Random class in the Java programming language
• SecureRandom class in the Java programming language

PRNG ที่ใช้ External entropy

• CryptGenRandom - Microsoft Windows
• Fortuna_(PRNG)
• Yarrow_algorithm - Mac OS X and FreeBSD
• /dev/random - Linux and Unix
• LavaRnd - The open-source (LGPL) successor to Lavarand
• HotBits
• random.org

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

วิธีตัดกลางของผลคูณ (Midproduct Method)

• 1.) เลือกตัวเลขสี่หลัก 2 ค่า x'₀ และ x₀
• 2.) คูณค่า x'₀ และ x₀ เข้าด้วยกัน
• 3.) ใชสี่หลักกลางของผลคูณที่ได้ในข้อ 2.) เป็นตวัเลขสุ่มเทียม x₁
• 4.) คูณ ค่า x₀ และ x₁
• 5.) ทำซ้ำขั้นตอน 3.) และ 4.) จนกว่าจะได้ตัวเลขสุ่มเท่าจำนวนที่ต้องการ

วิธีตัวคูณคงที่ (Constant Multiplier Technique

• 1.) กำหนดค่าคงที่ k ขนาดสี่หลัก และค่าเริ่มต้น x₀
• 2.) คูณค่า k และ x₀ เข้าด้วยกัน
• 3.) ใชสี่หลักกลางของผลคูณที่ได้ในข้อ 2.) เป็นตัวเลขสุ่มเทียม x₁
• 4.) คูณ ค่า k และ x₁
• 5.) ทำซ้ำขั้นตอน 3.) และ 4.) จนกว่าจะได้ตัวเลขสุ่มเท่าจำนวนที่ต้องการ

วิธีการบวกเศษเหลือ (Additive Congruent Method)

• 1.) กำหนดตวัเลขจำนวนเต็ม x₁, x₂,..., x_n
• 2.) สร้าง x_n+1, x_n+2, ... จากตyวเลขในข้อ 1.)
• 3.) สร้างตัวเลขสุ่มเทียมโดยใช้สูตร
• x_i= (x_i-1+x_i-n) (mod m)
• R_i-n= x_i/m

วิธีการใช้เศษเหลือ (Congruent Method)

• วิธีการที่นิยมใช้ที่สุดในการสร้างตัวเลขแบบสุ่มคือการใช้เศษเหลือของผลคูณ (Multiplicative Congruential Method)
• โดยใช้สูตร x_i+1 =ax_i (mod m)
• ด้วยการกำหนดค่าให้ a และ m ซึ่งจะต้องไม่เป็นค่าลบและกำาหนดค่าเริ่มต้น x₀

เวลาในการทำงาน หน่วยความจำที่ใช้ หรือ การพิสูจน์ความถูกต้อง

• ขึ้นกับแต่ละขั้นตอนวิธี เพราะขั้นตอนวิธีต่างกันจะมี เวลาในการทำงาน และ หน่วยความจำที่ใช้ต่างกัน การพิสูจน์ความถูกต้องของ ตัวสร้างเลขสุ่มเทียม แต่ละขั้นตอนวิธีก็ต่างกันด้วย

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

• คาบเวลาการซ้ำสั้นกว่าที่คาดเอาไว้สำหรับบางสถานะ seed (สถานะเริ่มต้น)
• ขาดเอกรูป (Non-Uniform) ในการแจกแจงลำดับสุ่มเสมือนที่สร้างขึ้นมาเมื่อสร้างตัวเลขสุ่มมาแล้วเป็นจำนวนมาก
• เกิดความสัมพันธ์กับค่าที่อยู่ติดกันซึ่งอาจทำให้ผู้โจมตีสามารถคาดเดาตัวต่อไปซึ่งเป็นรหัสที่ถูกต้องได้
• การแจกแจงที่มีมิติหรือขอบเขตที่ไม่ดี (poor dimension) ในลำดับสุ่มเสมือนที่ได้จาก ตัวสร้างเลขสุ่มเทียม
   

  ปริภูมิ 3 มิติ ของ 100,000 ค่าที่สร้างขึ้นมาด้วย แรนดูRANDU โดยจุดแต่ละจุดแสดง 3 ลำดับย่อยของตัวเลขสุ่มเทียม

จุดบกพร่องเหล่านี้มีตั้งแต่ไม่สามารถสังเกตเห็นได้จนกระทั่งสามารถเห็นได้อย่างชัดเจน ตัวอย่างหนึ่งก็คือ แรนดู RANDU ซึ่งเป็นขั้นตอนวิธีในการสร้างเลขสุ่มเทียมที่ใช้กันมากว่าทศวรรตบน คอมพิวเตอร์ mainframe ซึ่งไม่สมบูรณ์แบบอย่างมากๆ แต่เนื่องด้วยสมัยนั้นวิทยาการในการตรวจสอบที่มียังมีไม่เพียงพอ ทำให้ความไม่สมบุร์ณ์แบบดังกล่าวไม่ถูกตรวจพบเป็นระยะเวลายาวนาน อีกตัวอย่างหนึ่งของปัญหาก็คือ การวิจัยในหลายๆสาขาในช่วงเวลาดังกล่าวซึ่งอาศัย การเลือกแบบสุ่ม การจำลองแบบ วิธีมอนติคาโล Monte Carlo method หรือในทางอื่นๆ ได้ผลการวิจัยที่มีความน่าเชื่อถือน้อยกว่าที่มันควรจะเป็น

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

ลำดับสุ่มเสมือนส่วนใหญ่ที่ได้จากขั้นตอนวิธีตัวสร้างเลขสุ่มเทียมเป็นหนึ่งในแกนกลางทั้งทางทฤษฏีและทางปฏิบัติของการเข้ารหัส (Cryptography) ไม่ว่าจะมีวิธีการหรือไม่มีวิธีการในการจำแนกลำดับสุ่มเสมือนคุณภาพสูงของตัวสร้างเลขสุ่มเทียมออกจากลำดับสุ่มแท้จริงโดยที่ยังไม่รู้ขั้นตอนวิธีที่ใช้และยังไม่รู้สถานะเริ่มต้นที่ใช้

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

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

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

รายการของตัวสร้างเลขสุ่มเทียมที่มีความมั่นคงเชิงรหัส (CSPRNG)

• Stream ciphers
• Block ciphers running in counter or output feedback mode
• ตัวสร้างเลขสุ่มเทียมที่ได้รับการอออกแบบมาเป็นอย่างดีสำหรับใช้ในการเข้ารหัสโดยเฉพาะ
  • Microsoft's Cryptographic Application Programming Interface function CryptGenRandom
  • Yarrow algorithm (incorporated in Mac OS X and FreeBSD)
  • Fortuna
• การผสมผสานระหว่าง ขั้นตอนวิธีตัวสร้างเลขสุ่มเทียม ดั้งเดิมหลายๆตัวโดยมีเป้าหมายในการกำจัดลำดับที่ดูเหมือนว่าไม่ได้ถูกสุ่มออกไป
• การออกแบบ ขั้นตอนวิธี ชนิดพิเศษที่ตั้งอยู่บนสมมุติฐานอย่างยากทางคณิตศาสตร์ เช่น Micali-Schnorr, ขั้นตอนวิธีBlum Blum Shub ซึ่งได้พิสูจน์ความมั่นคงของรหัสได้เป็นอย่างดีไว้แล้ว ขั้นตอนวิธี เหล่านี้จะใช้เวลาช้ากว่า ตัวสร้างเลขสุ่มเทียม แบบอื่นและใช้งานไม่ได้ในทางปฏิบัติด้านอื่นๆนอกจากใช้ในการเข้ารหัสเท่านั้น

BSI evaluation criteria

หน่วยงานความมั่นคงทางสารสนเทศของเยอรมัน (The German Federal Office for Information Security: BSI) ได้จัดตั้งกฎเกณฑ์ในการกำหนดคุณภาพของตัวสร้างเลขสุ่มเทียมขึ้นดังนี้

• K1 ลำดับสุ่มเสมือนซึ่งมีโอกาสต่ำที่หลักที่อยู่ติดกันจะมีค่าซ้ำกัน
• K2 ลำดับสุ่มเสมือนซึ่งไม่สามารถแยกจากลำดับสุ่มแท้จริงด้วยการทดสอบทางสถิติที่แน่ชัด การทดสอบโมโนบิต monobit test (จำนวนที่เท่ากันของเลขศูนย์และเลขหนึ่งในลำดับ), การทดสอบโปกโกอร์ poker test (ตัวอย่างพิเศษของ chi-square test), การทดสอบการวิ่งruns test (นับจำนวนความถี่ของการวิ่งของความยาวที่ต่างๆกัน), การทดสอบการวิ่งระยะยาว longruns test (ตรวจสอบการวิ่ว่ามี ความยาวมากกว่า 34 or หรือใหญ่กว่า 20 000 bits ในลำดับหรือไม่ — both from BSI2 (AIS 20, v. 1, 1999) and FIPS (140-1, 1994), และ การทดสอบความผิดพลาดอันเนื่องมากจากความสัมพันธ์autocorrelation test ใจความสำคัญของการทดสอบเหล่านี้คือลำดับย่อยใดๆที่เลือกมาจะต้องไม่มีข้อมูลใดของตัวถัดไปของลำดับปรากฏอยู่
• K3 สำหรับในทางปฏิบัติเป็นไปไม่ได้ที่ผู้โจมตีใดๆจะคำนวณหรือเดาตัวเลขสุ่มได้จากลำดับย่อยใดๆที่ได้มา ตัวก่อนหน้าหรือตัวถัดไปของลำดับ หรือจากสถานะใดๆของ ตัวสร้างเลขสุ่มเทียม
• K4 สำหรับในทางปฏิบัติเป็นไปไม่ได้ที่ผู้โจมตีใดๆจะคำนวณหรือเดาตัวเลขสุ่มได้จาก สถานะภายในของตัวสร้างเลขสุ่มเทียม ตัวก่อนหน้าหรือตัวถัดไปของลำดับ หรือ สถานะก่อนหน้าใดๆของ ตัวสร้างเลขสุ่มเทียม

สำหรับโปรแกรมในการเข้ารหัสตัวสร้างเลขสุ่มเทียม (PRNG) ที่ครบตามเงื่อนไขของมาตรฐาน K3 or K4 เท่านั้นที่ยอมรับได้ว่าเป็นตัวสร้างเลขสุ่มเทียมที่มีความมั่นคงเชิงรหัส (CSPRNG)

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

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

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

1: cumulative distribution function ${\displaystyle F(b)}$  ของ${\displaystyle f(b)}$ :

${\displaystyle F(b)=\int _{-\infty }^{b}f(b')db'}$ 

${\displaystyle 0=F(-\infty )\leq F(b)\leq F(\infty )=1}$ . เลือก c แบบสุ่มจากการแจกแจงเอกรูปและหาความหนาแน่นของความน่าจะเป็นจะได้

${\displaystyle F(b)=c}$ 

ดังนั้น

${\displaystyle b=F^{-1}(c)}$ 

คือตัวเลขแบบสุ่มที่ได้จากการแจกแจง${\displaystyle f(b)}$ .

2: ตัวผกผัน Cumulative Gaussian distribution

${\displaystyle \operatorname {erf} ^{-1}(x)}$  พร้อมกับ ตัวสร้างเลขสุ่มเทียม เอกรูปแบบอุดมคติในช่วง (0, 1) เป็น input x จะให้ลำดับของค่าบวกซึ่งเป็นการแจกแจงแบบ Gaussian distribution ออกมา

• เมื่อใช้ในทางปฏิบัติการแสดงตัวเลขจะต้องมีการตัดหางที่ยาวไม่มีที่สิ้นสุดของการแจกแจงให้เป็นค่าที่มี่ที่สิ้นสุด
• การคำนวณซ้ำหลายครั้ง${\displaystyle \operatorname {erf} ^{-1}(x)}$ ควรถูกลดให้เป็นแบบ Ziggurat algorithm เพื่อความเร็วที่มากขึ้นของการสร้างด้วยหลักการที่คล้ายกับการแจกแจงเรย์ลี (Rayleigh distribution) และการแจกแจงปัวซง (Poisson distribution) ก็สามารถนำมาใช้ในการสร้างการแจกแจงแบบไม่เอกรูปได้เช่นกัน

โปรแกรมประยุกต์และการประยุกต์ใช้งานในด้านอื่นๆ

• KeyPass
• QFX keyscramble
• โปรแกรมสุ่มเลขบัตรประจำตัวประชาชน-สุ่มเลขบัตรประชาชนสำหรับใช้ในการสมัครสมาชิกเว็บต่างๆ เพื่อความปลอดภัยของผู้สมัครสมาชิก
• Passward Generator
• การพยากรอากาศ
• การทำนายอนาคต
• GPS สามารถหาเวลาที่ต่างกันระหว่างเครื่องรับกับดาวเทียมได้อย่างมีประสิทธิภาพและมีราคาไม่แพงทำให้กลายเป็นเครื่องมือที่ทุกคนสามารถใช้ได้
• การโคจรของดาวเทียม ดาวเทียมทุกดวงสามารถใช้คลื่นความถี่เดียวกันได้ โดยไม่เกิดการรบกวนต่อกัน ดาวเทียมแต่ละดวงจะมี Pseudo Random code เป็นของเฉพาะตัว ดังนั้นเวลาเครื่องรับนำรหัสมาใช้ต้องให้ถูกตามหมายเลขดาวเทียม
• ทฤษฏีความโกลาหลChaos theory ปรากฏการณ์ที่ดูเหมือนว่าเกิดขึ้นอย่างสะเปะสะปะแต่ที่จริงแล้วแฝงไปด้วยความเป็นระเบียบ
• วิธีการชนะที่รูเล็ตคาสิโนออนไลน์ จากจุดบกพร่องของตัวสร้างเลขสุ่มเทียมของ คาสิโนออนไลน์

ดูเพิ่ม

• Pseudorandom binary sequence
• Random number generator attack
• Quisi random
• Pseudorandom generator theorem
• Pseudorandom function
• Chaos_theory

อ้างอิง

• Michael Luby, Pseudorandomness and Cryptographic Applications, Princeton Univ Press, 1996. A definitive source of techniques for provably random sequences.
• Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Chapter 3, pp. 1–193.

Extensive coverage of statistical tests for non-randomness.

• R. Matthews Maximally Periodic Reciprocals Bulletin of the Institute of Mathematics and its Applications 28 147-148 1992
• J. Viega, Practical Random Number Generation in Software, in Proc. 19th Annual Computer Security Applications Conference, Dec. 2003.
• John von Neumann, "Various techniques used in connection with random digits," in A.S. Householder, G.E. Forsythe, and H.H. Germond, eds., Monte Carlo Method, National Bureau of Standards Applied Mathematics Series, 12 (Washington, D.C.: U.S. Government Printing Office, 1951) : 36-38.
• NIST Recommendation for Random Number Generation Using Deterministic Random Bit Generators
• Luc Devroye (1986). Non-Uniform Random Variate Generation. New York: Springer-Verlag.
• http://www.tuct.ac.th/Computer/sm/Chapter3.pdf
• http://www.gpsthaionline.com/index.php?option=com_content&view=article&id=96:gps-pseudo-random-code&catid=26:gps-articles&Itemid=57
• http://www.slideshare.net/ApplesMountain/chaos-theory-4968454
• http://www.shmatsunaga.com/?p=395