การทดสอบความเป็นจำนวนเฉพาะสำหรับผู้เริ่มต้น

ผู้เขียน	ลาสซี่ เรมเป้-กิลเลน , รีเบคก้า วัลเดกเกอร์
ชื่อเรื่องเดิม	Primzahltests สำหรับ Einsteiger: Zahlentheorie, Algorithmik, Kryptographie
ภาษา	ภาษาเยอรมัน
ประเภท	คณิตศาสตร์
สำนักพิมพ์	Vieweg+Teubner สมาคมคณิตศาสตร์อเมริกัน
วันที่เผยแพร่	2009

หนังสือ Primality Testing for Beginnersเป็นหนังสือคณิตศาสตร์ระดับปริญญาตรีเกี่ยวกับการทดสอบความเป็นจำนวนเฉพาะซึ่งเป็นวิธีการทดสอบว่าจำนวนที่กำหนดให้เป็นจำนวนเฉพาะ หรือ ไม่ โดยเน้นที่การทดสอบความเป็นจำนวนเฉพาะ AKSซึ่งเป็นวิธีการแรกในการแก้ปัญหานี้ในเวลาพหุนาม หนังสือเล่มนี้เขียนโดย Lasse Rempe-Gillenและ Rebecca Waldeckerและตีพิมพ์ครั้งแรกในภาษาเยอรมันในชื่อ Primzahltests für Einsteiger: Zahlentheorie, Algorithmik, Kryptographie (Vieweg+Teubner, 2009) ^{[ 1 ] [ 2 ]}ได้รับการแปลเป็นภาษาอังกฤษในชื่อ Primality Testing for Beginnersและตีพิมพ์ในปี 2014 โดย American Mathematical Societyเป็นเล่มที่ 70 ของชุดหนังสือ Student Mathematical Library ^{[ 2 ] [ 3 ] [ 4 ] [ 5 ]}ฉบับภาษาเยอรมันฉบับที่สองได้รับการตีพิมพ์โดย Springer ในปี 2016

การทดสอบความเป็นจำนวนเฉพาะสำหรับผู้เริ่มต้นมีเจ็ดบท แบ่งออกเป็นสองส่วน: สี่บทเกี่ยวกับเนื้อหาพื้นฐานในทฤษฎีจำนวนและทฤษฎีความซับซ้อนของการคำนวณและสามบทเกี่ยวกับการทดสอบความเป็นจำนวนเฉพาะ AKS ^{[ 1 ] [ 5 ]}

บทที่ 1 ประกอบด้วยเนื้อหาพื้นฐานเกี่ยวกับทฤษฎีจำนวน รวมถึงทฤษฎีบทพื้นฐานทางเลขคณิตเกี่ยวกับการแยกตัวประกอบเฉพาะเป็นจำนวนเฉพาะทฤษฎีบททวินาม ขั้นตอนวิธีของยุคลิดสำหรับการหาตัวหารร่วมมากและตะแกรงของเอราโตสเธเนสสำหรับการสร้างลำดับของจำนวนเฉพาะ บทที่ 2 เริ่มศึกษาเกี่ยวกับขั้นตอนวิธีและความซับซ้อนของขั้นตอนวิธี รวมถึงขั้นตอนวิธีสำหรับการคำนวณพื้นฐานทางเลขคณิต แนวคิดเรื่องความสามารถ ในการคำนวณ ขั้นตอนวิธีเวลาพหุนาม การสุ่ม และเวลาพหุนามแบบไม่กำหนดในส่วนของขั้นตอนวิธีแบบสุ่ม จะมีการแนะนำความแตกต่างระหว่างขั้นตอนวิธีลาสเวกัสที่ให้คำตอบที่ถูกต้องเสมอหลังจากช่วงเวลาแบบสุ่ม (เช่นควิกซอร์ต ) และขั้นตอนวิธีมอนเตคาร์โลซึ่งมีความน่าจะเป็นเล็กน้อยที่จะได้คำตอบที่ผิด (ตัวอย่างเช่น ขั้นตอนวิธีที่อิงตามทฤษฎีบทของชวาร์ตซ์-ซิปเปลสำหรับการทดสอบเอกลักษณ์ของพหุนาม ) บทที่ 3 ให้เนื้อหาเพิ่มเติมเกี่ยวกับทฤษฎีจำนวน รวมถึงทฤษฎีบทเศษเหลือของจีนทฤษฎีบทเล็กของแฟร์มาต์และการทดสอบความเป็นจำนวนเฉพาะของแฟร์มาต์นอกจากนี้ยังแนะนำการคำนวณด้วยพหุนามและเลขคณิตมอดูลาร์ส่วนแรกของหนังสือจบลงด้วยบทที่ 4 เกี่ยวกับประวัติของจำนวนเฉพาะและการทดสอบความเป็นจำนวนเฉพาะ รวมถึงทฤษฎีบทจำนวนเฉพาะ (ในรูปแบบที่อ่อนลง) การประยุกต์ใช้จำนวนเฉพาะในการเข้ารหัสและการทดสอบความเป็นจำนวนเฉพาะของมิลเลอร์-ราบินที่ ใช้กันอย่างแพร่หลาย ซึ่งทำงานในเวลาพหุนามแบบสุ่ม^{[ 5 ]}

