Friday, December 16, 2016

[yyqaqeer] Instant factoring

What is the largest size general numbers which can be factored "instantly" according to human perception?  Provide it as a function in a calculator app (but it is a function that returns multiple values).  (Actually, returning just the least prime factor would be useful.)

Which algorithm should be used?  The crossover point where the number field sieve becomes more efficient than quadratic sieve is probably way beyond the timescale of "instant" so NFS will not be needed.  Experiments with Pari/GP find that quadratic sieve does produce useful results within 100 milliseconds.

We want a highly optimized parallel implementation to take advantage of multicore.  (This is the only failing of Pari/GP.)

Trying other algorithms leads to messy questions.  Other algorithms, e.g., elliptic curve method, tried before quadratic sieve can decrease average running time but will increase worst case running time.

The only factorizations useful for most people are probably either less than around 10000 (or smooth so that all factors are less than 10000) or greater than 2^1024 (the latter effectively impossible), so providing quick factorizations of medium sized numbers is probably overkill.

No comments :