The Carmichael Numbers can be factorized in polynomial time.
Are weak fermat pseudoprimes (w.r.t. a given base) easy to factorize as well?
What are some large/broad classes of numbers that are easy to factorize (i.e. in polynomial time). This part is pretty broad, so i would be thankful if someone can provide some examples of these classes and more importantly a few good up-to date sources, that studies/lists the classes of numbers and their factorization difficulty ?
Six classes of "lucky numbers", that can be factorized easily, are discussed on page 107 and following of Integer Factoring by Arjen Lenstra (2000). These include: trial division by a small prime (very effective, since 88% of all positive integers have a factor $< 100$, and almost 92% have a factor $< 1000$), Pollard's rho method and the elliptic curve method (if some random number close to some prime factor of $n$ is "smooth", in the sense that all its prime factors are small), Fermat's method (for numbers that have two large prime factors close to each other), congruence of squares (for numbers $n$ for which there exist $x$ and $y$ such that $x^2-y^2$ is a multiple of $n$).
Here is a large class of numbers that can be factored in polynomial time: products of a smooth number and large prime. More precisely, a number less than $x$ whose second largest prime factor is less than $\exp(O((\log \log x)^2/\log \log \log x))$ can be factored in polynomial time. There are about $$x(\log\log x)^2/(\log x \log\log\log x)$$ such numbers, so this is quite a large class. You can read more in Granville's survey Smooth numbers: computational number theory and beyond.
Here are some classes of numbers that can be fully factored efficiently with high probability.
Let $p_i$ be primes such that $2 p_i + 1$ are also primes and $q$ arbitrary prime.
Let $n'=\prod_{i=1}^n (2p_i+1)$ and $n''=\prod_{i=1}^n p_i$.
Let $N= q n' n ''$. Then $N$ can be factored completely efficiently with high probability.
We have $\phi(n')=2^n n''$. Knowing a multiple of the totient function factors the number with high probability (essentially always). For reference see Wong's answer here: https://math.stackexchange.com/questions/191896/does-knowing-the-totient-of-a-number-help-factoring-it
By this argument we factor $n'$ and from $p=2p_i+1$ we get $p_i$ which is prime.This leaves only $q$.
By similar argument for sigma, we can replace $2p_i+1$ by $2 p_i -1$.
Added 2016-12-01
A New Special-Purpose Factorization Algorithm Qi Cheng ∗ In this paper, a new factorization algorithm is presented, which finds a prime factor $p$ of an integer $n$ in time $(D\log{n})^{O(1)} $, if $4p - 1 = Db^2$ where $D$ and $b$ are integers. Hence this algorithm will factor a number efficiently, if it has a prime factor p such that $4p - 1$ is a product of a small integer and a square.
Pollard's $p-1$ method will likely find $p$ quickly if $p-1$ is a least common multiple of positive integers, all of which are small. (To put it another way, $p-1$ is a product of small primes, none of which is repeated too many times.)
There are analogous methods that target $p+1$ or any other product of cyclotomic polynomials in $p$; the key is to compute in a different group modulo $p$. Computation in $F_{p^{2}}^{\times}$, for example, can be accomplished using sequences satisying second-order linear recurrences, using $2 \times 2$ matrices, or other methods.
Also, if there is a small (positive integral) multiplier $c$ such that $n$ has a divisor $d$ such that $cd$ and $\frac{n}{d}$ are very close, a variant of Fermat's method with multipliers will factor $n$ by finding $cn = (\frac{cd+\frac{n}{d}}{2})^{2}-(\frac{cd-\frac{n}{d}}{2})^{2}$. (This assumes that $c$ will not interfere with the calculation of $\gcd (cd,n)$. But if $c$ is small, then trial division up to $c$, among other methods, can rule out $n$ having such small prime factors.)
