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

ในทฤษฎีจำนวน การแยกตัวประกอบจำนวนเต็ม (อังกฤษ: integer factorization) หรือ การแยกตัวประกอบเฉพาะ (อังกฤษ: prime factorization) คือการแบ่งย่อยจำนวนประกอบออกเป็นตัวหารไม่ชัด (ตัวหารที่ไม่ใช่ 1 กับ ตัวมันเอง) หลายๆ ตัว ซึ่งเมื่อคูณตัวหารไม่ชัดเหล่านั้นเข้าด้วยกันจะได้ผลลัพธ์ดังเดิมเมื่อจำนวนมีขนาดใหญ่มาก ไม่มีขั้นตอนวิธีการแยกตัวประกอบของจำนวนเต็มใดๆ ที่มีประสิทธิภาพเพียงพอ ในปี 2009 ความพยายามในการแยกตัวประกอบของเลข 232 หลัก ได้สำเร็จลง จากการใช้เครื่องจักรมากกว่า 100 เครื่องภายในระยะเวลา 2 ปี ความยากของปัญหาแหละนี้คือหัวใจของขั้นตอนวิธีบางอย่างในวิทยาการเข้ารหัสลับ เช่น RSAจำนวนที่มีความยาวเท่ากัน ใช่ว่าจะแยกตัวประกอบด้วยความยากเท่ากัน กรณีที่ยากที่สุดของปัญหาเหล่านี้ (สำหรับกลวิธีที่รู้กันในปัจจุบัน) คือจำนวนครึ่งเฉพาะ (semiprime) ซึ่งก็คือจำนวนที่เป็นผลคูณของจำนวนเฉพาะ 2 ตัวจากทฤษฎีบทมูลฐานของเลขคณิต จำนวนเต็มบวกทุกตัวจะมีการแยกตัวประกอบเฉพาะที่แตกต่างกัน

ใกล้เคียง

การแยกตัวประกอบ การแยกตัวประกอบจำนวนเต็ม การแยกทัศนคติออกเป็นสองขั้ว การแยกส้อม การแยกศาสนจักรกับอาณาจักร การแยกแบบโชเลสกี การแยกใช้อำนาจ การแยกสาย (บล็อกเชน) การแยกเดี่ยว การแยกคู่ยีนอย่างอิสระ

แหล่งที่มา

WikiPedia: การแยกตัวประกอบจำนวนเต็ม ftp://ftp.computing.dcu.ie/pub/crypto/factor.exe http://factordb.com/ http://www.rsasecurity.com/rsalabs/node.asp?id=209... http://mathworld.wolfram.com/news/2005-11-08/rsa-6... http://www.thorstenreinecke.de/qsieve/ http://citeseer.ist.psu.edu/327036.html http://www.shamus.ie/ http://www.cse.iitk.ac.in/users/manindra/algebra/p... http://www.frenchfries.net/paul/factoring/source.h... http://ardoino.altervista.org/blog/index.php?id=19