[Polizeiposaune]

if it's really as simple as p = q xor 6 or even p|6 == q|6, I'd think that trial division starting with the first odd number less than the square root would get you there in a handful of trials.