Your question was migrated to stackexchange Mathematica. Please see the Mathematica implementation invphi.nb by Maxim Rytin, available at http://library.wolfram.com/infocenter/MathSource/696/ . This code easily handles integers n in your range.
See also Chapter 3 in A Course in Computational Number Theory by Bressoud and Wagon.