[archgoon]

pari-gp is freely available for linux, and it's source is available if you're interested in their implementation.

http://pari.math.u-bordeaux.fr/

The relevant file is

  src/basemath/ifactor1.c