Problem Description

Currently BQFClassGroupQuotientMorphism is really quite slow when the index of the smaller order in the second is very large. From what I gather the root computation here is the bottleneck.

Example:

from sage.quadratic_forms.bqf_class_group import BQFClassGroupQuotientMorphism
nbits = 256
while (p := random_prime(2**nbits)) % 4 != 3:
    pass
D = -p
q = random_prime(2**nbits)
Cl = BQFClassGroup(D)
Clq = BQFClassGroup(D*q**2)
f = Clq.random_element()
phi = BQFClassGroupQuotientMorphism(Clq, Cl)
print(phi(f)) # freezes

Proposed Solution

My suggestion is to instead use the map from Theorem 7.9 from Buell's "Binary Quadratic Forms". There it is computed by computing the composition of the input form with the identity form in the larger order. It is not explicitly stated that this will be the same projection so I would appreciate if someone with more experiences in this area can weigh in on if there are any edge-cases or otherwise mismatching behavior. From my limited testing it seems to match the wanted behavior.

CC @yyyyx4 for being the original author of the class.

Using the above values we can instead compute the map like this (which is basically instant):

print(Cl(BinaryQF(pari(f.form()) * pari(Cl.zero().form()))))

Alternatives Considered

None

Additional Information

No response

Is there an existing issue for this?

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