การแยกตัวประกอบจำนวนเต็ม

Q: สถานะปัจจุบันของเทคโนโลยี

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

ปัญหาที่ยังแก้ไม่ตกในวิทยาการคอมพิวเตอร์

การแยกตัวประกอบจำนวนเต็มสามารถแก้ไขได้ในเวลาพหุนามบนคอมพิวเตอร์แบบคลาสสิกหรือไม่?

ยังมีปัญหาที่ยังแก้ไม่ตกอีกมากมายในสาขาวิทยาการคอมพิวเตอร์

ในทางคณิตศาสตร์การแยกตัวประกอบจำนวนเต็มคือ การแยกจำนวนเต็มบวกออกเป็นผลคูณของจำนวนเต็ม จำนวนเต็มบวกทุกจำนวนที่มากกว่า 1 จะเป็นผลคูณของตัวประกอบ จำนวนเต็มตั้งแต่สองตัว ขึ้นไปที่มากกว่า 1 ซึ่งในกรณีนี้จะเป็นจำนวนประกอบหรือหากไม่ใช่ผลคูณของ ตัวประกอบ จำนวนเต็ม ก็จะเป็นจำนวนเฉพาะตัวอย่างเช่น $15$ เป็นจำนวนประกอบเพราะ $15 = 3 \cdot 5$ แต่ $7$ เป็นจำนวนเฉพาะเพราะไม่สามารถแยกตัวประกอบในลักษณะนี้ได้ ถ้าตัวประกอบตัวใดตัวหนึ่งเป็นจำนวนประกอบ ก็สามารถเขียนเป็นผลคูณของตัวประกอบที่เล็กกว่าได้ เช่น $60 = 3 \cdot 20 = 3 \cdot (5 \cdot 4)$ การทำเช่นนี้ไปเรื่อยๆ จนกว่าตัวประกอบทุกตัวจะเป็นจำนวนเฉพาะ เรียกว่าการแยกตัวประกอบเฉพาะผลลัพธ์ที่ได้จะมีความเป็นเอกลักษณ์เสมอจนถึงลำดับของตัวประกอบตามทฤษฎีบทการแยกตัวประกอบเฉพาะ

ในการแยกตัวประกอบของจำนวนเต็มขนาดเล็ก $n$ โดยใช้การคำนวณในใจหรือการเขียนลงบนกระดาษ วิธีที่ง่ายที่สุดคือการหารแบบลองผิดลองถูก : ตรวจสอบว่าจำนวนนั้นหารลงตัวด้วยจำนวนเฉพาะ $2$ , $3$ , $5$ และอื่นๆ ไปจนถึงรากที่สองของ $n$ หรือไม่ สำหรับจำนวนที่ใหญ่กว่า โดยเฉพาะอย่างยิ่งเมื่อใช้คอมพิวเตอร์ อัลกอริทึมการแยกตัวประกอบที่ซับซ้อนกว่าต่างๆ จะมีประสิทธิภาพมากกว่า อัลกอริทึมการแยกตัวประกอบเฉพาะโดยทั่วไปจะเกี่ยวข้องกับการทดสอบว่าตัวประกอบแต่ละตัวเป็นจำนวนเฉพาะหรือไม่ทุกครั้งที่พบตัวประกอบ

เมื่อตัวเลขมีขนาดใหญ่เพียงพอ จะไม่มีอัลกอริทึมการแยกตัวประกอบจำนวนเต็มที่ ไม่ใช่ ควอนตัม ที่มีประสิทธิภาพ เป็นที่รู้จัก อย่างไรก็ตาม ยังไม่มีการพิสูจน์ว่าอัลกอริทึมดังกล่าวไม่มีอยู่จริงความยากลำบาก ที่คาดการณ์ไว้ ของปัญหานี้มีความสำคัญต่ออัลกอริทึมที่ใช้ในการเข้ารหัสลับเช่นการเข้ารหัสกุญแจสาธารณะ RSAและลายเซ็นดิจิทัล RSA [ ¹^]^หลายสาขาของคณิตศาสตร์และวิทยาศาสตร์คอมพิวเตอร์ได้ถูกนำมาใช้กับปัญหานี้ รวมถึงเส้นโค้งวงรี ทฤษฎี จำนวนพีชคณิตและการคำนวณควอนตัม

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

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

การสลายตัวหลัก

การแยกตัวประกอบเฉพาะของ $n = 864$ คือ $25 \times 3 3$

ตามทฤษฎีบทพื้นฐานทางเลขคณิตจำนวนเต็มบวกทุกจำนวนมีตัวประกอบเฉพาะ ที่ไม่ซ้ำกัน (ตามธรรมเนียม 1 คือผลคูณว่าง ) การทดสอบว่าจำนวนเต็มนั้นเป็นจำนวนเฉพาะหรือไม่ สามารถทำได้ในเวลาพหุนามเช่น โดยใช้การทดสอบความเป็นจำนวนเฉพาะ AKSอย่างไรก็ตาม หากเป็นจำนวนประกอบ การทดสอบในเวลาพหุนามจะไม่ให้ข้อมูลใดๆ เกี่ยวกับวิธีการหาตัวประกอบ

