I'd say that it makes it at best only 24 times easier. Which cuts the problem down approx. 1.4 order of magnitudes which doesn't matter much when the problem scales exponentially.

Ahh, I was thinking that p^2 - 1 = 24n held for any n as well as any p, but I can see that's not necessarily the case. Thanks

I think such a test is similar to skipping multiples of low primes like 2,3,5,7,... But who knows, maybe it might be more efficient: only one modulo division needed, rather than many :)