View source for Second category integer factoring

== Problem Description==
A general-purpose factoring algorithm, also known as a Category 2, Second Category, or Kraitchik family algorithm,[9] has a running time which depends solely on the size of the integer to be factored. This is the type of algorithm used to factor RSA numbers. Most general-purpose factoring algorithms are based on the congruence of squares method.

== Bounds Chart ==
[[File:Second_category_integer_factoringBoundsChart.png|1050px]]

== Step Chart ==
[[File:Second_category_integer_factoringStepChart.png|1050px]]

== Improvement Table ==
{| class="wikitable" style="text-align:center;" width="100%" 
 !width="20%" | Complexity Classes !! width="40%" | Algorithm Paper Links !! width="40%" | Lower Bounds Paper Links
 |-
| rowspan="1" | Exp/Factorial
| [https://www.ams.org/journals/mcom/1981-36-153/S0025-5718-1981-0595059-1/home.html Dixon's algorithm (1981)]

[https://www.ams.org/journals/bull/1931-37-10/S0002-9904-1931-05271-X/home.html Continued fraction factorization (CFRAC) (1931)]
|
|-
| rowspan="1" | Polynomial > 3
|
|
|-
| rowspan="1" | Cubic
|
|
|-
| rowspan="1" | Quadratic
| [https://www.ams.org/journals/mcom/1993-61-203/S0025-5718-1993-1182953-4/S0025-5718-1993-1182953-4.pdf Rational sieve (1993)]
|
|-
| rowspan="1" | nlogn
| [http://www.ams.org/notices/199612/pomerance.pdf General number field sieve (1996)]

[https://www.ams.org/journals/mcom/2008-77-261/S0025-5718-07-02010-8/S0025-5718-07-02010-8.pdf Shanks's square forms factorization (SQUFOF) (2007)]
|
|-
| rowspan="1" | Linear
|
|
|-
| rowspan="1" | logn
| [https://ieeexplore.ieee.org/document/365700/ Shor's algorithm Quantum Implementation (1994)]
|
|-|}