The search for all solutions in the crypto-arithmetic problem is performed with two kinds of adaptive parallel genetic algorithm. Since the performance of genetic algorithms is critically determined by the architecture and parameters involved in the evolution process, an adaptive control is implemented on two parameters governing the relative percentages of preserved (survived) individuals and reproduced individuals (offspring). Adaptive parameter control in the first method involves the estimation of Shannon entropy associated with the fitness distribution of the population. In the second method, parameters are controlled by average values between the extreme and median fitness of individuals. Experiments designed to test two algorithms using crypto-arithmetic problems with ten and eleven alphabets are analyzed using the average first passage time to solutions. Results are compared with exhaustive search and show strong evidence that over 85% of the solutions in each problem can be found using our adaptive parallel genetic algorithms with a considerably faster speed. Furthermore, adaptive parallel genetic algorithm with the second method involving the median is consistently faster than the first method using entropy.