2

Does PARI/GP have a function for finding the smallest prime factor of a t_INT or otherwise perform a partial factorization of an integer?

For example, if I have the number:

a=261432792226751124747858820445742044652814631500046047326053169701039080900441047539208779404889565067

it takes a long time to do factor(a) because a contains two huge prime factors. However, it is quite easy to find that 17 is a divisor of a.

Of course in this case I could have used just forprime(p=2,,a % p == 0 && return(p)) or a similar trial division to find the factor. But if the least factor had had 20 decimal figures, say, that would be impractical, and I might have wanted to use the sophisticated methods of factor in that case.

So it would be ideal if I could call factor with some kind of flag saying I will be happy with any partial factorization, or saying that all I care about is the smallest non-trivial divisor, etc.

Jeppe Stig Nielsen
  • 60,409
  • 11
  • 110
  • 181
  • Have you thought about a variant of the [Lenstra elliptic-curve factorization](https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization) (which specializes in getting small factors)? You could modify it to break once it has found any factor. – Joseph Wood Oct 20 '17 at 01:22
  • @JosephWood PARI's `factor` or `factorint` function already uses elliptic-curve methods as one of its approaches. I know I could code my own elliptic curve implementation, but I was asking if there was something built-in in PARI/GP. – Jeppe Stig Nielsen Oct 20 '17 at 12:22
  • 1
    The PARI library has the function `Z_factor_until` which might be useful. But proving that you've found the smallest prime factor isn't generally easy, choose one option: works only on special numbers, some only 'with high probability' rather than certainty; long running time; works only on small numbers. – Charles Dec 08 '17 at 04:48
  • 1
    Also, for numbers larger than 40 digits, you're much better off with [yafu](https://sourceforge.net/projects/yafu/). – Charles Dec 08 '17 at 04:49

1 Answers1

1

A very simple partial answer to my question is that factor has an optional argument lim, so you can just say:

factor(a, 10^5)

for example, and only factors below 10^5 will appear in the result (the cofactor greater than 10^5 can be composite!).

The optional argument to factorint is entirely different, a bit-wise "flag", and it does not allow to specify a limit. That was probably what confused me. As an example:

factorint(a, 1+8)

selects flags 1 ("avoid MPQS") and 8 ("don't run final ECM").

Jeppe Stig Nielsen
  • 60,409
  • 11
  • 110
  • 181