• given n find p1,p2,...,pk s.t. n=p1•p2•...•pk

 

• special hard case (RSA numbers): n=p1•p2

 

• best solutions have running time

 

Ω(ec|n|ß (log |n|)1-ß), ( 0<ß<1 )

 

• RSA-155 (~512 bits) largest factored so far