Factoring large integers is an open research problem. The issue is definitely nothing to do with Julia's handling of bignums, or its use of GMP (there is no competitive factoring algorithm in GMP).
Fixing that problem properly is on the order of about 120,000 lines of C code, if you want to be truly up-to-date. Here is a list of algorithms you need to factor big numbers fast: trial division perfect power testing lehmer pollard rho SQUFOF p-1 p+1 elliptic curve method quadratic sieve (self initialising, multiple polynomial, small, large and double large prime variants) general number field sieve (active open research area) then you need to be able to check for primality reliably to certify that you have actually fully factored your numbers, for which you will want a lookup table for small primes trial division strong probable prime test Lucas test Baillie-PSW Miller-Rabin Pocklington-Lehmer p-1 test Morrison's p+1 test (+ Brillhart, Lehmer, Selfridge improvements) APR-CL or ECPP You might like to look at the msieve library and the GMP-ECM library. That will take most of the burden off you. If you want to factor numbers bigger than about 100 decimal digits, you need something like CADO-NFS. If you want to factor numbers bigger than 200 digits you need a miracle. Hopefully flint will also have something relatively competitive by the end of the summer, though it isn't specialised just on those problems. We are still missing APR-CL, qsieve, ECM which we plan to add over the next few months to a year, and we don't have any plans for a general number field sieve at this point. Note that the primality testing in GMP is for probable prime testing only. It sometimes (exceedingly rarely) says composite numbers are prime. It does no primality proving (i.e. it has no APR-CL or ECPP).
