Fastest tweetable integer factorizer

Question

The task is to find a non-trivial factor of a composite number.

Write code that finds a non-trivial factor of a composite number as quickly as possible subject to your code being no more than 140 bytes long. The output should just be the factor you have found.

Your code can take input and give output in any way that is convenient including for example as arguments to a function.

Test cases which list all the factors (you only need to output one)

187: 11 17
1679: 23 73
14369648346682547857: 1500450271 9576890767
34747575467581863011: 3628273133 9576890767
52634041113150420921061348357: 2860486313 5463458053 3367900313
82312263010898855308580978867: 264575131106459 311111111111113
205255454905325730631914319249: 2860486313 71755440315342536873 
1233457775854251160763811229216063007: 1110111110111 1000000000063 1111111999999
1751952685614616185916001760791655006749: 36413321723440003717 48112959837082048697

I won't score your answer on the following difficult test case which may be of interest for testing:

513231721363284898797712130584280850383: 40206835204840513073 12764787846358441471

Score

Your score is the combined time to factor all the test cases above with a penalty of 10 minutes for each failed factorization (all rounded to the nearest second). Your code should work for other integers too, that is shouldn't just hardcode these answers.

I will stop your code after 10 minutes.

If two people get the same score then the first answer wins.

Restrictions

Your code can't use any builtin or library function that performs integer factorization. You can assume the input takes less than 256 bits. All input numbers will be composite.

How will I time?

I will literally run time ./myprog on my Ubuntu system to do the timing so please also supply a complete program for me to run that includes any function you have defined.

A note for compiled languages

Compilation time must take no more than 1 minute on my machine.

Is it actually possible?

If you ignore the space constraints, then each one can be factored in less than 2 seconds on my computer using pure Python code + pypy.

So what is a non-trivial factoring algorithm?

Pollard's rho algorithm is fast and suitable for golfing. Of course there are plenty of other ways to factor an integer as well.

Even faster is the Quadratic sieve. It looks like a serious challenge to squeeze that into 140 bytes.

Leading scores

• SEJPM, 10 minutes penalty for the last test case + 16 seconds in Haskell

Answer 1

Haskell, 100 97 91 89 87 72 67 Bytes

Try It Online!

-3 bytes thanks to @flawr
-6 bytes thanks to @flawr again
-2 bytes thanks to @flawr yet again
-2 bytes thanks to an optimized set of parameters
-1 byte thanks to @flawrs yet another time
-14 bytes thanks to requirement to only having to output one factor
-5 bytes thanks to @AndersKaseorg

f n|let s x=mod(x*x+7)n;a#b|d<-gcd(b-a)n,d>1=d|c<-s b=s a#s c=5#s 5

This works for the first 5 test cases in unnoticable time.
This will probably time-out on the largest test case.

In general this will usually return one non-trivial factor in time proportional to the square root of the smallest factor.
It will not work on every input because it doesn't vary the polynomial and detection of the exceptional case is hard to do in 140 bytes.
It will also not output the full factorization, but rather a non-trivial factor and the division of the input by this factor.
It will also not sort the factors by size.

