Square roots mod a prime power
287 views
Skip to first unread message
Bill Hart
Apr 25, 2012, 5:45:28 PM4/25/12
to flint-devel
Hi all,
I just added a new function to the ulong_extras module for computing
square roots of a residue c modulo p^exp for a prime p. The function
computes all of the square roots and returns them in an array, even
when p = 2 or p | c. It also returns the number of roots, which is
zero if c is a nonresidue modulo p^exp.
I also plan to add a function which will compute all the square roots
of a residue c modulo an arbitrary integer n given the factorisation
of n. Actually, making this efficient is going to be a bit of work.
I may also add fmpz versions of these functions, though there we'd
have to rely on the probable prime test in mpir for now since we don't
have proper primality testing for large integers.
Bill.
I just added a new function to the ulong_extras module for computing
square roots of a residue c modulo p^exp for a prime p. The function
computes all of the square roots and returns them in an array, even
when p = 2 or p | c. It also returns the number of roots, which is
zero if c is a nonresidue modulo p^exp.
I also plan to add a function which will compute all the square roots
of a residue c modulo an arbitrary integer n given the factorisation
of n. Actually, making this efficient is going to be a bit of work.
I may also add fmpz versions of these functions, though there we'd
have to rely on the probable prime test in mpir for now since we don't
have proper primality testing for large integers.
Bill.
Fredrik Johansson
Apr 26, 2012, 4:41:50 AM4/26/12
to flint...@googlegroups.com
BTW, selmer (and the main flint git repository) still isn't accessible
to the world (unless you know the magic number).
Fredrik
Bill Hart
Apr 26, 2012, 5:34:47 AM4/26/12
to flint...@googlegroups.com
On 26 April 2012 09:41, Fredrik Johansson <fredrik....@gmail.com> wrote:
> On Wed, Apr 25, 2012 at 23:45, Bill Hart <goodwi...@googlemail.com> wrote:
>> Hi all,
>>
>> I just added a new function to the ulong_extras module for computing
>> square roots of a residue c modulo p^exp for a prime p. The function
>> computes all of the square roots and returns them in an array, even
>> when p = 2 or p | c. It also returns the number of roots, which is
>> zero if c is a nonresidue modulo p^exp.
>>
>> I also plan to add a function which will compute all the square roots
>> of a residue c modulo an arbitrary integer n given the factorisation
>> of n. Actually, making this efficient is going to be a bit of work.
>>
>> I may also add fmpz versions of these functions, though there we'd
>> have to rely on the probable prime test in mpir for now since we don't
>> have proper primality testing for large integers.
>
> Great news! I'm curious about how the performance compares to other software.
It's a bit hard to measure given that the number of roots varies
> On Wed, Apr 25, 2012 at 23:45, Bill Hart <goodwi...@googlemail.com> wrote:
>> Hi all,
>>
>> I just added a new function to the ulong_extras module for computing
>> square roots of a residue c modulo p^exp for a prime p. The function
>> computes all of the square roots and returns them in an array, even
>> when p = 2 or p | c. It also returns the number of roots, which is
>> zero if c is a nonresidue modulo p^exp.
>>
>> I also plan to add a function which will compute all the square roots
>> of a residue c modulo an arbitrary integer n given the factorisation
>> of n. Actually, making this efficient is going to be a bit of work.
>>
>> I may also add fmpz versions of these functions, though there we'd
>> have to rely on the probable prime test in mpir for now since we don't
>> have proper primality testing for large integers.
>
> Great news! I'm curious about how the performance compares to other software.
wildly. But it shouldn't be hopeless. It's really just a big case
bash, though there were a couple of bits that I put some effort into
making fast.
Having said that, I don't really know of any other software which does
this computation.
>
> BTW, selmer (and the main flint git repository) still isn't accessible
> to the world (unless you know the magic number).
Instead of selmer.warwick.ac.uk just use 137.205.37.203 for now.
Bill.
Bill Hart
Apr 26, 2012, 12:09:35 PM4/26/12
to flint...@googlegroups.com
I've now added the function which computes all the square roots of a
residue modulo an arbitrary integer m given its factorisation. I think
this has been done relatively efficiently.
Bill.
residue modulo an arbitrary integer m given its factorisation. I think
this has been done relatively efficiently.
Bill.
Reply all
Reply to author
Forward
0 new messages