Tag Archives: factoring

Factoring I

I remember when I first learnt that testing for primality is in P (as noted in the paper Primes is in P, which explains the AKS algorithm). Some time later, I was talking with a close friend of mine (who has since received his bachelors in Computer Science). He had thought it was hard to believe that it was possible to determine whether a number was prime without factoring that number. That’s pretty cool. The AKS algorithm doesn’t even rely on anything really deep – it’s just a clever application of many (mostly) elementary results. Both of us were well aware of the fact that numbers are hard, as an understatement, to factor. My interest in factoring algorithms has suddenly surged again, so I’m going to look through some factoring algorithms (other than my interesting algorithm, that happens to be terribly slow).


Posted in Expository, Math.NT, Mathematics | Tagged , , , , , | 1 Comment

An interesting (slow) factoring algorithm

After my previous posts (I, II) on perfect partitions of numbers, I continued to play with the relationship between compositions and partitions of different numbers. I ended up stumbling across the following idea: which numbers can be represented as a sum of consecutive positive integers? This seems to be another well-known question, but I haven’t come across it before.


Posted in Math.CO, Math.NT, Math.REC, Mathematics | Tagged , , , , , , | 3 Comments