Finite field roots

[4c814734-baf9-4879-ba94-57f68b74985f]

Implemented a "new" algorithm for nth root in finite fields/rings (adapted from the paper "On taking roots in finite fields" by Adelman et al. 1977). My tests show similar or slightly better performance at small prime moduli and significantly better performance in many cases at large prime moduli. This performance increase is mainly due to not relying on K.multiplicative_generator() which needs to factor (p-1) and leads to erratic performance.

Component: finite rings

Author: Hauke Neitzel

Branch/Commit: u/gh-theHawke/finite_field_roots @ 5845925

Issue created by migration from https://trac.sagemath.org/ticket/28585

[4c814734-baf9-4879-ba94-57f68b74985f]

Branch: u/gh-theHawke/finite_field_roots

[4c814734-baf9-4879-ba94-57f68b74985f]

Commit: 533fd5d

[4c814734-baf9-4879-ba94-57f68b74985f]

Description changed:

--- 
+++ 
@@ -1 +1 @@
-
+Implemented a "new" algorithm for nth root in finite fields/rings (adapted from the paper "On taking roots in finite fields" by Adelman et al. 1977). My tests show similar or slightly better performance at small prime moduli and significantly better performance in many cases at large prime moduli. This performance increase is mainly due to not relying on K.multiplicative_generator() which needs to factor (p-1) and leads to erratic performance.

[4c814734-baf9-4879-ba94-57f68b74985f]

Author: Hauke Neitzel

[pjbruin]

comment:4

The branch points to 9.0.beta0; did you perhaps forget to push your branch?

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 533fd5d to 359dd4b

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

a19dc0b	first implementation
359dd4b	tested: working

[4c814734-baf9-4879-ba94-57f68b74985f]

comment:6

Replying to @pjbruin:

The branch points to 9.0.beta0; did you perhaps forget to push your branch?

Apologies, I didn't realize git trac create forks from develop instead of the current branch.

EDIT: Also apologies that it is not compiling, "it was working fine yesterday" and I have no idea what Cython is trying to tell me.

EDIT2: it was unicode quotes in the citation of the paper, ~600 lines down

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 359dd4b to a10ba65

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

a10ba65

it compiles again

[videlec]

comment:8

Hi,

Please post your benchmarks instead of writing My tests show similar or slightly better performance at small prime moduli and significantly better performance in many cases at large prime moduli.

[videlec]

comment:9

The option algorithm="AMM" should be documented in the INPUT section somewhere.

[videlec]

comment:10

There musts be tests associated to your new algorithm in the section EXAMPLES: and possibly TESTS:.

[videlec]

comment:11

It is often better to avoid coercion (ie comparison, operation, etc of elements with distinct parents). For example

• g**((q-1)/r) == 1 -> (g**((q-1)/r)).is_one()
• A*G**lam != 1 -> not (A*G**lam).is_one()
• J = 0 -> J = K.zero()
• J == 0 -> J.is_zero()
• g += 1 -> g += one where one would have been initialized to K.one()

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from a10ba65 to 495b65b

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

495b65b

suggested changes

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

18d1b1a

expanded doctests

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 495b65b to 18d1b1a

[4c814734-baf9-4879-ba94-57f68b74985f]

comment:15

Replying to @videlec:

It is often better to avoid coercion (ie comparison, operation, etc of elements with distinct parents). For example

• g**((q-1)/r) == 1 -> (g**((q-1)/r)).is_one()
• A*G**lam != 1 -> not (A*G**lam).is_one()
• J = 0 -> J = K.zero()
• J == 0 -> J.is_zero()
• g += 1 -> g += one where one would have been initialized to K.one()

Thank you for the feedback!

I have now included the algorithm in the INPUT, EXAMPLES and TEST sections and I have attached my small benchmark script to this ticket.

I have also integrated your suggestions with regard to coercion, however since J is an exponent like k and v, I believe it should always be an integer and shouldn't be an element of K.

Lastly, I have expanded the algorithm to include the self.is_one() case.

[4c814734-baf9-4879-ba94-57f68b74985f]

Attachment: root_test.sage.gz

small benchmark comparing the two algorithms

[4c814734-baf9-4879-ba94-57f68b74985f]

sample output of the benchmark

[4c814734-baf9-4879-ba94-57f68b74985f]

comment:16

Attachment: root_test_output.txt

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

9d6a86e

