<< NumberTheory`NumberTheoryFunctions`

b = 234  (y^34565647) + 33  (y^3424242);
n = 4500;

Nullstelle calculates roots by trying out:

Nullstelle[a_?PolynomialQ, x_Symbol, n_Integer] := 
      Module[
{i, res = {}, as, 
          PowerModPoly}, 
PowerModPoly[b_, exp_] := 
          PowerMod[b, exp, n]; 
as := 
          a /. Power -> PowerModPoly; 
For[i = 0, 
          i < n, 
If[
            Mod[as /. x -> i, n] == 0,  
            AppendTo[res, 
              i]]; i++]; 
res
]

The isomorphism of Theorem 1 is applied to the polynomial b

Isomorphism[b_?PolynomialQ, x_Symbol, n_Integer] := 
      Module[{listig, app, polytab}, 
listig = 
          FactorInteger[n]; 
app = 
          Table[listig[[i]][[1]]^listig[[i]][[2]], {i, Length[listig]}]; 
polytab = 
          Table[PolynomialMod[b, app[[i]]], {i, 
              Length[app]}]; 
Return[polytab]]

The function Rootfinder calculates roots of b using Nullstelle and Isomorphism

\(Rootfinder[a_?PolynomialQ, x_Symbol, n_Integer] := 
      Module[{primzerlegung, faktoren, c, result, aktion, 
          sol = {}}, 
primzerlegung = 
          FactorInteger[n]; 
faktoren = 
          Table[\(primzerlegung[\([i]\)]\)[\([1]\)]^\(primzerlegung[\([i]\)]\)[\([2]\)], {i, Length[primzerlegung]}]; 
c = 
          Isomorphism[a, x, n]; 
result = 
          Table[Nullstelle[c[\([j]\)], x, faktoren[\([j]\)]], {j, 
              Length[c]}]; 


        aktion = 
          Flatten[Outer[List, Sequence @@ result], 
            Length[result] - 1]; 

For[l = 1, 
          l ≤ Length[aktion], 
sol = 
            Append[sol, 
              ChineseRemainder[aktion[\([l]\)], 
                faktoren]]; \(l++\)]\ ; 
Sort[
          sol]
]\)

As one can see  in this example, Rootfinder yields all roots within 0.2 seconds

Timing[Rootfinder[b, y, n]]

The command Roots refuses to calculate

Roots[b == 0, y, Modulus -> n]

Here is a plot of the runtime of Rootfinder for different n.

zeiten = 
        Table[{n, Timing[Rootfinder[b, y, n]][[1]]}, {n, 100, 5000, 
              7}] /. Second -> 1;
ListPlot[zeiten]

Select[zeiten, #[[2]]
 > 0.62 &]

If n is a prime power, Rootfinder takes longer as in the case, where n is no prime power, because Isomorphism does not yield anything new.

Timing[Rootfinder[b, y, 2048]]

p = 234  (y^34565647) + 33  (y^3424242);
m = 45000;

Timing[Rootfinder[p, y, m]]