I had the same question when i was undergrad and it led me to do masters! It works because of symmetry, if calculations are symmetric you don't need to perform them twice which results in "fast computation". DFT matrix can be decomposed into multiple matrices in such a way that most of its elements are zeros and this representation is what is called FFT. This can be done because DFT structure has certain symmetries which are exploited to decompose its matrix it is also the reason why any arbitrary matrix cannot be made fast. Why DFT has this structure comes from the theory of linear shift invariant systems.

search for "pushchel" and "symmetry" if you want to go deeper and to understand what is meant by symmetry in mathematical terms.