เมื่อมีอัลกอริทึมทั่วไปสำหรับการแยกตัวประกอบจำนวนเต็มแล้ว จำนวนเต็มใดๆ ก็สามารถแยกตัวประกอบออกเป็นตัวประกอบเฉพาะได้โดยการใช้อัลกอริทึมนี้ซ้ำๆ สถานการณ์จะซับซ้อนมากขึ้นสำหรับอัลกอริทึมการแยกตัวประกอบเฉพาะทาง ซึ่งอาจไม่ได้รับประโยชน์เท่าที่ควรหรืออาจไม่ได้รับประโยชน์เลยจากตัวประกอบที่ได้จากการแยกตัวประกอบ ตัวอย่างเช่น ถ้า $n = 171 \times p \times q$ โดยที่ $p < q$ เป็นจำนวนเฉพาะขนาดใหญ่มากการหารแบบลองผิดลองถูกจะให้ตัวประกอบ 3 และ 19 ได้อย่างรวดเร็ว แต่จะต้องใช้ การหาร $p$ ครั้งเพื่อหาตัวประกอบถัดไป เพื่อเป็นการเปรียบเทียบ หาก $n$ เป็นผลคูณของจำนวนเฉพาะ $13729$ , $1372933$ และ $18848997161$ โดยที่ $13729 \times 1372933 = 18848997157$ วิธีการแยกตัวประกอบของแฟร์มาต์จะเริ่มต้นด้วย $⌈ \sqrt n ⌉ = 18848997159$ ซึ่งจะได้ $b = \sqrt a 2 - n = \sqrt 4 = 2$ ทันที และด้วยเหตุนี้ ตัวประกอบ $a - b = 18848997157$ และ $a + b$ = $18848997161$ แม้ว่าจะสามารถระบุจำนวนเหล่านี้ว่าเป็นจำนวนประกอบและจำนวนเฉพาะได้อย่างง่ายดาย แต่การใช้วิธีของแฟร์มาต์จะใช้เวลานานกว่ามากในการแยกตัวประกอบของจำนวนประกอบ เนื่องจากค่าเริ่มต้นของ $⌈ \sqrt 18848997157 ⌉ = 137292$ สำหรับ $a$ เป็นตัวประกอบของ 10 จาก $1372933$

สถานะปัจจุบันของเทคโนโลยี

ในบรรดา จำนวน $b$ บิต จำนวนที่ยากที่สุดในการแยกตัวประกอบในทางปฏิบัติโดยใช้อัลกอริธึมที่มีอยู่คือจำนวนกึ่งเฉพาะที่มีตัวประกอบขนาดใกล้เคียงกัน ด้วยเหตุนี้ จำนวนเหล่านี้จึงถูกนำมาใช้ในแอปพลิเคชันทางด้านการเข้ารหัสลับ

ในปี 2019 ทีมวิจัยซึ่งรวมถึงPaul Zimmermann ได้แยก ตัวประกอบเลข 240 หลัก (795 บิต) ( RSA-240 ) โดยใช้พลังการประมวลผลประมาณ 900 ปีของคอร์^[²^]นักวิจัยเหล่านี้ประเมินว่าโมดูลัส RSA 1024 บิตจะใช้เวลานานขึ้นประมาณ 500 เท่า^[³^]

จำนวน กึ่งเฉพาะที่ใหญ่ที่สุดที่เคยแยกตัวประกอบได้คือRSA-250ซึ่งเป็นจำนวน 829 บิตที่มีตัวเลขทศนิยม 250 หลัก ในเดือนกุมภาพันธ์ 2020 เวลาในการคำนวณทั้งหมดอยู่ที่ประมาณ 2700 ปีของการประมวลผลโดยใช้ Intel Xeon Gold 6130 ที่ความเร็ว 2.1 GHz เช่นเดียวกับสถิติการแยกตัวประกอบล่าสุดทั้งหมด การแยกตัวประกอบนี้เสร็จสมบูรณ์ด้วยการใช้งานGeneral Number Field Sieve ที่ได้รับการปรับแต่งอย่างสูง ซึ่งทำงานบนเครื่องหลายร้อยเครื่อง

ความซับซ้อนเชิงเวลา

ยังไม่มีการเผยแพร่อัลกอริทึม ใดที่สามารถแยกตัวประกอบจำนวนเต็มทั้งหมดได้ใน เวลาพหุนามกล่าวคือ สามารถแยกตัวประกอบจำนวน $b บิต$ $n$ ได้ ในเวลา $O (b k)$ สำหรับค่าคงที่ $k$ บางค่า ไม่มีการพิสูจน์การมีอยู่หรือไม่มีอยู่ของอัลกอริทึมดังกล่าว แต่โดยทั่วไปแล้วคาดว่าไม่มีอยู่จริง^{[ 4 ]}^{[ 5 ]}

