Re: Computation with two algebraic integers

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

On Thu, Jan 22, 2026 at 02:56:58PM +0100, Ewan Delanoy wrote:
> I have two algebraic integers g and h, and
> 
> - I know the minimal polynomial of g, stored in a variable called minpoly_for_g, which has degree 18 in g
> - I know the minimal polynomial of h, stored in a variable called minpoly_for_h, which has degree 72 in h
> - I also know an extra relation between g and h, in the form of a polynomial with integer coefficients called
> relator, and which has degree 17 in g, 71 in h. This relation ensures that g is unique in terms of h.
> 
> 
> My goal is to compute the (polynomial) expression of g in terms of h from those data.

So you have three polynomials
minpoly_for_g(x), minpoly_for_h(y) and relator(x,y) and you define g,h by

minpoly_for_g(g) = 0
minpoly_for_h(h) = 0
relator(g,h) = 0

What is the equation satisfied by the polynomial you are looking for ? 
Is it 
g = pol(h)

You should probably use some forms of resultants, like rnfequation.

> So far, all my attempts failed
> because of integer overflow at some point. For example, the most obvious method of applying the Euclidean algorithm
> overflows after a few iterations.

Probably, you need to use approximations, either p-adic, floating points or
multi modular (use CRT).  That is how most GP functions work.
For example, to compute a discriminant or a determinant, PARI compute it modulo
various prime of 63 bit and apply CRT.

Maybe provide a small example as a tested for experiment.

Cheers,
Bill.