// Intrinsics used by code from paper 2:
// _Applications of the class field theory of global fields_, by Claus Fieker

intrinsic CyclicExtensions(k::FldNum, n::RngIntElt, B::RngIntElt) -> []
{Computes all cyclic n extensions of k of |Discriminant| = B. n must be prime}

  require IsPrime(n) : "Only prime extensions are allowed";

  m := MaximalOrder(k);
  l := [1*m];
  p := 2;

  // we have: Disc(K) = Disc(k)^n * f^{n-1}  (if n is prime....)
  // so Disc(k)^n * f^(n-1) < B =>
  //    f < (B/Disc(k)^n)^(1/(n-1))
  //
  //  suppose n is squarefree....
  //  then
  B := Floor((B / AbsoluteDiscriminant(m)^n)^(1/(n-1)));

  print "Bound for primes is ", B;

  if B eq 0 then
    return [];
  end if;

  while p le B do
    if n mod p eq 0 then
      max_exp := 1;
    else
      max_exp := 0;
    end if;

    if Gcd(n, p^max_exp*(p-1)) eq 1 then
      p := NextPrime(p);
      continue;
    end if;

    lp := Decomposition(m, p);

    llp := [];
    for j in lp do
      if n mod p eq 0 then
        max_exp := Floor(n*RamificationIndex(j[1]) / (n-1)) + 1;
      else
        max_exp := 1;
      end if;
      for i := 1 to max_exp by 1 do
        Append(~llp, j[1]^i);
      end for;
    end for;
    llp := { &* x : x in Subsets(Set(llp)) };

    l := [ i*j : i in llp, j in l | Norm(i)*Norm(j) le B ];
    printf "size now %o\n", #l;
    p := NextPrime(p);
  end while;

  printf "Having to consider %o ideals...\n", #l;

  s := [];
  for i in l do
    _ := TwoElement(i);
    printf "checking %o\n in k %o\n\n", i, k;

    if (n mod 2 eq 0) then
      A := AbelianExtension(i, [ x : x in [1..Signature(k)] ]);
    else
      A := AbelianExtension(i);
    end if;
    if Degree(A) mod n ne 0 then continue; end if;
    if Conductor(A) ne i then continue; end if;

    c := A`DefiningGroup;
    G := Domain(c`RcgMap);

    su := Subgroups(G : Quot := [n]);
    printf "has %o subgroups\n", #su;

    for j in su do
      q, mq := quo<G | j`subgroup>;
      a := AbelianExtension(Inverse(mq)*c`RcgMap);
      if Conductor(a) ne i then continue; end if;
      printf "got one!!!\n";
      Append(~s, a);
    end for;
  end for;

  return s;
end intrinsic;


intrinsic ListDeg4Fields(B::RngIntElt) -> []
{Finds all imprimitive degreee 4 fields with |Discriminant| B}

  s := [];
  for i:= -B to B do
    if not IsFundamentalDiscriminant(i) then
      continue;
    end if;

    k := QuadraticField(i);
    s cat:= CyclicExtensions(k, 2, B);
  end for;

  return s;
end intrinsic;


intrinsic AbsoluteDiscriminant(L::FldAb) -> RngIntElt
{}
  return Discriminant(BaseRing(L))^Degree(L) * Norm(Discriminant(L));
end intrinsic;

intrinsic FindDuplicates(L::[FldAb]) -> []
{Removes duplicates from L (isomorphic fields)}

  l := [ AbsoluteDiscriminant(x) : x in L ];
  Sort(~l, ~p);
  L := PermuteSequence(L, p);

  for i := 1 to #L do
    j := i+1;
    i;
    while j le #L do
      j;
      if l[i] eq l[j] then
        <i,j>;
        if IsIsomorphic(SimpleExtension(NumberField(L[i])),
                        SimpleExtension(NumberField(L[j]))) then
          Remove(~L, j);
          Remove(~l, j);
        else
          j +:= 1;
        end if;
      else
        break;
      end if;
    end while;
  end for;

  return L;
end intrinsic;