[QUOTE=xilman;422276]there are persuasive rumours that an unpublished L(1/4) algorithm has been developed.[/QUOTE]

Has anyone else heard about this?

That would indeed be quite the rumor...

This is not about my original question,
but at least I found a nice approach to solve for t in t^2 == N (mod p^e), for any e>=2.
Look at the comment of Gottfried Barthel here: [url]http://mathoverflow.net/questions/52081/is-there-an-efficient-algorithm-for-finding-a-square-root-modulo-a-prime-power[/url]
It works pretty good.

For guys saying "this is just basic number theory": I'm just a stupid computer scientist ;-)