บทที่ 5 ขยายทฤษฎีบทเล็กของแฟร์มาต์จากจำนวนไปสู่พหุนาม และแนะนำการทดสอบความเป็นจำนวนเฉพาะแบบสุ่มโดยอิงจากการขยายนี้ บทที่ 6 นำเสนอผลลัพธ์ทางคณิตศาสตร์ที่สำคัญเบื้องหลังความถูกต้องของการทดสอบความเป็นจำนวนเฉพาะ AKS และบทที่ 7 อธิบายการทดสอบนั้นเอง^{[ 5 ]}ทั้งความถูกต้องและเวลาการทำงานของอัลกอริทึมแบบพหุนามได้รับการพิสูจน์อย่างเข้มงวด^{[ 3 ]}มีแบบฝึกหัดรวมอยู่ในแต่ละบท และส่วนท้ายของหนังสือมีคำตอบสำหรับแบบฝึกหัดบางส่วน^{[ 1 ] [ 2 ]}ภาคผนวกอีกส่วนหนึ่งแสดงรายการปัญหาที่ยังไม่ได้รับการแก้ไขบางส่วนจากทฤษฎีจำนวน^{[ 3 ]}

แม้ว่าการทดสอบจำนวนเฉพาะสำหรับผู้เริ่มต้น จะเหมาะสำหรับนักศึกษาระดับปริญญาตรีสาขาคณิตศาสตร์เป็นหลัก แต่ก็ไม่จำเป็นต้องมีความรู้พื้นฐานมากนัก และอาจเหมาะสำหรับนักเรียนมัธยมปลายที่มีความรู้ขั้นสูงด้วย^{[ 2 ] [ 3 ]}โดยอิงจากโครงการภาคฤดูร้อนสำหรับนักเรียนระดับนี้ ซึ่งดำเนินการโดยผู้เขียนในประเทศเยอรมนี โดยมีเป้าหมายเพื่อแนะนำนักเรียนให้รู้จักกับงานวิจัยล่าสุด^{[ 4 ]}

ผู้วิจารณ์ Robin Chapman และ Jeffrey Ehme เห็นพ้องกันว่าเนื้อหาโดยรวมของหนังสือเล่มนี้อาจจะน้อยเกินไปที่จะใช้เป็นตำราหลักสำหรับหลักสูตรทฤษฎีจำนวนในระดับปริญญาตรี แต่สามารถใช้เป็นส่วนเสริมที่ดีสำหรับหลักสูตรดังกล่าว หรือสำหรับหลักสูตรการเข้ารหัสลับได้^{[ 3 ] [ 4 ]}ผู้วิจารณ์ Frederic Green แนะนำให้ใช้เป็นบทนำที่ดีสำหรับการวิจัยทางคณิตศาสตร์โดยทั่วไป และยังแนะนำให้นักวิจัยใช้เป็นข้อมูลอ้างอิงอย่างรวดเร็วเกี่ยวกับการทดสอบความเป็นจำนวนเฉพาะ^{[ 5 ]}