It's easy to see how the number of operations will grow with requirements of
this size. Does it have to be done in Excel?

Excel VBA should be considered as a support language for manipulating the
associated spreadsheets, not as a programming environment in its own right.
Although it is compiled, it does not compile to object code, merely to an
internal representation, and will always be much slower than a fully-compiled
language.

Under most circumstances the inherent slowness isn't noticeable or at least
isn't too annoying. But you'll soon notice the slowness on compute-intensive
work.