In this paper, we introduce a new public key cryptosystem based on hexadecimal algebra, which is a non-associative, non-commutative and alternativ; we call it HXDTRU. The security of HXDTRU with N dimension equals the security of NTRU with the 16N dimension, and HXDTRU with N dimension is sixteen times faster than NTRU with the 16N dimensions. Keywords: NTRU, HXDTRU, hexadecnion algebra, lattice hexadecnion