BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Unconditional computation of fundamental units in number fields Yee, Randy


The current state of the art algorithm for computing a system of fundamental units in a number field without relying on any unproven assumptions or heuristics is due to Buchmann and has an expected run time O(\Delta_K^{1/4 + \epsilon}). If one is willing to assume the GRH, then one can use the index-calculus method, which computes the logarithm lattice corresponding to the unit group. This method has subexponential complexity with respect to the logarithm of the discriminant, though both complexity and correctness of this method depend on the GRH. We discuss a hybrid algorithm which computes the basis of the logarithm lattice for a number field given a full rank sublattice as input. The algorithm is capable of certifying the output of the index calculus algorithm in asymptotically fewer operations than Buchmann's method.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International