มีอัลกอริทึมที่เผยแพร่แล้วซึ่งเร็วกว่า $O((1 + ε) b)$ สำหรับ $ε$ บวกทั้งหมด นั่นคือ เร็วกว่า เลขชี้กำลัง เล็กน้อยณ ปี 2022อัลกอริทึมที่มีเวลาการทำงานเชิงทฤษฎีที่ดีที่สุดคือตะแกรงฟิลด์ตัวเลขทั่วไป (GNFS) ซึ่งเผยแพร่ครั้งแรกในปี พ.ศ. 2536 ^{[ 6 ]}ทำงานบนตัวเลข $n บิต$ $b$ ในเวลา:

\exp \left(\left(\left({\tfrac {8}{3}}\right)^{\frac {2}{3}}+o(1)\right)\left(\log n\right)^{\frac {1}{3}}\left(\log \log n\right)^{\frac {2}{3}}\right).

สำหรับคอมพิวเตอร์ในปัจจุบัน GNFS เป็นอัลกอริทึมที่ดีที่สุดที่เผยแพร่สำหรับ $n$ ขนาดใหญ่ (มากกว่าประมาณ 400 บิต) อย่างไรก็ตาม สำหรับ คอมพิวเตอร์ควอนตัม ปีเตอร์ ชอร์ได้ค้นพบอัลกอริทึมในปี 1994 ที่แก้ปัญหานี้ได้ในเวลาพหุนามอัลกอริทึมของชอร์ใช้เวลาเพียง $O(b³)$ และ พื้นที่ $O( b) สำหรับ$ $อินพุต$ จำนวน $b$ บิต ในปี 2001 อัลกอริทึมของชอร์ได้รับการนำไปใช้เป็นครั้งแรกโดยใช้ เทคนิค NMRบนโมเลกุลที่ให้คิวบิตเจ็ดตัว^{[ 7 ]}

ในการพูดถึงระดับความซับซ้อนเช่น P, NP และ co-NP นั้น จำเป็นต้องระบุปัญหาในรูปแบบของปัญหาการตัดสินใจ

ปัญหาการตัดสินใจ(การแยกตัวประกอบจำนวนเต็ม) —สำหรับจำนวนธรรมชาติทุกจำนวน $n$ และ $k$ นอกจาก 1 แล้ว $n$ มีตัวประกอบอื่นที่เล็กกว่า $k$ อีกหรือไม่ ?

เป็นที่ทราบกันว่าอยู่ในทั้งNPและco-NPซึ่งหมายความว่าทั้งคำตอบ "ใช่" และ "ไม่ใช่" สามารถตรวจสอบได้ในเวลาพหุนาม คำตอบ "ใช่" สามารถรับรองได้โดยการแสดงการแยกตัวประกอบ $n = d (⁠ n / d ⁠)$ โดยที่ $d \leq k$ คำตอบ "ไม่ใช่" สามารถรับรองได้โดยการแสดงการแยกตัวประกอบของ $n$ เป็นจำนวนเฉพาะที่แตกต่างกัน ซึ่งทั้งหมดมีค่ามากกว่า $k$ สามารถตรวจสอบความเป็นจำนวนเฉพาะโดยใช้การทดสอบความเป็นจำนวนเฉพาะ AKSจากนั้นคูณกันเพื่อให้ได้ $n$ ทฤษฎีบทพื้นฐานของเลขคณิตรับประกันว่ามีเพียงสตริงเดียวที่เป็นไปได้ของจำนวนเฉพาะที่เพิ่มขึ้นซึ่งจะได้รับการยอมรับ ซึ่งแสดงให้เห็นว่าปัญหานี้อยู่ในทั้งUPและ co-UP ^{[ 8 ]}เป็นที่ทราบกันว่าอยู่ในBQPเนื่องจากอัลกอริทึมของ Shor

ปัญหาดังกล่าวคาดว่าจะอยู่นอกเหนือคลาสความซับซ้อนทั้งสามคลาส ได้แก่ P, NP-complete, ^{[ 9 ]}และco-NP-completeดังนั้นจึงเป็นผู้สมัครสำหรับคลาสความซับซ้อนระดับกลาง NP

ในทางตรงกันข้าม ปัญหาการตัดสินใจ " $n$ เป็น จำนวนประกอบหรือไม่?" (หรือเทียบเท่ากับ: " $n$ เป็น จำนวนเฉพาะหรือไม่?") ดูเหมือนจะง่ายกว่าปัญหาการระบุตัวประกอบของ $n$ มาก ปัญหาจำนวนประกอบ/จำนวนเฉพาะสามารถแก้ไขได้ในเวลาพหุนาม (ในจำนวน หลัก $b$ ของ $n$ ) ด้วยการทดสอบความเป็นจำนวนเฉพาะ AKSนอกจากนี้ยังมีอัลกอริธึมเชิงความน่า จะเป็นหลายตัว ที่สามารถทดสอบความเป็นจำนวนเฉพาะได้อย่างรวดเร็วในทางปฏิบัติ หากเรายอมรับความเป็นไปได้ของข้อผิดพลาดที่น้อยมาก ความง่ายในการทดสอบความเป็นจำนวนเฉพาะเป็นส่วนสำคัญของ อัลกอริธึม RSAเนื่องจากจำเป็นต้องค้นหาจำนวนเฉพาะขนาดใหญ่เพื่อเริ่มต้น

