Re: Factoring with Pari

[Bill Allombert <allomber@math.u-bordeaux.fr>]

On Fri, Dec 09, 2005 at 02:39:32AM +0100, Alessio Rocchi wrote:
> After having solved my previous problem (i finally decided to migrate to 
> linux), i'm here to ask again for help.
Good move!

> The problem is the following: I need to write C code (using Pari, of 
> course) whose result is that of decompose an integer in its prime factors.
> Under GP shell, i can simply write FACTOR(<int>).

factor(<int>) rather... uppercase are deprecated since seven years.

> I tried to write a C function to do it,  but it seems to be really 
> difficult (i began using Pari only two days ago...).
> May anyone help me (also posting an example, if possible)?

This one is very easy. This example will factor 2^128+1 and display the
result as a product.

#include <pari/pari.h>
int main(void)
{
  GEN n,F;
  long i;
  pari_init(4000000,2);
  n=gadd(gpowgs(gen_2,128),gen_1);
  F=factor(n);
  pariputsf("%Z = ",n);
  for(i=1;i<lg(F[1]);i++)
    pariputsf("%Z^%Z ",gcoeff(F,i,1),gcoeff(F,i,2));
  pariputsf("\n");
}

For more complex examples, try the GP2C compiler. It will generate
example PARI code at will from the GP code. For example if you
feed it with
func()=
{
  local(n,F);
  n=2^128+1;
  F=factor(n);
  print1(n," = ");
  for(i:small=1,#F[,1],
      print1(F[i,1],"^",F[i,2]));
  print()
}

you get

void
func(void)        /* void */
{
  GEN n, F;
  long l1;
  n = gaddgs(gpowgs(gen_2, 128), 1);
  F = factor(n);
  pariputsf("%Z = ", n);
  l1 = glength(gel(F, 1));
  {
    long i;
    for (i = 1; i <= l1; ++i)
      pariputsf("%Z^%Z", gcoeff(F, i, 1), gcoeff(F, i, 2));
  }
  pariputsf("\n");
  return;
}

Cheers,
Bill.