I'm always curious when Gauss turns up in the solution to a math problem. Wikipedia has a section on the algorithm here: https://en.wikipedia.org/wiki/Computus#Gauss_algorithm
The same article also explains why it is a hard problem:
"Easter calculations are based on agreements and conventions, not on the actual celestial movements nor on indisputable facts of history."
Sounds a lot like many user requirements I have had to code for.