Charles Greathouse on Fri, 07 Nov 2014 06:03:55 +0100

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Cube roots mod prime powers

Is there a way to find cube roots mod prime powers, rather than just primes? Modular roots are handled by gen_Shanks_sqrtn, which is quite specific to primes, but I don't know if there's away to do Hensel lifting other than 'by hand'.

Also, is there a way to get Fp_sqrtn's *zeta from gp? gpow just throws it away, but it would be nice to know what the other roots were. (At the moment I'm using ./gp-sta because I'm on a temporary system rather than my usual setup, so solutions that don't use install() would be best. I'm not even sure if you can access that sort of parameter with install, though.)

Of course all this tends to the goal of being able to take arbitrary roots of arbitrary numbers, which would be useful in many contexts. At the moment I'm running a search which finds the cube root mod the radical of n, rather than mod n. For most numbers this is only a few times slower, but numbers with high exponents cause my program to do many times more work than it should.

Charles Greathouse
Case Western Reserve University