I found a need for allsqrtmod, and wrote (perl code for) the functions documented below. Would you be interested in incorporating some or all of these in MPU? If you would, I'd be happy to add some tests (and maybe XS variants) and put together a PR.
allsqrtmod is implemented in terms of allsqrtmodfact which in turn uses allsqrtmodpk; the latter two could also be private functions.
=head2 allsqrtmod( $a, $n )
Given integer C<a> and positive integer C<n>, return a list of the square
roots C<x> of C<a mod n> having C<< 0 <= x < n >>. If no square root
exists, an empty list is returned.
=head2 allsqrtmodfact( $a, $n, $f )
Given integer C<a> and positive integer C<n>, and the factorization C<f>
of C<n> as returned by L<factor_exp>, return a list of the square roots C<x>
of C<a mod n> having C<< 0 <= x < n >>. If no square root exists, an empty
list is returned.
=head2 allsqrtmodpk( $a, $p, $k )
Given integer C<a>, prime C<p> and positive integer C<k>, return a list of
the square roots C<x> of C<a mod p^k> having C<< 0 <= x < p^k >>. If no
square root exists, an empty list is returned.
=cut
I found a need for
allsqrtmod, and wrote (perl code for) the functions documented below. Would you be interested in incorporating some or all of these in MPU? If you would, I'd be happy to add some tests (and maybe XS variants) and put together a PR.allsqrtmodis implemented in terms ofallsqrtmodfactwhich in turn usesallsqrtmodpk; the latter two could also be private functions.