อัลกอริทึมการแยกตัวประกอบ

วัตถุประสงค์พิเศษ

เวลาในการทำงานของอัลกอริทึมการแยกตัวประกอบเฉพาะทางนั้นขึ้นอยู่กับคุณสมบัติของจำนวนที่จะแยกตัวประกอบ หรือตัวประกอบที่ไม่ทราบค่าอย่างใดอย่างหนึ่ง เช่น ขนาด รูปแบบพิเศษ เป็นต้น พารามิเตอร์ที่กำหนดเวลาในการทำงานจะแตกต่างกันไปในแต่ละอัลกอริทึม

กลุ่มย่อยที่สำคัญของอัลกอริธึมการแยกตัวประกอบเฉพาะทางคือ อัลกอริธึม ประเภทที่ 1หรือประเภทแรกซึ่งเวลาในการทำงานขึ้นอยู่กับขนาดของตัวประกอบเฉพาะที่เล็กที่สุด เมื่อกำหนดจำนวนเต็มที่มีรูปแบบที่ไม่ทราบ วิธีการเหล่านี้มักจะถูกนำไปใช้ก่อนวิธีการทั่วไปเพื่อกำจัดตัวประกอบขนาดเล็ก^{[ 10 ]}ตัวอย่างเช่นการหารแบบทดลอง อย่างง่าย เป็นอัลกอริธึมประเภทที่ 1

แผนกพิจารณาคดี
การแยกตัวประกอบล้อ
อัลกอริทึมโรของพอลลาร์ดซึ่งมีสองรูปแบบที่ใช้กันทั่วไปในการระบุวัฏจักรกลุ่มได้แก่ รูปแบบหนึ่งของฟลอยด์ และอีกรูปแบบหนึ่งของเบรนต์
อัลกอริทึมการแยกตัวประกอบกลุ่มพีชคณิตซึ่งรวมถึงอัลกอริทึม $p$ $- 1$ ของ Pollard , อัลกอริทึม $p$ $+ 1$ ของ Williamsและการแยกตัวประกอบเส้นโค้งวงรีของ Lenstra
วิธีการแยกตัวประกอบของแฟร์มาต์
วิธีการแยกตัวประกอบของออยเลอร์
ตะแกรงร่อนเมล็ดพืชหมายเลขพิเศษ
ผลต่างของกำลังสอง

อเนกประสงค์

อัลกอริทึมการแยกตัวประกอบอเนกประสงค์ หรือที่รู้จักกันในชื่อCategory 2 , Second CategoryหรือKraitchik family algorithm ^{[ 10 ]}มีเวลาการทำงานที่ขึ้นอยู่กับขนาดของจำนวนเต็มที่จะแยกตัวประกอบเท่านั้น นี่คือประเภทของอัลกอริทึมที่ใช้ในการแยกตัวประกอบจำนวน RSAอั ลกอริ ทึมการแยกตัวประกอบอเนกประสงค์ส่วนใหญ่จะใช้หลักการความสอดคล้องของกำลังสองเป็น พื้นฐาน

อัลกอริทึมที่น่าสนใจอื่นๆ

อัลกอริทึมของชอร์สำหรับคอมพิวเตอร์ควอนตัม

เวลาการทำงานของฮิวริสติก

ในทฤษฎีจำนวน มีอัลกอริธึมการแยกตัวประกอบจำนวนเต็มหลายตัวที่มีเวลาการทำงาน ที่คาดหวังตามหลักการเชิงฮิวริสติก

L_{n}\left[{\tfrac {1}{2}},1+o(1)\right]=e^{(1+o(1)){\sqrt {(\log n)(\log \log n)}}}

ใน สัญลักษณ์ little-oและL-notationตัวอย่างของอัลกอริธึมเหล่านี้ ได้แก่วิธีเส้นโค้งวงรีและตะแกรงกำลังสองอัลกอริธึมอีกแบบหนึ่งคือวิธีความสัมพันธ์กลุ่มชั้นที่เสนอโดย Schnorr ^{[ 11 ]} Seysen ^{[ 12 ]}และ Lenstra ^{[ 13 ]}ซึ่งพวกเขาพิสูจน์โดยสมมติสมมติฐาน Riemann ทั่วไปที่ ยังไม่ได้รับการพิสูจน์เท่านั้น

ระยะเวลาการวิ่งที่เข้มงวด