fixed failing FinitePolyExtElement test

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 18d1b1a to 9d6a86e

[videlec]

comment:18

You introduced this doctest

sage: a._nth_root_common(4, True, "AMM", cunningham = True) # optional - cunningham

with no output!

[videlec]

comment:19

It would be better to not duplicate

            if all:
                nthroot = g**q1overn
                L = [self]
                for i in range(1,n):
                    self *= nthroot
                    L.append(self)
                return L

(you could move that out of the if/else)

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 9d6a86e to 3d4fcb6

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

3d4fcb6

moved common code out of the algorithms and fixed doctest

[videlec]

comment:21

There are trailing whitespaces in several place (ie space sign before line break). Please remove them. They appear in red if you do git diff YOUR_BRANCH MAIN_BRANCH.

[videlec]

comment:22

This is ugly

if y.nth_root(r)**r != y: raise RuntimeError
if y.nth_root(r, algorithm='AMM')**r != y: raise RuntimeError
if (y^41).nth_root(41*r)**(41*r) != y^41: raise RuntimeError
if (y^41).nth_root(41*r, algorithm='AMM')**(41*r) != y^41: raise RuntimeError
if (y^307).nth_root(307*r)**(307*r) != y^307: raise RuntimeError
if (y^307).nth_root(307*r, algorithm='AMM')**(307*r) != y^307: raise RuntimeError

What about

for s, algo in product([1,41,307], ['Johnston', 'AMM']):
    assert (y^s).nth_root(s*r, algorithm=algo)**(s*r) == y^s

(you need a from itertools import product)

[videlec]

comment:23

More interestingly, if AMM is faster for larger moduli why not make it the default in these cases? Would this dispatch be reasonable:

• if moduli is small just use Johnston
• if moduli is large
  • if a multiplicative generator is already available use Johnston
  • if not use AMM

[4c814734-baf9-4879-ba94-57f68b74985f]

comment:24

Replying to @videlec:

More interestingly, if AMM is faster for larger moduli why not make it the default in these cases? Would this dispatch be reasonable:

• if moduli is small just use Johnston
• if moduli is large
  • if a multiplicative generator is already available use Johnston
  • if not use AMM

Since AMM is actually slightly faster even at small moduli, it could also be made the default in general unless the multiplicative generator is available.

That said, I am not sure how to check whether the generator is available. There does seem to be some caching but I can't see a way to explicitly check it.

[videlec]

comment:25

There is some caching

sage: R = Zmod(next_prime(2**10))
sage: r = R.multiplicative_generator()
sage: R.multiplicative_generator() is r
True

or finite fields

sage: R = GF(next_prime(2**10)**2)
sage: r = R.multiplicative_generator()
sage: R.multiplicative_generator() is r
True

The cache is implemented via the decorator @cached_method. To access the cache here is what could be done

gen = R.multiplictative_generator.cache
if gen is not None:
    # gen is the multiplicative generator
    ...
else:
    # do not trigger multiplicative generator computation
    ...

You should also check timings over very small moduli, e.g things like GF(2^5) or GF(3^10).

[4c814734-baf9-4879-ba94-57f68b74985f]

Attachment: root_test.2.sage.gz

Benchmark script for comparing the two algortihms in various situations

[4c814734-baf9-4879-ba94-57f68b74985f]

sample output of the benchmark (new version)

[4c814734-baf9-4879-ba94-57f68b74985f]

comment:26

Attachment: root_test_output.2.txt

I added a couple new tests to the benchmarks. Unless you want to set a threshold at something like 11 I don't think it is worth using Johnston for small values.

Whether a particular finite field is faster with Johnston or AMM seems to be fairly randomly distributed with AMM's advantage getting slightly larger as the fields order increases (goes up to 85% AMM better for orders below 10000).

I would suggest making the default simply depend on the availability of a cached multiplicative generator.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

5845925

Made AMM the default algorithm unless a multiplicative generator is available cached

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 3d4fcb6 to 5845925

[embray]

comment:28

Ticket retargeted after milestone closed

[mkoeppe]

comment:29

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

[videlec]

comment:31

The reference would better go in the dedicated file $SAGE_ROOT/src/doc/en/reference/references/index.rst. You can make citations using ReST citations.

[mkoeppe]

comment:32

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

[mkoeppe]

comment:33

Setting a new milestone for this ticket based on a cursory review.

[mezzarobba]

comment:34

no longer applies