Caching of factorizations

[cwgreene]

Problem Description

Currently, to the best of my knowledge, there is no way to tell Sage the factorization of a number such that future calls to the toplevel factor method. So even when the factorization is known, there is no way to let the sage system know, which means that, for example, attempting to compute the multiplicative order of a ring will spend an indefinite amount of time in the factor method.

Letting the method factor know the factorizations is necessary as a number of algorithms defer to it (discrete log for example).

An alternative approach would be to refactor uses of factor in various algorithms to defer to the parent ring. The ring could then be subclassed to allow for a custom factor method to be provided. However, this would require a fair amount of work as a number of places in the code call factor directly on a derived integer (and thus no longer a ring element) obtained from the ring.

Proposed Solution

Create an associative array in sage.arith.misc FACTORS.

Provide a new top toplevel method in sage.arith.misc assert_factorization(n, F) which checks that F is a valid factorization of n and inters it into the FACTORS. When factor is invoked, the FACTORS cache is consulted, and if present, returns the previously validated factorization.

Alternatives Considered

An alternative idea would be to subclass the ring in question. Thus instead we would do something like

class IntegerRingWithFactorization(sage.rings.finite_rings.integer_mod_ring.IntegerModRing_generic_with_category):
   def __init__(self, n, F):
          self.F = F
          super(self)

   def factor(self, n):
        return self.F

Unfortunately, at the moment, factor is not a method on the ring, and many relevant methods, order, multiplicative_order return raw integers. sage.arith.misc's factor method does defer to the element, so if all ways in which these parameters were accessed were tracked down and updated, we could possibly create a IntegerWithFactorization object as the return object. However, this would probably not interact well with other code which is oblivious to the original ring or casts the object explicitly to a bare integer.

I believe that providing the factorization directly to a cache used by factor would be the simplest solution.

Additional Information

There has been an idea for special form database in the past:

https://github.com/sagemath/sage/issues/191

However, it seems to have been resolved by the addition of specialized support for cunningham tables, which is not really what this ticket is requesting.

Is there an existing issue for this?

• [X] I have searched the existing issues for a bug report that matches the one I want to file, without success.

[maxale]

Somewhat related to #32900

[AZ-0]

How about taking a page from the set_order method of elliptic curves and their points? It serves a very similar purpose. We could implement a set_factors(facs, *, check=True) that sets a _factors attribute. Whenever factor is called, it can check whether this attribute is set and avoid calling expensive factorisation routines.