อัลกอริทึมความน่าจะเป็น Schnorr–Seysen–Lenstra ได้รับการพิสูจน์อย่างเข้มงวดโดย Lenstra และ Pomerance ^{[ 14 ]}ว่ามีเวลาการทำงานที่คาดหวัง $L [⁠ 1 / 2 ⁠, 1+ o (1)]$ โดยการแทนที่สมมติฐาน GRH ด้วยการใช้ตัวคูณ อัลกอริทึมใช้กลุ่มคลาสของรูปแบบกำลังสองไบนารี บวก ของดิสคริมิแนนต์ $Δ$ ที่ แสดงด้วย $G$ $G$ คือเซตของสามจำนวนเต็ม $(a, b, c)$ ซึ่งจำนวนเต็มเหล่านั้นเป็นจำนวนเฉพาะสัมพัทธ์

อัลกอริทึม Schnorr–Seysen–Lenstra

กำหนดให้จำนวนเต็ม $n$ ที่ต้องการแยกตัวประกอบ โดยที่ $n$ เป็นจำนวนเต็มบวกคี่ที่มากกว่าค่าคงที่ค่าหนึ่ง ในอัลกอริทึมการแยกตัวประกอบนี้ ตัวแยกแยะ $Δ$ จะถูกเลือกให้เป็นพหุคูณของ $n$ , $Δ = - dn$ โดยที่ $d$ เป็นตัวคูณบวกบางค่า อัลกอริทึมคาดหวังว่าสำหรับ $d ค่า$ หนึ่ง จะมี รูปแบบ เรียบ เพียงพอ ใน $G$ Lenstra และ Pomerance แสดงให้เห็นว่าการเลือก $d$ สามารถจำกัดให้อยู่ในเซตเล็กๆ เพื่อรับประกันผลลัพธ์ที่เรียบเนียนได้

ให้ $P$ เป็น เซตของจำนวนเฉพาะ $q$ ทั้งหมด ที่มีสัญลักษณ์โครเนกเกอร์ $(⁠ Δ / q ⁠) = 1$ โดยการสร้างเซตของตัวสร้าง $G$ และรูปแบบจำนวนเฉพาะ $f$ ของ $G$ โดยที่ $q$ อยู่ใน $P$ จะได้ ลำดับความสัมพันธ์ระหว่างเซตของตัวสร้างและ $f$ ขนาดของ $q$ สามารถจำกัดได้ด้วย $c (log | Δ |) 2$ สำหรับค่าคงที่ $c$ บาง ค่า

ความสัมพันธ์ที่จะนำมาใช้คือความสัมพันธ์ระหว่างผลคูณของกำลังที่เท่ากับองค์ประกอบที่เป็นกลางของ $G$ ความสัมพันธ์เหล่านี้จะถูกนำมาใช้เพื่อสร้างรูปแบบที่เรียกว่ารูปแบบกำกวมของ $G$ ซึ่งเป็นองค์ประกอบของ $G$ ที่มีอันดับหาร 2 ลงตัว โดยการคำนวณการแยกตัวประกอบที่สอดคล้องกันของ $Δ$ และการหาห.ร.ม.รูปแบบกำกวมนี้จะให้การแยกตัวประกอบเฉพาะที่สมบูรณ์ของ $n$ อัลกอริทึมนี้มีขั้นตอนหลักดังต่อไปนี้:

ให้ $n$ เป็นจำนวนที่ต้องการแยกตัวประกอบ

ให้ $Δ$ เป็นจำนวนเต็มลบ โดยที่ $Δ = - dn$ โดยที่ $d$ เป็นตัวคูณ และ $Δ$ คือค่าดิสครีมิแนนต์ลบของรูปแบบกำลังสองบางรูปแบบ
เลือก จำนวนเฉพาะ $t$ ตัวแรก $p = 2, p$ = 3 $,$ $p$ $= 5, ...,$ $p$ สำหรับบาง $t \in N$
ให้ $f$ เป็นรูปแบบจำนวนเฉพาะสุ่มของ $G$ โดยที่ $(⁠ Δ / q ⁠) =$ 1
หาเซตตัวก่อกำเนิด $X$ ของ $G$
รวบรวมลำดับความสัมพันธ์ระหว่างเซต $X$ และ ${f : q \in P}$ ที่สอดคล้องกับเงื่อนไขต่อไปนี้:
$\left(\prod _{x\in X_{}}x^{r(x)}\right).\left(\prod _{q\in P_{\Delta }}f_{q}^{t(q)}\right)=1.$
สร้างรูปแบบกำกวม $(a, b, c)$ ที่เป็นองค์ประกอบ $f \in GΔ$ มีอันดับหาร 2 ลงตัว เพื่อให้ได้การแยกตัวประกอบเฉพาะร่วมของตัวหารคี่ที่ใหญ่ที่สุดของΔ $ซึ่ง$ Δ $= -4ac หรือ$ Δ $= a (a - 4c) หรือ$ Δ $= (b - 2a) (b + 2a)$
ถ้าฟอร์มที่กำกวมให้การแยกตัวประกอบของ $n$ แล้วให้หยุด มิฉะนั้นให้หาฟอร์มที่กำกวมอื่นต่อไปจนกว่าจะพบการแยกตัวประกอบของ $n$ เพื่อป้องกันไม่ให้เกิดฟอร์มที่กำกวมที่ไร้ประโยชน์ ให้สร้างกลุ่ม2-Sylow $Sll (Δ)$ ของ $G (Δ$ )

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