The method used is Pollard-Rho-Factoring with the standard starting value of 2 (with the standard x^2+1 polynomial applied once) and the non-standard polynomial constant factor of 7 (because 1 didn't work with 1679) for all further evaluations.

Full program (factor.hs):

import System.Environment(getArgs)

f n|let s x=mod(x*x+7)n;a#b|d<-gcd(b-a)n,d>1=d|c<-s b=s a#s c=5#s 5

main= do
      args <- getArgs
      print$f (read $ head args :: Integer)

Compile as $ ghc factor.hs (needs ghc installed).
Run as $ ./factor <number>.

Example run:

$ ./factor 187
11

---

Ungolfed code:

f n=g 5 (s 5)
   where s x=mod(x*x+7)n
         g a b = if d>1 then d else g(s a)(s(s b))
               where d=gcd(b-a)n

Computes the non-trivial factor by calling g with initial values. The polynomial is pre-applied on 2 here and re-applied on the result (5) so that the input to g (in a "where" clause) can always be readily used for the gcd-test. g (golfed version uses infix #) then tries to compute a non-trivial factor d (in the where clause in the un-golfed version, in-line in the golfed one) as the difference between the two inputs to g, if it succeeds returns said factor, else retries. Here it may generate n as the output if a==b and thus returns only a trivial factor, the proper approach to handle this would be to either vary the starting values upon this event or change the polynomial.

Answer 2

Pari/GP, 137 bytes, ~5 seconds

Using GP's built-in elliptic curve operations _{(and some underhanded parameter tuning)}:

ecm(n)=iferr(if(n%2==0,2,n%3==0,3,for(a=1,n,ellmul(ellinit(Mod([a,a^2-a-1],n)),[1,a],lcm([1..ceil(4^a^0.5)])))),e,gcd(n,lift(Vec(e)[3])))

ecm is a function that (ought to) return a factor. Try it online!

Test:

ecm(n)=iferr(if(n%2==0,2,n%3==0,3,for(a=1,n,ellmul(ellinit(Mod([a,a^2-a-1],n)),[1,a],lcm([1..ceil(4^a^0.5)])))),e,gcd(n,lift(Vec(e)[3])))

{
ns = [
  187,
  1679,
  14369648346682547857,
  34747575467581863011,
  52634041113150420921061348357,
  82312263010898855308580978867,
  205255454905325730631914319249,
  1233457775854251160763811229216063007,
  1751952685614616185916001760791655006749
  ]
}

test(n) = {
    d = ecm(n);
    if (!(1<d && d<n && n%d==0), error(d));
    print(n, ": ", d)
}

apply(test, ns)

quit

Ungolfed:

ecm(n) = {
  iferr(if(n%2 == 0, 2,
           n%3 == 0, 3,
           for(a = 1, n,
               /* x^3 + A*x + B = y^2 */
               E = ellinit(Mod([a, a^2-a-1], n)); /* [A, B] */
               x0 = [1, a]; /* [x, y] */
               B = ceil(4^a^0.5); /* ~ exp(sqrt(log(p))), p ~= exp(a) */
               print("a=", a, ", B=", B);
               ellmul(E, x0, lcm([1..B]))
              )
          ),
         ERR, gcd(n, lift(Vec(ERR)[3] /* = Mod(d, n) */)),
         errname(ERR)=="e_INV")
}

Sadly, handling the factors 2 and 3 uses many bytes. Bytes that could have been used to add a stage 2:

ecm(n)=iferr(for(a=1,n,Y=X=ellmul(E=ellinit(Mod([a,1],n)),[0,1],(B=ceil(4^a^0.5))!);for(z=0,9*B,Y=elladd(E,Y,X))),e,gcd(n,lift(Vec(e)[3])))

Answer 3

Wolfram Language (Mathematica), 81 bytes, 22 sec +10min(penalty)

uses Pollards ρ-algorithm x(0)=33, f(x)=x^8+1 and searches only x(2k)-x(k)

(x@0=33;n=#;v=1;x@k_:=x@k=Mod[x[k-1]^8+1,n];While[(r=GCD[x[2v]-x@v,n])<2,v++];r)&

Try it online!

Answer 4

Axiom, 137 bytes 9 minutes

p(n:PI):PI==(j:=1;a:=3;s:=n^.2;repeat(b:=j:=nextPrime(j);repeat(b<s=>(b:=b*j);break);a:=powmod(a,b,n);d:=gcd(a-1,n);d>1 or j>n=>break);d)

above the function p() that would implement p-1 algo for factoring below what to copy in a file for test on p() function

-- one has to copy this below text in a file name for example file.input
-- in one window where there is Axiom one could write 
-- )read C:\absolutepathwherethereisthatfile\file
-- and call the function test()
-- test()
-- the first character of all function and array must be afther a new line "\n"
)cl all
)time on
vA:=[187,1679,14369648346682547857,34747575467581863011,52634041113150420921061348357,82312263010898855308580978867,205255454905325730631914319249,1233457775854251160763811229216063007, 1751952685614616185916001760791655006749]

p(n:PI):PI==(j:=1;a:=3;s:=n^.2;repeat(b:=j:=nextPrime(j);repeat(b<s=>(b:=b*j);break);a:=powmod(a,b,n);d:=gcd(a-1,n);d>1 or j>n=>break);d)

-- this would try to factor n with p-1 Pollard method
pm1(n:PI):PI==
   j:=1;a:=3;s:=n^.2
   repeat
      b:=j:=nextPrime(j)
      repeat(b<s=>(b:=b*j);break)
      a:=powmod(a,b,n)
      d:=gcd(a-1,n);d>1 or j>n=>break
   d

test()==(for i in 1..#vA repeat output [vA.i, p(vA.i)])

results here:

(5) -> test()
   [187,11]
   [1679,73]
   [14369648346682547857,9576890767]
   [34747575467581863011,9576890767]
   [52634041113150420921061348357,2860486313]
   [82312263010898855308580978867,311111111111113]
   [205255454905325730631914319249,2860486313]
   [1233457775854251160763811229216063007,1111111999999]
   [1751952685614616185916001760791655006749,36413321723440003717]
                                                               Type: Void
                              Time: 496.78 (EV) + 53.05 (GC) = 549.83 sec

Answer 5

Axiom, 10 minutes + 31 seconds

A(a)==>a:=(a*a+7)rem n;z(n)==(p:=a:=b:=101;for i in 1..repeat(A(a);A(b);A(b);p:=mulmod(p,a-b,n);i rem 999<9=>(p:=gcd(p,n);p>1=>break));p)

z() is the function rho, one 137 bytes function; ungolfed z() and call it as rho(). It would suppose that gcd(0,n)=n so the loop stop and return for fail n.

)time on    
rho(n)==
  p:=a:=b:=101
  for i in 1..repeat
          A(a);A(b);A(b)
          p:=mulmod(p,a-b,n)
          i rem 999<9=>(p:=gcd(p,n);p>1=>break)
  p

