ການທົດສອບ Primality ໃນ Polynomial Time, ຈາກ Randomized Algorithms ເຖິງ "PRIMES ແມ່ນຢູ່ໃນ P"

ການປິ່ນປົວດ້ວຍຕົນເອງຂອງສູດການຄິດໄລ່ທີ່ມີປະສິດທິພາບທາງດ້ານທິດສະດີແລະການປະຕິບັດທີ່ສໍາຄັນສໍາລັບບັນຫາ primality. ຂໍ້ຄວາມກວມເອົາສູດການຄິດໄລ່ແບບສຸ່ມໂດຍ Solovay-Strassen ແລະ Miller-Rabin ຈາກທ້າຍຊຸມປີ 1970 ເຊັ່ນດຽວກັນກັບສູດການຄິດໄລ່ຫຼ້າສຸດຂອງ Agrawal, Kayal ແລະ Saxena. ປະລິມານແມ່ນລາຍລັກອັກສອນສໍາລັບນັກສຶກສາຂອງວິທະຍາສາດຄອມພິວເຕີ, ໂດຍສະເພາະຜູ້ທີ່ມີຄວາມສົນໃຈພິເສດໃນ cryptology, ແລະນັກສຶກສາຂອງຄະນິດສາດ, ແລະມັນອາດຈະຖືກນໍາໃຊ້ເປັນອາຫານເສີມສໍາລັບວິຊາຫຼືສໍາລັບການສຶກສາດ້ວຍຕົນເອງ.