ระยะเวลาดำเนินการที่คาดไว้

อัลกอริทึมดังกล่าวเป็นอัลกอริทึมเชิงความน่าจะเป็นเนื่องจากเลือกแบบสุ่ม เวลาการทำงานที่คาดหวังคือ $L [⁠ 1 / 2 ⁠, 1+ o (1)]$ . ^{[ 14 ]}

ดูเพิ่มเติม

การแยกตัวประกอบแบบออริเฟยเลียน
อัลกอริทึมของบาค– สำหรับการสร้างตัวเลขสุ่มที่แยกตัวประกอบแล้ว
การแสดงผลแบบมาตรฐานของจำนวนเต็มบวก
การแยกตัวประกอบ
การแบ่งส่วนแบบคูณ– วิธีการเขียนจำนวนหนึ่งในรูปผลคูณของจำนวนอื่น ๆ
$การประเมินค่า p$ -adic
การแบ่งส่วนจำนวนเต็ม– การแยกจำนวนเต็มออกเป็นผลรวมของจำนวนเต็มบวก

หมายเหตุ

↑ Lenstra, Arjen K. (2011), "Integer Factoring", ในแวน ทิลบอร์ก, เฮงค์ แคลิฟอร์เนีย; Jajodia, Sushil (eds.), Encyclopedia of Cryptography and Security , Boston: Springer, หน้า611– 618, doi : 10.1007/978-1-4419-5906-5_455 , ISBN 978-1-4419-5905-8
↑ " [ Cado-nfs-discuss ]การแยกตัวประกอบ 795 บิตและลอการิทึมแบบไม่ต่อเนื่อง"เก็บถาวรจากต้นฉบับเมื่อ 2 ธันวาคม 2019
↑ไคลน์จุง, ธอร์สเตน; อาโอกิ, คาซูมาโระ; แฟรงเก้, เจนส์; Lenstra, อาร์เยน เค.; โทเม, เอ็มมานูเอล; บอส จอปป์ ว.; เกาดรี, เพียร์ริก; ครุปปา, อเล็กซานเดอร์; มอนต์โกเมอรี, ปีเตอร์ แอล.; ออสวิค, แด็ก อาร์เน; เต ริเอเล, เฮอร์แมน เจเจ; ทิโมเฟเยฟ, อันเดรย์; ซิมเมอร์มันน์, พอล (2010) "การแยกตัวประกอบของโมดูลัส RSA 768 บิต" (PDF ) ใน Rabin, Tal (เอ็ด.) Advances in Cryptology - CRYPTO 2010, การประชุม Cryptology Conference ประจำปีครั้งที่ 30, ซานตาบาร์บาร่า, แคลิฟอร์เนีย, สหรัฐอเมริกา, 15-19 สิงหาคม 2553. Proceedings บันทึกการบรรยายทางวิทยาการคอมพิวเตอร์ ฉบับที่6223. สปริงเกอร์ หน้า333– 350. ดอย : 10.1007/978-3-642-14623-7_18 . ไอเอสบีเอ็น 978-3-642-14622-0.
↑ Krantz, Steven G. (2011), The Proof is in the Pudding: The Changing Nature of Mathematical Proof , New York: Springer, หน้า203, doi : 10.1007/978-0-387-48744-1 , ISBN 978-0-387-48908-7, MR 2789493
↑ Arora, Sanjeev ; Barak, Boaz (2009), ความซับซ้อนในการคำนวณ , เคมบริดจ์: สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์, หน้า230, doi : 10.1017/CBO9780511804090 , ISBN 978-0-521-42426-4MR 2500087 , S2CID 215746906
↑ Buhler, JP; Lenstra, HW Jr.; Pomerance, Carl (1993). "การแยกตัวประกอบจำนวนเต็มด้วยตะแกรงสนามจำนวน" การพัฒนาตะแกรงสนามจำนวนบันทึกการบรรยายทางคณิตศาสตร์ เล่มที่1554สปริงเกอร์ หน้า50–94 doi : 10.1007 / BFb0091539 hdl : 1887/2149 ISBN 978-3-540-57013-4สืบค้นข้อมูลเมื่อ วัน ที่12 มีนาคม 2564
↑ Vandersypen, Lieven MK; และคณะ (2001). "การสร้างอัลกอริทึมการแยกตัวประกอบควอนตัมของ Shor ในทางปฏิบัติโดยใช้เรโซแนนซ์แม่เหล็กนิวเคลียร์" Nature . 414 (6866): 883– 887. arXiv : quant-ph/0112176 . Bibcode : 2001Natur.414..883V . doi : 10.1038/414883a . PMID 11780055 . S2CID 4400832 .
↑ Lance Fortnow (13 กันยายน 2002). "Computational Complexity Blog: Complexity Class of the Week: Factoring" .
↑ Goldreich, Oded ; Wigderson, Avi (2008), "IV.20 ความซับซ้อนในการคำนวณ", ในGowers, Timothy ; Barrow-Green, June ; Leader, Imre (บรรณาธิการ), The Princeton Companion to Mathematics , Princeton, New Jersey: Princeton University Press, หน้า575– 604, ISBN 978-0-691-11880-2, MR 2467561 โปรดดูโดยเฉพาะหน้า 583
1 2 David BressoudและStan Wagon (2000). หลักสูตรทฤษฎีจำนวนเชิงคำนวณ . สำนักพิมพ์ Key College Publishing/Springer. หน้า168–169 . ISBN 978-1-930190-10-8.
↑ Schnorr, Claus P. (1982). "การวิเคราะห์ที่ละเอียดขึ้นและการปรับปรุงอัลกอริทึมการแยกตัวประกอบบางอย่าง"วารสารอัลกอริทึม 3 ( 2): 101– 127. doi : 10.1016/0196-6774(82)90012-8 . MR 0657269 . เก็บถาวรจากต้นฉบับเมื่อวันที่ 24 กันยายน 2017
↑ Seysen, Martin (1987). "อัลกอริทึมการแยกตัวประกอบเชิงความน่าจะเป็นด้วยรูปแบบกำลังสองของดิสคริมิแนนต์เชิงลบ"คณิตศาสตร์ของการคำนวณ 48 ( 178): 757– 780. doi : 10.1090/S0025-5718-1987-0878705-X . MR 0878705 .
↑ Lenstra, Arjen K (1988). "การแยกตัวประกอบที่รวดเร็วและเข้มงวดภายใต้สมมติฐานรีมันน์ทั่วไป" (PDF) . Indagationes Mathematicae . 50 (4): 443– 454. doi : 10.1016/S1385-7258(88)80022-2 .
1 2 Lenstra, HW; Pomerance, Carl (กรกฎาคม 1992). "ขอบเขตเวลาที่เข้มงวดสำหรับการแยกตัวประกอบจำนวนเต็ม" (PDF)วารสารของสมาคมคณิตศาสตร์อเมริกัน 5 ( 3): 483– 516. doi : 10.1090/S0894-0347-1992-1137100-0 . MR 1137100 .

