Is it not enough to simply check modulo more primes of the form 3k+1?
I suspect you could do the computation faster if you didn't check 7, 9, 13, and 19 separately... but instead computed it once modulo 7*9*13*19, and uesd that to compute the residue modulo your other moduli. (Or even just stored an array indicating whether an element modulo 7*9*13*19 is a cube)
