My naive notion on this is yes, iff the new method is computationally or memory-wise of lower complexity

Computing M_a(n) appears to be at least as hard as factoring n for a=1, so I think you're safe here.