Boolean matching is one of the most important fundamental algorithms in FPGA synthesis and architecture evaluations. However, existing Boolean matchers for FPGAs, even with numerous improvements, are still not scalable to complex PLBs and large circuits. This paper aims to improve the efficiency of Boolean matching using lookup tables implemented by Bloom filters, which can store terabyte-lookup tables with a desktop PC. The key improvement is to efficiently prune a large set of non-implementable functions use the Bloom filter. Using the area-oriented re-synthesis as an application, the experiments on a broad selection of benchmark sets show that the re-synthesis with our improved Boolean matcher is 18X faster than the one with an optimized SAT-based Boolean matcher, while preserving the quality of the re-synthesizer.