Dans le cas général de cryptosystèmes basés sur des courbes elliptiques ou hyperelliptiques, la meilleure attaque connue reste une variante parallèle des méthodes de type "paradoxes des anniversaires" (Shanks, Pollard). Dans le cas particulier où la courbe est définie sur un sous-corps du corps considéré, l'utilisation du Frobenius permet d'accélérer cet algorithme, comme l'ont montré Gallant, Lambert, Vanstone, Wiener et Zuccherato. Nous étendons cette attaque au cas où l'on dispose d'un automorphisme sur la courbe, ce qui inclut certaines courbes elliptiques à multiplication complexe, ainsi que la plupart des courbes hyperelliptiques proposées dans la littérature ({\em cf.} Koblitz, Chao, Matsuda, Tsujii, Sakai, Sakurai). Dans cet algorithme, la marche aléatoire est perturbée par la présence de petits cycles parasites. Ce phénomène était déjà signalé et corrigé dans la littérature. Nous analysons plus précisément le nombre de ces petits cycles, et montrons sur quelques exemples que les valeurs moyennes annoncées sont valides.