  We report on an implementation of the Extended Tower Number Field Sieve
(ExTNFS) and record computation in a medium characteristic finite field
$\mathbb{F}_{p^4}$ of 512 bits size. Empirically, we show that sieving in a
4-dimensional box (orthotope) for collecting relations for ExTNFS in
$\mathbb{F}_{p^4}$ is faster than sieving in a 4-dimensional hypersphere. We
also give a new intermediate descent method, `descent using random vectors',
without which the descent stage in our ExTNFS computation would have been
difficult/impossible, and analyze its complexity.