ลิงก์ภายนอก

msieve – ซึ่งรวมถึง SIQS และ NFS – ได้ช่วยดำเนินการแยกตัวประกอบสาธารณะครั้งใหญ่ที่สุดบางส่วนเท่าที่เคยมีมา
Richard P. Brent, "ความก้าวหน้าล่าสุดและแนวโน้มของอัลกอริทึมการแยกตัวประกอบจำนวนเต็ม", การคำนวณและการจัดเรียง , 2000, หน้า 3–22. ดาวน์โหลด
มนินทรา อากราวัล , นีราช คายาล, นิติน ซักเซนา, "PRIMES is in P." พงศาวดารคณิตศาสตร์ 160(2): 781–793 (2004) PDF เวอร์ชันเดือนสิงหาคม 2548
Eric W. Weisstein, “RSA-640 Factored” MathWorld Headline News , 8 พฤศจิกายน 2005
เครื่องคำนวณการแยกตัวประกอบจำนวนเต็มของดาริโอ อัลแปร์น – แอปพลิเคชันบนเว็บสำหรับการแยกตัวประกอบจำนวนเต็มขนาดใหญ่

[1] Lenstra, Arjen K. (2011), "Integer Factoring", ในแวน ทิลบอร์ก, เฮงค์ แคลิฟอร์เนีย; Jajodia, Sushil (eds.), Encyclopedia of Cryptography and Security , Boston: Springer, หน้า611– 618, doi : 10.1007/978-1-4419-5906-5_455 , ISBN 978-1-4419-5905-8

[2] " [ Cado-nfs-discuss ]การแยกตัวประกอบ 795 บิตและลอการิทึมแบบไม่ต่อเนื่อง"เก็บถาวรจากต้นฉบับเมื่อ 2 ธันวาคม 2019

