[boothby]

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