Thursday, December 4, 2014

Factoring integers using the complex plane

Please see my wiki for a comprehensible version of this post.

I was pretty pleased that I factored a recent Composite of the day entirely in the complex plane.
The number was 9509, which I noticed immediately is 97²+10². Since I know Fermat's little theorem, and I know that the Composite of the day is composite, I knew there should be another way to write it as the sum of two squares. A little bit of counting (100+193+191) showed that it is also equal to 95²+22².

For some reason, I know that if I use those two summations to write complex integers with modulus 9509, their greatest common factor will also divide 9509.
So I said, (97+10i) - (95+22i) = 2-12i. The modulus of that is 2²+12²=148. The factors of 2 must be irrelevant (since the Cotd is odd), so 37 should be the number we're looking for.

Similarly, (97-10i) - (95+22i) = 2-32i. The modulus of that is 1048. Again, discarding factors of 2, we're left with the prime 257.

And the number is now factored, by finding complex integers with the right modulus and manuipulating them in the complex plane.

Pretty wild, huh?


  1. Man, for years I thought this was called the little theorem, but apparently that's something else. The one I meant has no cool name:

  2. Also, today's composite of the day is the difference between two fourth powers. That must be very rare.