Bloom filters are very efficient, especially with low hit rates as in your case.

Speed, scalability and low memory are major advantages. Disadvantages include a tunable rate of false positives and not telling which phone number did match.

Your application could use a precomputed and 'store'ed filter. Reimplement the algorithm using Bit::Vector if you need more speed.