RC Schroeppel: Assuming some version of GRH, every [algebraic?] UFD has a hard-to-compute axiom-of-choice-style norm so that the Euclidean algorithm completes in four steps. [I've got some details wrong here, but you get the flavor.] This might be why the phrase 'Euclidean-for- the-norm' was introduced. 2^(1/5) generates a Euclidean field, with a not-too-hard dimishing norm. The idea is to compute the remainder's standard norm. If that's not smaller than norm(divisor), you adjust the quotient with a choice of ~50 values. Try adding +-1, +-2^1/5, +-4^1/5, etc. At least one will work. [This is my work, based on cutting up the unit cube into 100K boxes.] --well, that news sucks. If the reason this is hard is, the norms are incredibly hairy, then we're in trouble. RCS: [Hendrik?] Lenstra (in his thesis?) has a way of generating a lot of Euclidean fields. I never understood his trick, but it's not profound. --I think it's related to lattices and volumes. If you have a lattice in 3-space (or some dimensional space) and you have a convex body centered at origin, and maybe it has to be a centrosymmetric convex body, then if the convex body is large enough compared to the volume associated with any one lattice point, then body guaranteed to contain a lattice point. (Thm of Minkowski vastly generalizing the pigeonhole principle.) So in the Euclidean algorithm, have A & B, want to replace the bigger one B with "B mod A" which means B-k*A for some k. Well, note these points as k varies form a lattice, or translated lattice anyhow. To prove the euclidean algorithm descends you prove this lattice contains a smaller-norm point, which you do with Minkowski theorem or its ilk (in cases where you can make that work, anyhow). This sounds like a quite productive, easy. & obvious approach, but everybody since Minkowski has known about it, it is massively used for everything, so I doubt it'll work since if it did, they would have done it already? Or maybe I overestimate their wisdom. RCS: Puzzle on adjoining 1^(1/N): I though this was the distinction between regular & irregular primes, and there were about 50% each, empirically. This doesn't match the Masley-Montgomery result. What's my error? --I think your defn of regular & irregular primes is wrong. Kummer came up with "ideals" to get around the lack of unique factorization and still survive. RCS: What's an example of a totally-complex cubic field? :-)? --I think my defn of "totally complex" must have been wrong, I think I meant "complex" cubic field which is to say, not a totally-real one.