ถ้าจำนวน b บิตเป็นผลคูณของจำนวนเฉพาะ 2 ตัวที่มีขนาดใกล้เคียงกันแล้ว จะไม่มีขั้นตอนวิธีใดๆ ที่สามารถแยกตัวประกอบมันได้ภายในเวลาแบบพหุนาม (polynomial time) กล่าวคือ ไม่สามารถแยกตัวประกอบได้ภายใน O (bk) เมื่อ k คือค่าคงที่ค่าหนึ่ง ปัจจุบันมีขั้นตอนวิธีหลายขั้นตอนที่เร็วกว่า O ((1+ε) b) เมื่อ ε คือจำนวนบวก กล่าวคือ มีประสิทธิภาพเชิงเวลาแบบใต้เลขชี้กำลัง (sub-exponential)
ขั้นตอนวิธีที่มีเวลาการทำงานเชิงเส้นกำกับที่ดีที่สุดคือ การกรองตัวเลขในขอบเขตแบบธรรมดา (general number field sieve (GNFS)) สำหรับจำนวน b บิตจะมีความซับซ้อนเป็น
สำหรับคอมพิวเตอร์ทั่วไป การกรองตัวเลขในขอบเขตแบบธรรมดา (GNFS) คือขั้นตอนวิธีที่ดีที่สุดสำหรับจำนวนขนาดใหญ่มากๆ (เลข 100 หลักขึ้นไป) แต่สำหรับควอนตัมคอมพิวเตอร์ ปีเตอร์ ชอร์ ได้ค้นพบขั้นตอนวิธีที่สามารถแก้ปัญหาได้ในเวลาแบบพหุนามในปี พ.ศ. 2537 ขั้นตอนวิธีของชอร์ใช้เวลาการทำงานเพียงแค่ O (b3) และใช้ปริภูมิ O (b) สำหรับจำนวน b บิต
โดนัลด์ คนูธ. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Section 4.5.4: Factoring into Primes, pp. 379–417.
Richard Crandall and Carl Pomerance (2001). Prime Numbers: A Computational Perspective (1st ed.). Springer. ISBN0-387-94777-9. Chapter 5: Exponential Factoring Algorithms, pp. 191–226. Chapter 6: Subexponential Factoring Algorithms, pp. 227–284. Section 7.4: Elliptic curve method, pp. 301–313.
แหล่งข้อมูลอื่น
A collection of links to factoring programs
Richard P. Brent, "Recent Progress and Prospects for Integer Factorisation Algorithms", Computing and Combinatorics", 2000, pp. 3-22. download
Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P." Annals of Mathematics 160 (2) : 781-793 (2004). August 2005 version PDF
[1] is a public-domain integer factorization program for Windows. It claims to handle 80-digit numbers. See also the web site for this program MIRACL
The RSA Challenge Numbers - a factoring challenge, no longer active.
Eric W. Weisstein, “RSA-640 Factored” MathWorld Headline News, November 8, 2005
Qsieve, a suite of programs for integer factorization. It contains several factorization methods like Elliptic Curve Method and MPQS.
Source code by Paolo Ardoino, Three known algorithms and C source code.
Factorization Source Code: by Paul Herman & Ami Fischman, C++ source code for many factorization algorithms including Pollard Rho & Shor's.
a database containing factorizations, complete and incomplete, of over 80 million numbers.
สิงหาคม 13, 2021
การแยกต, วประกอบจำนวนเต, ในทฤษฎ, จำนวน, งกฤษ, integer, factorization, หร, การแยกต, วประกอบเฉพาะ, งกฤษ, prime, factorization, อการแบ, งย, อยจำนวนประกอบออกเป, นต, วหารไม, วหารท, ไม, ใช, วม, นเอง, หลายๆ, งเม, อค, ณต, วหารไม, ดเหล, าน, นเข, าด, วยก, นจะได, ผลล, พธ. inthvsdicanwn karaeyktwprakxbcanwnetm xngkvs integer factorization hrux karaeyktwprakxbechphaa xngkvs prime factorization khuxkaraebngyxycanwnprakxbxxkepntwharimchd twharthiimich 1 kb twmnexng hlay tw sungemuxkhuntwharimchdehlannekhadwykncaidphllphthdngedimemuxcanwnmikhnadihymak immikhntxnwithikaraeyktwprakxbkhxngcanwnetmid thimiprasiththiphaphephiyngphx inpi 2009 khwamphyayaminkaraeyktwprakxbkhxngelkh 232 hlk idsaerclng cakkarichekhruxngckrmakkwa 100 ekhruxngphayinrayaewla 2 pi khwamyakkhxngpyhaaehlanikhuxhwickhxngkhntxnwithibangxyanginwithyakarekharhslb echn RSAcanwnthimikhwamyawethakn ichwacaaeyktwprakxbdwykhwamyakethakn krnithiyakthisudkhxngpyhaehlani sahrbklwithithirukninpccubn khuxcanwnkhrungechphaa semiprime sungkkhuxcanwnthiepnphlkhunkhxngcanwnechphaa 2 twcakthvsdibthmulthankhxngelkhkhnit canwnetmbwkthuktwcamikaraeyktwprakxbechphaathiaetktangkn enuxha 1 khwamyakaelakhwamsbsxn 2 ewlakarthanganthikhadhwng 3 khntxnwithikaraeyktwprakxbtang 3 1 wtthuprasngkhechphaa 3 2 wtthuprasngkhthwip 3 3 khntxnwithithimichuxesiyngxun 4 xangxing 5 aehlngkhxmulxunkhwamyakaelakhwamsbsxn aekikhthacanwn b bitepnphlkhunkhxngcanwnechphaa 2 twthimikhnadiklekhiyngknaelw caimmikhntxnwithiid thisamarthaeyktwprakxbmnidphayinewlaaebbphhunam polynomial time klawkhux imsamarthaeyktwprakxbidphayin O bk emux k khuxkhakhngthikhahnung pccubnmikhntxnwithihlaykhntxnthierwkwa O 1 e b emux e khuxcanwnbwk klawkhux miprasiththiphaphechingewlaaebbitelkhchikalng sub exponential khntxnwithithimiewlakarthanganechingesnkakbthidithisudkhux karkrxngtwelkhinkhxbekhtaebbthrrmda general number field sieve GNFS sahrbcanwn b bitcamikhwamsbsxnepn O exp 64 9 b 1 3 log b 2 3 displaystyle O left exp left left begin matrix frac 64 9 end matrix b right 1 over 3 log b 2 over 3 right right dd sahrbkhxmphiwetxrthwip karkrxngtwelkhinkhxbekhtaebbthrrmda GNFS khuxkhntxnwithithidithisudsahrbcanwnkhnadihymak elkh 100 hlkkhunip aetsahrbkhwxntmkhxmphiwetxr pietxr chxr idkhnphbkhntxnwithithisamarthaekpyhaidinewlaaebbphhunaminpi ph s 2537 khntxnwithikhxngchxrichewlakarthanganephiyngaekh O b3 aelaichpriphumi O b sahrbcanwn b bitewlakarthanganthikhadhwng aekikhkhntxnwithikaraeyktwprakxbepnkhntxnwithiechingkhwamnacaepn hrux khntxnwithiaebbsum ewlakarthanganthikhadhwngkhxngmncungimekin L n 1 2 1 o 1 displaystyle L n left 1 2 1 o 1 right khntxnwithikaraeyktwprakxbtang aekikhwtthuprasngkhechphaa aekikh ewlakarthangankhunxyukbkhunsmbtikhxngcanwnthicaaeyktwprakxb twxyangechn khntxnwithithdlxngkarhar thukcdekhahmwdwtthuprasngkhechphaa ephraawaewlakarthanganepnsdswntamkhnadkhxngtwprakxbthielkthisud karharechingthdlxng khntxnwithiorhkhxngphxllard khntxnwithiphilbhnungkhxngphxllardwtthuprasngkhthwip aekikh ewlakarthangankhunxyukbkhnadkhxngcanwnetmthicathakaraeyktwprakxbephiynglaphng taaekrngkalngsxng karkrxngtwelkhinkhxbekhtaebbthrrmdakhntxnwithithimichuxesiyngxun aekikh khntxnwithikhxngchxrxangxing aekikhodnld khnuth The Art of Computer Programming Volume 2 Seminumerical Algorithms Third Edition Addison Wesley 1997 ISBN 0 201 89684 2 Section 4 5 4 Factoring into Primes pp 379 417 Richard Crandall and Carl Pomerance 2001 Prime Numbers A Computational Perspective 1st ed Springer ISBN 0 387 94777 9 Chapter 5 Exponential Factoring Algorithms pp 191 226 Chapter 6 Subexponential Factoring Algorithms pp 227 284 Section 7 4 Elliptic curve method pp 301 313 aehlngkhxmulxun aekikhA collection of links to factoring programs Richard P Brent Recent Progress and Prospects for Integer Factorisation Algorithms Computing and Combinatorics 2000 pp 3 22 download Manindra Agrawal Neeraj Kayal Nitin Saxena PRIMES is in P Annals of Mathematics 160 2 781 793 2004 August 2005 version PDF 1 is a public domain integer factorization program for Windows It claims to handle 80 digit numbers See also the web site for this program MIRACL The RSA Challenge Numbers a factoring challenge no longer active Eric W Weisstein RSA 640 Factored MathWorld Headline News November 8 2005 Qsieve a suite of programs for integer factorization It contains several factorization methods like Elliptic Curve Method and MPQS Source code by Paolo Ardoino Three known algorithms and C source code Factorization Source Code by Paul Herman amp Ami Fischman C source code for many factorization algorithms including Pollard Rho amp Shor s a database containing factorizations complete and incomplete of over 80 million numbers ekhathungcak https th wikipedia org w index php title karaeyktwprakxbcanwnetm amp oldid 4760454, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,
