[adgjlsfhk1]

for about a decade, integer multiplication was at n4^log*(n) where log* is the iterated logarithm.

Also the curently best factorization algorithm (GNFS) is at exp(k*log(n)^1/3log(log(n))^2/3).

Intro algorithms classes just tend to stay away from the really cursed runtimes since the normal ones are enough to traumatize the undergrads.

[hinkley]

Are BigInteger multiplications in logn² now or do they still have weird terms in them?

[adgjlsfhk1]

down to nlogn

[Sniffnoy]

Hey the asterisks in your reply got read as formatting so it's ended up messed-up.

[adgjlsfhk1]

oops. fixed.