ทฤษฎีความซับซ้อนในการคำนวณซึ่งเป็นการศึกษาเกี่ยวกับทรัพยากรทางการคำนวณที่ต้องใช้ในการแก้ปัญหาหนึ่งๆ ได้สร้างแบบจำลองของขั้นตอนวิธีแบบสุ่มให้เป็นเครื่องจักรทัวริงเชิงความน่าจะเป็น ทั้งขั้นตอนวิธีลาสเวกัสและมอนติคาร์โลได้ถูกนำมาพิจารณา รวมถึง "คลาสของความซับซ้อน" หลายๆคลาสก็ได้ถูกนำมาศึกษา คลาสของความซับซ้อนแบบสุ่มแบบที่เป็นพื้นฐานที่สุดคือแบบอาร์พี ซึ่งเป็นคลาสของปัญหาการตัดสินใจที่มีขั้นตอนวิธีแบบสุ่ม (หรือเครื่องจักรทัวริงเชิงความน่าจะเป็น) ที่มีประสิทธิภาพ (ทำงานได้ได้ในเวลาโพลิโนเมียล) ที่สามารถตอบว่า "ไม่" ได้ถูกต้องเสมอ และสามารถตอบว่า "ใช่" ได้ โดยมีโอกาสถูกต้องอย่างน้อย 1/2 คลาสส่วนกลับ (complement) ได้แก่โค-อาร์พี และคลาสของปัญหาซึ่งทั้งคำตอบ "ใช่" และ "ไม่" สามารถมีค่าความน่าจะเป็นได้ทั้งคู่ (นั่นคือ ไม่ได้บังคับให้ต้องตอบถูกต้องเสมอ) เรียกว่าซีพีพี (ZPP) สำหรับปัญหาซึ่ง (เชื่อกันว่า) อยู่นอกคลาสนี้ เช่นปัญหาเอ็นพีแบบยาก (ซึ่งแม้แต่ขั้นตอนวิธีแบบสุ่มก็ไม่สามารถแก้ได้) จำเป็นต้องแก้ด้วยขั้นตอนวิธีการประมาณ

ในประวัติศาสตร์ ขั้นตอนวิธีแบบสุ่มเริ่มเป็นที่รู้จัก จากการค้นพบของมิลเลอร์และราบินในปี ค.ศ. 1976 ว่า ปัญหาการตรวจสอบการเป็นจำนวนเฉพาะของตัวเลข สามารถแก้ได้อย่างมีประสิทธิภาพด้วยขั้นตอนวิธีแบบสุ่ม ในเวลานั้น ยังไม่มีขั้นตอนวิธีดิเทอร์มินิสติกสำหรับปัญหานี้เลย

การตรวจสอบการเป็นจำนวนเฉพาะมิลเลอร์-ราบินนั้น มีหลักการพื้นฐานอยู่บนความสัมพันธ์ทวิภาค ระหว่างจำนวนเต็มบวกสองตัว k และ n ใดๆ ที่สามารถบอกได้ว่า k "เป็นตัวยืนยันการเป็นจำนวนประกอบของ" n เราสามารถแสดงได้ว่า

• ถ้ามีตัวยืนยันการเป็นจำนวนประกอบของ n แล้ว n เป็นจำนวนประกอบ (หมายความว่า n ไม่เป็นจำนวนเฉพาะ) และ
• ถ้า n เป็นจำนวนประกอบแล้ว มีอย่างน้อยสามในสี่ของจำนวนนับที่มีค่าน้อยกว่า n ที่เป็นตัวยืนยันการเป็นจำนวนประกอบของ n ได้ และ
• มีขั้นตอนวิธีที่ทำงานได้รวดเร็วพอ ที่เมื่อให้ค่า k และค่า n ขั้นตอนวิธีสามารถบอกได้ว่า k เป็นตัวยืนยันการเป็นจำนวนประกอบของ n หรือไม่

สังเกตว่าข้อเท็จจริงเหล่านี้ทำให้สรุปได้ว่าปัญหาการทดสอบการเป็นจำนวนเฉพาะอยู่ในโค-อาร์พีสมมุติ n เป็นจำนวนประกอบ ถ้าเราเลือกตัวเลขที่น้อยกว่า n มี 100 ตัว ความน่าจะเป็นที่จะหา "ตัวยืนยัน" ดังกล่าวไม่เจอจะเป็น (1/4) 100 ซึ่งในทางปฏิบัติแล้ววิธีนี้ก็เป็นการทดสอบการเป็นจำนวนเฉพาะที่ใช้ได้วิธีหนึ่ง และอาจจะไม่มีวิธีใดเลยที่ใช้ได้ดีในทางปฏิบัติเมื่อ n มีขนาดใหญ่มาก เราสามารถลดความน่าจะเป็นที่จะเกิดความผิดพลาดให้เหลือเท่าใดก็ได้ โดยการเพิ่มรอบการทำงานให้มากพอ

ดังนั้น ในทางปฏิบัติแล้ว จึงมักไม่ค่อยมีใครสนใจกับโอกาสเกิดความผิดพลาดที่มีเล็กน้อยนี้สักเท่าไร เพราะเราสามารถทำให้มันน้อยลงเท่าไรก็ได้ตามใจปรารถนา ที่จริงแล้ว ถึงแม้ว่าเราจะมีขั้นตอนวิธีในการตรวจสอบการเป็นจำนวนเฉพาะแบบดิเทอร์มินิสติกที่สามารถทำงานได้ในเวลาโพลิโนเมียลแล้ว มันก็ยังไม่ได้ถูกนำไปใช้แทนวิธีเชิงความน่าจะเป็นแบบเดิมในซอฟต์แวร์ด้านการเข้ารหัสลับ และก็ยังไม่มีใครคิดว่าจะเป็นเช่นนั้นได้ในอนาคตอันใกล้นี้ด้วย

สมมุติว่าเราใช้วิธีเชิงสุ่ม แล้วมีความน่าจะเป็นที่จะเกิดความผิดพลาดเป็น 2−1000 คำถามที่ตามมาคือ ตัวเลขนี้เกิดจากการพิสูจน์ทางคณิตศาสตร์หรือไม่? ถึงแม้ว่าโอกาสผิดพลาดจะน้อยมากเมื่อเทียบกับโอกาสเกิดความผิดพลาดของฮาร์ดแวร์ที่ใช้ทำมัน หรือโอกาสที่คนตรวจบทพิสูจน์จะมองข้ามความผิดพลาดไป แต่จริงๆแล้วการบอกว่ามีความน่าจะเป็นน้อยนี้ ควรให้ความหมายว่าอย่างไรดี?