Patent Document ID: 8060550
Application ID: 11535607
Patent Flag: 1

Claim One:
1. A method for transforming an integer using a processor comprising hardware and configured to perform the method, the method comprising: receiving a k-bit integer expressible as a modular factorization, the modular factorization comprising one or more factors, each factor having an exponent, wherein one of the factors has a base of 3; expressing, by a shifter and a first adder of the processor, the integer as a modulo product of a plurality of residues, a residue being a two-ones residue of the form (2 i +1), wherein i is an integer satisfying {1â‰¦iâ‰¦kâˆ’1, iâ‰ 2}; obtaining, by the processor, a discrete log of each of the plurality of residues from a lookup table, wherein the lookup table is indexed by the value i; iteratively calculating a modulo sum using the plurality of residue discrete logs in a second adder of the processor; establishing, by the processor, a discrete log of the integer from the sum, the sum corresponding to the product of the plurality of residues; determining, by the processor, a (kâˆ’2) bit value for the exponent of the base-3 factor from the discrete log; and representing the integer as the modular factorization comprising the one or more factors, each factor having a value for the exponent.