\\Program to compute discrete logs by the index calculus
\\It could be much improved...
\\by Felipe Voloch


\\Choose r and the factor base will consist of the first r primes
{
v(r)=primes(r)
}

\\this computes the smallest primitivive root mod p
\\if you don't have one already

{
g(p)=lift(primroot(p))
}

\\precomputation of the discrete logs of the primes in the
\\factor base
\\first step, find equations
{
exponents(p,w)=w=[];for(s=1,3*r,k=lift(mod(random,p-1));
if(((g(p)^k)%p)/prod(1,n=1,r,v(r)[n]^(valuation((g(p)^k)%p,v(r)[n])))==1,
w=concat(w,[k]),));w
}
\\second step build matrix
{
matriz(p,u)=matrix(length(u),r,n,m,
valuation(g(p)^(u[n])%p,v(r)[m]))
}



\\PARI has problems with linear algebra over rings. 
\\I assume below that (p-1)/2 is prime

\\the next three functions solve the linear equations

{
precomp1(p,r)=
trans(inverseimage(mod(matriz(p,u),(p-1)/2),trans(mod(u,(p-1)/2))))
}

{
precomp2(p,r)=
trans(inverseimage(mod(matriz(p,u),2),trans(mod(u,2))))
}
{
precomp(p,r)=vector(r,j,
lift(precomp2(p,r)[j])*mod((p-1)/2,p-1)+mod(2,p-1)*lift(1/mod(2,(p-1)/2))*
lift(precomp1(p,r)[j]))
}

\\finally we can compute the discrete log of h

{
dlog(h,p,w)=x;k=lift(mod(random,p-1));
if(((h*g(p)^k)%p)/prod(1,n=1,r,v(r)[n]^(valuation((h*g(p)^k)%p,v(r)[n])))==1,
x=-mod(k,p-1)+
sum(mod(0,p-1),s=1,r,valuation((h*g(p)^k)%p,v(r)[s])*w[s]),
x=print("try again"));x
}