4 ms·
A colleague of mine had invented a technique for factoring composite numbers, that he thought would be quite fast. I thought a little about it and saw that it
by linschn 4y ago
A colleague of mine had invented a technique for factoring composite numbers, that he thought would be quite fast.
I thought a little about it and saw that it would degenerate into sat solving.
I checked taocp and indeed my colleague's idea was in there. Also a faster algorithm was presented in the relevant section. I lended the book to him and we saved around a month of work.
- bombcar 4y agoThis is exactly what TAOCP can be best at - if you know enough about the problem domain to be dangerous, or even to build a solution, you will know enough to read the relevant portion of TAOCP, where it is very likely you will find value.
- lupire 4y agoThere is quite a lot of money waiting for you if you ever figure out how to factor composites quickly. (Any old bum can factor primes quickly.)
- linschn 4y agoWe had a very specific use case, where the input was a known composite, and some properties of the factors were known. Also, while no fast algorithms are known (and may never be depending on if p=np) some are faster than others depending on the properties of your inputs, and choosing the right one can mean saving a lot of time and effort.