Patent Document ID: 8374345
Application ID: 12366679
Patent Status: 1

Claim One:
1. A data processing system for testing the primality of a first integer, comprising: a first memory unit to store a second integer; a recoding unit to generate a new representation of the first integer; a bit manipulation operation unit; a modular multiplication unit; a loop control unit; and a decision unit to decide the primality or compositeness of the first integer, wherein the recoding unit scans a plurality of bits of the first integer and recodes the first integer to a base 2 w representation, provided that ‘w’ is a positive integer, wherein the bit manipulation operation unit processes a bit manipulation operation on the second integer based on the scanned bits, and wherein the bit manipulation operation comprises: an operation to clear all bits of the second integer to zero, an operation to select one bit of the second integer based on the base 2 w representation of the first integer, and an operation to set the selected one bit to one, wherein the modular multiplication unit calculates at least one modular multiplication based on the second integer, and wherein the modular multiplication unit calculates power of two modulo the first integer.