Return to Answer

This idea was first studied by Shanks, Pollard, Atkin and Rickert, although they didn't write a paper as far as I know. Schnorr and Lenstra gave a heuristic time complexity analysis in their 1987 paper. Since there's no standard name, I'll call it the class group method CGM.

The time complexity of CGM is soft-O of $L_n[1/2]$ meaning we drop logarithmic factors. There's a second constant in the time complexity but its not a strong predictor of an algorithm's practical performance so I'll ignore that. This time complexity is like all algorithms for factoring $n$ from that period with the sole exception of ECM. The time complexity of ECM is soft-O of $L_p[1/2]$ where $p$ is the smallest prime factor. Note that $n$ doesn't show up in the time complexity. In practice, the size of $p$ is the most important factor in the algorithm's performance.

There have been attempts to make CGM more competitive with ECM. The challenge there is that for ECM the practical performance is controlled by the size of the smallest prime factor of $n$ rather than the number itself (just what the time complexity would lead you to think). This is not true for CGM.

However, in the special case that $n$ is not squarefree there is new work on an algorithm that improves on CGM. The algorithm's time complexity depends on the size of the squarefree part of $n$. On the practical side, the author gives some evidence that the algorithm is fast compared to the best factoring libraries available for numbers of the form $n=pq^2$ where the primes $p$ and $q$ are of a certain size.

This algorithm takes advantage of properties of class groups of non-maximal orders. Modifying it to get a time complexity like ECM's would be hard and require a new idea.

This idea was first studied by Shanks, Pollard, Atkin and Rickert, although they didn't write a paper as far as I know. Schnorr and Lenstra gave a heuristic time complexity analysis in their 1987 paper. Since there's no standard name, I'll call it the class group method CGM.

The time complexity of CGM is soft-O of $L_n[1/2]$ meaning we drop logarithmic factors. There's a second constant in the time complexity but its not a strong predictor of an algorithm's practical performance so I'll ignore that. This time complexity is like all algorithms for factoring $n$ from that period with the sole exception of ECM. The time complexity of ECM is soft-O of $L_p[1/2]$ where $p$ is the smallest prime factor. Note that $n$ doesn't show up in the time complexity. In practice, the size of $p$ is the most important factor in the algorithm's performance.

There have been attempts to make CGM more competitive with ECM. The challenge there is that for ECM the practical performance is controlled by the size of the smallest prime factor of $n$ rather than the number itself (just what the time complexity would lead you to think). This is not true for CGM.

However, in the special case that $n$ is not squarefree there is new work on an algorithm that improves on CGM. The algorithm's time complexity depends on the size of the squarefree part of $n$. On the practical side, the author gives some evidence that the algorithm is fast compared to the best factoring libraries available for numbers of the form $n=pq^2$ where the primes $p$ and $q$ are of a certain size.

This algorithm takes advantage of properties of class groups of non-maximal orders. Modifying it to get a time complexity like ECM's for general $n$ would be hard and require a new idea.

This idea was first studied by Shanks, Pollard, Atkin and Rickert, although they didn't write a paper as far as I know. Schnorr and Lenstra gave a heuristic time complexity analysis in their 1987 paper. Since there's no standard name, I'll call it the class group method CGM.

The time complexity of CGM is soft-O of $L_n[1/2]$ meaning we drop logarithmic factors. There's a second constant in the time complexity but its not a strong predictor of an algorithm's practical performance so I'll ignore that. This time complexity is like all algorithms for factoring $n$ from that period with the sole exception of ECM. The time complexity of ECM is soft-O of $L_p[1/2]$ where $p$ is the smallest prime factor. Note that $n$ doesn't show up in the time complexity. In practice, the size of $p$ is the most important factor in the algorithm's performance.

