We propose a new algorithm for training a linear Support Vector Machine in the primal. The algorithm mixes ideas from non smooth optimization, subgradient methods, and cutting planes methods. This yields a fast algorithm that compares well to state of the art algorithms. It is proved to require $O(1/{lambdaepsilon})$ iterations to converge to a solution with accuracy $epsilon$. Additionally we provide an exact shrinking method in the primal that allows reducing the complexity of an iteration to much less than $O(N)$ where $N$ is the number of training samples.