1. A data processing system for testing the primality of an integer, comprising: a recoding unit generating a new representation of the integer, a modular operation unit for calculating a plurality of modular operations; a loop control unit; and a decision unit deciding the primality or compositeness of the input integer, wherein the recoding unit scans a plurality of bits of the integer and selects a modular operation to be computed by the modular operation unit according to the scanned bits.