There have been attempts to make CGM more competitive with ECM. The challenge there is that for ECM the practical performance is controlled by the size of the smallest prime factor of $n$ rather than the number itself (just what the time complexity would led. This is not true for CGM.

However, in the special case that $n$ is not squarefree there is new work on an algorithm that improves on CGM. Perhaps with some further work this algorithm's time complexity will depend on the size of the squarefree part of $n$. On the practical side, the author gives some evidence that the algorithm is fast compared to the best factoring libraries available for numbers of the form $n=pq^2$ where the primes $p$ and $q$ are of a certain size.

This algorithm takes advantage of properties of class groups of non-maximal orders. Extending it to a broader class of $n$ would require new ideas.

This idea was first studied by Shanks, Pollard, Atkin and Rickert, although they didn't write a paper as far as I know. Schnorr and Lenstra gave a heuristic time complexity analysis in their 1987 paper. Since there's no standard name, I'll call it the class group method CGM.

The time complexity of CGM is soft-O of $L_n[1/2]$ meaning we drop logarithmic factors. There's a second constant in the time complexity but its not a strong predictor of an algorithm's practical performance so I'll ignore that. This time complexity is like all algorithms for factoring $n$ from that period with the sole exception of ECM. The time complexity of ECM is soft-O of $L_p[1/2]$ where $p$ is the smallest prime factor. Note that $n$ doesn't show up in the time complexity. In practice, the size of $p$ is the most important factor in the algorithm's performance.

There have been attempts to make CGM more competitive with ECM. The challenge there is that for ECM the practical performance is controlled by the size of the smallest prime factor of $n$ rather than the number itself (just what the time complexity would lead you to think). This is not true for CGM.

However, in the special case that $n$ is not squarefree there is new work on an algorithm that improves on CGM. The algorithm's time complexity depends on the size of the squarefree part of $n$. On the practical side, the author gives some evidence that the algorithm is fast compared to the best factoring libraries available for numbers of the form $n=pq^2$ where the primes $p$ and $q$ are of a certain size.

This algorithm takes advantage of properties of class groups of non-maximal orders. Modifying it to get a time complexity like ECM's would be hard and require a new idea.

This idea was first studied by Shanks, Pollard, Atkin and Rickert, although they didn't write a paper as far as I know. Schnorr and Lenstra gave a heuristic time complexity analysis in their 1987 paper.

There have been attempts to make it more competitive with ECM. The challenge there is that for ECM both the time complexity and practical performance are dominated by the size of the smallest prime factor of n rather than the number itself. This is not true for SPAR.

However, in the special case that n is not squarefree there is new work on a modification to SPAR that makes the time complexity depend on the size of the squarefree part.

This idea was first studied by Shanks, Pollard, Atkin and Rickert, although they didn't write a paper as far as I know. Schnorr and Lenstra gave a heuristic time complexity analysis in their 1987 paper. Since there's no standard name, I'll call it the class group method CGM.

The time complexity of CGM is soft-O of $L_n[1/2]$ meaning we drop logarithmic factors. There's a second constant in the time complexity but its not a strong predictor of an algorithm's practical performance so I'll ignore that. This time complexity is like all algorithms for factoring $n$ from that period with the sole exception of ECM. The time complexity of ECM is soft-O of $L_p[1/2]$ where $p$ is the smallest prime factor. Note that $n$ doesn't show up in the time complexity. In practice, the size of $p$ is the most important factor in the algorithm's performance.

There have been attempts to make CGM more competitive with ECM. The challenge there is that for ECM the practical performance is controlled by the size of the smallest prime factor of $n$ rather than the number itself (just what the time complexity would led. This is not true for CGM.

However, in the special case that $n$ is not squarefree there is new work on an algorithm that improves on CGM. Perhaps with some further work this algorithm's time complexity will depend on the size of the squarefree part of $n$. On the practical side, the author gives some evidence that the algorithm is fast compared to the best factoring libraries available for numbers of the form $n=pq^2$ where the primes $p$ and $q$ are of a certain size.

This algorithm takes advantage of properties of class groups of non-maximal orders. Extending it to a broader class of $n$ would require new ideas.