Literatecode

There are numbers as a product of two prime factors and there is a special set of such numbers that can be factorized with a simply method.

The method is very easy to describe: take BASE2 representation of a number; pad it with a leading zero to even length if necessary; bisect it; confuse two halves together by XOR and reverse the result. The final result will be equal to the one of prime factors.

Here are few examples:

1) Let N=21. BASE2 representation is “10101″ and it has the odd length. Pad it to even: “010101″. Divide in half: “010″ and “101″. Confuse both halves together: “111″. Reverse will not affect the result: “111″. This result is a BASE2 representation of 7 and 7 is the prime factor of N. The other factor is 21/7=3.

2) Let N=5207. BASE2 representation, padded to even length, is “01010001010111″. Bisection gives us “0101000″ and “1010111″. Confusion and reversion gives “1111111″, which is 127 in decimal radix. 5207/127=41. Prime factors for 5207 are 127 and 41.

3) Let N=803. BASE2 representation is “1100100011″. Bisection gives us “11001″ and “00011″. Confusion result is “11010″, which in reverse gives us “01011″ (or decimal 11). 803/11=73. Prime factors for 803 are 11 and 73.

As you can see, this method is extremely fast and its performance does not affected by the size of N. However there is the tricky part: this method cannot apply to any product at all. So, you’ll not be able to solve any of the RSA Challenges by using it. Better luck next time.