Faster class group computations using norm relations
Saturation
Problem : from R ⊂ K×, compute R0 = {x ∈ K× s.t. xd ∈ R}.
Saturation algorithm (Pohst–Zassenhaus, rediscovered many
times) :
I Use reduction modulo primes to detect powers.
I Compute roots.
I Terminate or add more primes.
BFHP : under GRH, polynomial bound on the set of primes
required.