My problem is the following:
Given a positive integer $n$, determine if $n$ has a divisor of the form $d=3+8k$ where $k$ is a non-negative integer.
I'm aware there are fast algorithms for checking primality/compositeness such as the AKS or Miller-Rabin tests, could these be adapted to give an answer to this problem in roughly the same time? Effectively we are checking for compositeness within a more restricted space (checking if $n$ has a divisor in $\{3,11,19,...\}$ rather than $\{2,3,4,...\}$).