New factoring interface

Ethan Slota <[email protected]>
Newsgroups gmane.comp.mathematics.pari.devel
Message-ID <CAC6XWY127eHy2AVKeO2Jdt7fKKs3ppeL-4Vcbapko0cY0i3DNA@mail.gmail.com>
I've been using PARI/GP for a while now and it's immensely helpful with my
number theory calculations. I also use it a lot for general factorization
as it implements algorithms other than ECM and the QS. With factorization,
though, there is an issue I run into a lot: I haven't been able to find any
way to get an "incremental" factorization.

You have to get a full factorization even if you don't use all of it, which
can be a big slowdown. For example, searching for k-almost primes --
without any builtin functions, you'll need to perform a full factorization.

If some looping construct like `foreachfactor(f = n, ...)' existed, you
could write a function `is_k_almost_prime` as `(n, k) -> my(count = 0);
foreachfactor(f = n, count++; if(count > k, return(0))); 1'. In many cases,
it would be faster than `(n, k) -> bigomega(n) == k'.

Furthermore, if this returns an incremental factorization, I think there
should be a flag (or a separate function) to enable a sorted result. I
would use it mostly for counting factors, so order is not significant...
simply run factoring algorithms until you find a factor, return it, and go
again.

I know that there is at least some foundation already present for this in
GP: set debug to a value >0 and run `factorint' on some number. The factors
should just get exposed to the user.

- Ethan
lmpx.com only provides a reader for public news (NNTP) servers. It is not affiliated with the servers or forums shown here and is not responsible for the content of articles, which is written by their respective authors.