[rsa768-3] ไคลน์จุง, ธอร์สเตน; อาโอกิ, คาซูมาโระ; แฟรงเก้, เจนส์; Lenstra, อาร์เยน เค.; โทเม, เอ็มมานูเอล; บอส จอปป์ ว.; เกาดรี, เพียร์ริก; ครุปปา, อเล็กซานเดอร์; มอนต์โกเมอรี, ปีเตอร์ แอล.; ออสวิค, แด็ก อาร์เน; เต ริเอเล, เฮอร์แมน เจเจ; ทิโมเฟเยฟ, อันเดรย์; ซิมเมอร์มันน์, พอล (2010) "การแยกตัวประกอบของโมดูลัส RSA 768 บิต" (PDF ) ใน Rabin, Tal (เอ็ด.) Advances in Cryptology - CRYPTO 2010, การประชุม Cryptology Conference ประจำปีครั้งที่ 30, ซานตาบาร์บาร่า, แคลิฟอร์เนีย, สหรัฐอเมริกา, 15-19 สิงหาคม 2553. Proceedings บันทึกการบรรยายทางวิทยาการคอมพิวเตอร์ ฉบับที่6223. สปริงเกอร์ หน้า333– 350. ดอย : 10.1007/978-3-642-14623-7_18 . ไอเอสบีเอ็น 978-3-642-14622-0.

[4] Krantz, Steven G. (2011), The Proof is in the Pudding: The Changing Nature of Mathematical Proof , New York: Springer, หน้า203, doi : 10.1007/978-0-387-48744-1 , ISBN 978-0-387-48908-7, MR 2789493

[5] Arora, Sanjeev ; Barak, Boaz (2009), ความซับซ้อนในการคำนวณ , เคมบริดจ์: สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์, หน้า230, doi : 10.1017/CBO9780511804090 , ISBN 978-0-521-42426-4MR 2500087 , S2CID 215746906

[6] Buhler, JP; Lenstra, HW Jr.; Pomerance, Carl (1993). "การแยกตัวประกอบจำนวนเต็มด้วยตะแกรงสนามจำนวน" การพัฒนาตะแกรงสนามจำนวนบันทึกการบรรยายทางคณิตศาสตร์ เล่มที่1554สปริงเกอร์ หน้า50–94 doi : 10.1007 / BFb0091539 hdl : 1887/2149 ISBN 978-3-540-57013-4สืบค้นข้อมูลเมื่อ วัน ที่12 มีนาคม 2564

[7] Vandersypen, Lieven MK; และคณะ (2001). "การสร้างอัลกอริทึมการแยกตัวประกอบควอนตัมของ Shor ในทางปฏิบัติโดยใช้เรโซแนนซ์แม่เหล็กนิวเคลียร์" Nature . 414 (6866): 883– 887. arXiv : quant-ph/0112176 . Bibcode : 2001Natur.414..883V . doi : 10.1038/414883a . PMID 11780055 . S2CID 4400832 .

[8] Lance Fortnow (13 กันยายน 2002). "Computational Complexity Blog: Complexity Class of the Week: Factoring" .

[9] Goldreich, Oded ; Wigderson, Avi (2008), "IV.20 ความซับซ้อนในการคำนวณ", ในGowers, Timothy ; Barrow-Green, June ; Leader, Imre (บรรณาธิการ), The Princeton Companion to Mathematics , Princeton, New Jersey: Princeton University Press, หน้า575– 604, ISBN 978-0-691-11880-2, MR 2467561 โปรดดูโดยเฉพาะหน้า 583

[Bressoud_and_Wagon-10] 1 2 David BressoudและStan Wagon (2000). หลักสูตรทฤษฎีจำนวนเชิงคำนวณ . สำนักพิมพ์ Key College Publishing/Springer. หน้า168–169 . ISBN 978-1-930190-10-8.

[1982-schnorr-11] Schnorr, Claus P. (1982). "การวิเคราะห์ที่ละเอียดขึ้นและการปรับปรุงอัลกอริทึมการแยกตัวประกอบบางอย่าง"วารสารอัลกอริทึม 3 ( 2): 101– 127. doi : 10.1016/0196-6774(82)90012-8 . MR 0657269 . เก็บถาวรจากต้นฉบับเมื่อวันที่ 24 กันยายน 2017

[1987-seysen-12] Seysen, Martin (1987). "อัลกอริทึมการแยกตัวประกอบเชิงความน่าจะเป็นด้วยรูปแบบกำลังสองของดิสคริมิแนนต์เชิงลบ"คณิตศาสตร์ของการคำนวณ 48 ( 178): 757– 780. doi : 10.1090/S0025-5718-1987-0878705-X . MR 0878705 .

[1988-lenstra-13] Lenstra, Arjen K (1988). "การแยกตัวประกอบที่รวดเร็วและเข้มงวดภายใต้สมมติฐานรีมันน์ทั่วไป" (PDF) . Indagationes Mathematicae . 50 (4): 443– 454. doi : 10.1016/S1385-7258(88)80022-2 .

[lenstra-pomerance-14] 1 2 Lenstra, HW; Pomerance, Carl (กรกฎาคม 1992). "ขอบเขตเวลาที่เข้มงวดสำหรับการแยกตัวประกอบจำนวนเต็ม" (PDF)วารสารของสมาคมคณิตศาสตร์อเมริกัน 5 ( 3): 483– 516. doi : 10.1090/S0894-0347-1992-1137100-0 . MR 1137100 .

1

[

[

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]