va1:=[187,1679,14369648346682547857,34747575467581863011,52634041113150420921061348357,82312263010898855308580978867,205255454905325730631914319249,1233457775854251160763811229216063007, 1751952685614616185916001760791655006749]
p1()==(for i in 1..#va1-1 repeat output [va1.i,z(va1.i)]) 

results (z() is ok to all but the last number 1751952685614616185916001760791655006749 remain not factored (10 minutes) )

(6) -> p1()
   [187,17]
   [1679,23]
   [14369648346682547857,1500450271]
   [34747575467581863011,3628273133]
   [52634041113150420921061348357,2860486313]
   [82312263010898855308580978867,264575131106459]
   [205255454905325730631914319249,2860486313]
   [1233457775854251160763811229216063007,1111111999999]
                                                               Type: Void
                                 Time: 30.38 (EV) + 1.38 (GC) = 31.77 sec

(8) -> z(1679)
   (8)  23
                                                    Type: PositiveInteger
                                                              Time: 0 sec

Answer 6

APL(NARS), 140chars, 10+1 minutes

r←p m
r←j←1⋄a←2⋄s←m*.2
k←j←1πj
→4×⍳k≥s⋄k×←j⋄→3
→0×⍳(m≤k)∨1≥a←l a,k,m⋄→2×⍳1=r←m∨a-1

r←l w
(b e n)←w⋄r←1
→3×⍳0=2∣e⋄r←n∣r×b
b←n∣b×b⋄→2×⍳0<e←⌊e÷2

6+17+8+16+35 + 6+14+18+20= 140 Both functions have not check for validate input and use global variables so are not a trust if run with other functions... "l" is the function that some other could call "ltor" or "powmod", "p" use what they call "p-1" factoring method. "p" fail when return 1. I say "p" would fail in each prime number, 1 and some little number as 8 if all goes well.

   p¨187,1679,14369648346682547857x,34747575467581863011x,52634041113150420921061348357x,82312263010898855308580978867x,205255454905325730631914319249x,1233457775854251160763811229216063007x
11 73 9576890767 9576890767 2860486313 311111111111113 2860486313 1111111999999 

this above takes 1 minute

  p 513231721363284898797712130584280850383x
40206835204840513073 

this above 38 seconds. The problem is the number 1751952685614616185916001760791655006749x that has factors-1 so big that function "p" would take too much time here. One little solution could be use at end of "p" function one algo "baby step giant step" it seems they call it, that find here in 2 minutes the result, but they are many chars more than 140...

r←p1 n;j;a;s;k;t;h;m;q;z
r←j←1⋄a←2⋄s←n*.2
k←j←1πj
→4×⍳k≥s⋄k×←j⋄→3
→0×⍳(n≤k)∨1≥a←l a,k,n⋄→5×⍳1=r←n∨a-1⋄→0
→2×⍳j≤4e5⋄h←30030⋄m←l a,h,n⋄z←l m,13,n⋄q←{l a,⍵,n}¨q/⍨1=h∨q←⍳h-1⋄h←0
t←n∨¨1⌈¨∣¯1+z×q⋄t←t/⍨(1<t)∧t≠n⋄→7×⍳∼0≠≢t⋄r←↑t⋄→0
z←n∣z×m⋄→6×⍳2e4≥h+←1

This above function "p1" should factorize all examples in few minutes.

  p1¨187,1679,14369648346682547857x,34747575467581863011x,52634041113150420921061348357x,82312263010898855308580978867x,205255454905325730631914319249x,1233457775854251160763811229216063007x,1751952685614616185916001760791655006749x
11 73 9576890767 9576890767 2860486313 311111111111113 2860486313 1111111999999 36413321723440003717 

Answer 7

Python 3, 100 99 bytes, 45 40 39 seconds + 10 minute penalty

import math
def f(n):
 x=y=2;d=1
 while d<2:y=y*y+1;x,y=1+x*x%n,y*y%n+1;d=math.gcd(x-y,n)
 return d

Try it online!

Uses Pollard-Rho with initial value 2 and polynomial x^2+1.