The vast majority of work on the efficiency of lattice-based cryptography, including fully homomorphic encryption (FHE), has relied on cyclotomic number fields and rings. This is because cyclotomics offer a wide variety of benefits, including good geometrical properties, fast ring arithmetic, and rich homomorphic operations like vectorized (SIMD) operations on “packed” plaintexts, automorphisms, and ring-switching. However, selecting a suitable cyclotomic that has the desired number and type of plaintext “slots,” while also balancing security and efficiency, is a highly constrained problem that often lacks an ideal solution, resulting in wasted SIMD capacity and lost efficiency. This work provides a suite of tools for instantiating ring-based lattice cryptography to work over subfields of cyclotomics, which provide more flexibility and better-fitting parameters for applications. A particular focus is on realizing FHE with optimal plaintext packing and homomorphic SIMD parallelism for any plaintext characteristic, along with efficient packed bootstrapping that fully exploits this parallelism. Toward this end, this (two-part) work makes the following main technical contributions, all of which are catalyzed by Galois theory: