Random testing has revealed a problem in test_karatsuba_multiplication

[vbraun]

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.

Did you read the documentation and troubleshoot guide?

• I have read the documentation and troubleshoot guide

Environment

- **OS**: Ubuntu 18.04 32 bit
- **Sage Version**: 10.1.beta1

Steps To Reproduce

Random fail when running the tests, just saw it for the first time on a build bot:

**********************************************************************
File "src/sage/rings/tests.py", line 449, in sage.rings.tests.?
Failed example:
    test_karatsuba_multiplication(QQbar, 3, 3, numtests=2)    # long time     # optional - sage.rings.number_field
Expected nothing
Got:
    Random testing has revealed a problem in test_karatsuba_multiplication
    Please report this bug!  You may be the first
    person in the world to have seen this problem.
    Please include this random seed in your bug report:
    Random seed: 164480309984640964737929113640888706047
    ValueError('Multiplication failed')
**********************************************************************
1 item had failures:
   1 of  13 in sage.rings.tests.?
    [62 tests, 1 failure, 25.59 s]
----------------------------------------------------------------------
sage -t --long --random-seed=0 src/sage/rings/tests.py  # 1 doctest failed
----------------------------------------------------------------------

Expected Behavior

Doctest should not fail

Actual Behavior

Doctest fails (randomly, seed is provided above)

Additional Information

probably due to #35443

[vbraun]

@tornaria FYI

[tobiasdiez]

More info on how to reproduce this (or a very closely related error:: #36961

[GiacomoPope]

This has also cropped up here: #37455

Each time I saw the error in the CI I could not reproduce it locally.

[mezzarobba]

Also here: #37193 (comment)

[GiacomoPope]

Another example of this:

#37441 (comment)

sage: from sage.rings.tests import test_karatsuba_multiplication ## line 429 ##
sage: test_karatsuba_multiplication(ZZ, 6, 5, verbose=True, seed=42) ## line 430 ##
test_karatsuba_multiplication: ring=Univariate Polynomial Ring in x over Integer Ring, threshold=2
  (x^6 + 4*x^5 + 4*x^4 - 3*x^3 - x^2 - x)*(2*x^4 + 3*x^3 - 20*x^2 - 2*x + 1)
  (4*x^5 + 16*x^2 + x - 41)*(x^2 + x - 1)
  (8*x^2 + 2*x + 1)*(3)
  (-4*x - 1)*(-8*x^2 - x)
  (-x^6 - x^3 - x^2 + x + 1)*(2*x^3 - x + 3)
  (-x^2 + x + 1)*(x^4 + x^3 - x^2 - x + 76)
  (4*x^3 + x^2 + 6)*(-x^2 - 5*x)
  (x + 4)*(-x + 5)
  (-2*x)*(3*x^2 - x)
  (x^6 + 21*x^5 + x^4 + 4*x^3 - x^2)*(14*x^4 + x^3 + 2*x^2 - 12*x)
sage: rings = [QQ] ## line 445 ##
sage: rings += [ZZ[I], ZZ[I, sqrt(2)]]                                          # needs sage.rings.number_field sage.symbolic ## line 446 ##
sage: rings += [GF(49, 'a')]                                                    # needs sage.rings.finite_rings ## line 447 ##
sage: rings += [MatrixSpace(GF(17), 3)]                                         # needs sage.modules ## line 448 ##
sage: for C in rings:                                                           # needs sage.modules
    test_karatsuba_multiplication(C, 10, 10) ## line 449 ##
sage: test_karatsuba_multiplication(QQbar, 3, 3, numtests=2)    # long time, needs sage.rings.number_field ## line 454 ##

The output following #37561 makes this error more verbose.

[mezzarobba]

Another example of this:

#37441 (comment)

This one isn't a “multiplication failed” but a plain crash—with no new info from #37561, presumably due to output buffering.

[fchapoton]

Here is more data

Multiplication failed for elements defined by
R1.<y> = QQ[]
R2.<x> = QQbar[]
8*QQbar.polynomial_root(AA.common_polynomial(y^2 + 1), CIF(RIF(RR(0)), RIF(-RR(1))))*x^3 + 1/5*QQbar.polynomial_root(AA.common_polynomial(y^2 - y + 5), CIF(RIF(RR(0.49999999999999994), RR(0.50000000000000011)), RIF(RR(2.1794494717703365), RR(2.179449471770337))))*x^2 + QQbar(1/2*AA.polynomial_root(AA.common_polynomial(y^2 - 2), RIF(RR(1.4142135623730949), RR(1.4142135623730951))))*x + QQbar(1/4*AA.polynomial_root(AA.common_polynomial(y^2 - y - 4), RIF(RR(2.5615528128088298), RR(2.5615528128088303))))
and
R1.<x> = QQbar[]
R2.<y> = QQ[]
2/3*x^3 + QQbar(AA.polynomial_root(AA.common_polynomial(y^2 - y - 8988), RIF(-RR(94.30638164174394), -RR(94.306381641743926))))*x^2 + (QQbar.polynomial_root(AA.common_polynomial(y^2 + 1), CIF(RIF(RR(0)), RIF(RR(1)))) - 1)*x + QQbar(1/15*AA.polynomial_root(AA.common_polynomial(y^2 - 106), RIF(-RR(10.295630140987001), -RR(10.295630140986999))) + 11/15)

[user202729]

A (slightly different?) error

2025-02-01T12:28:25.8118182Z sage -t --long --warn-long 30.0 --random-seed=286735480429121101562228604801325644303 src/sage/rings/tests.py
2025-02-01T12:28:25.8119196Z **********************************************************************
2025-02-01T12:28:25.8131737Z ##[error]Failed example:: Got: Random testing has revealed a problem in test_karatsuba_multiplication
Please report this bug!  You may be the first
person in the world to have seen this problem.
Please include this random seed in your bug report:
Random seed: 108989663366345573243852144936891050366
NTLError('FFT prime index too large')
                                                                                                                                                               
2025-02-01T12:28:25.8135159Z     test_karatsuba_multiplication(QQbar, 3, 3, numtests=2)    # long time, needs sage.rings.number_field
2025-02-01T12:28:25.8135895Z Expected nothing
2025-02-01T12:28:25.8136213Z Got:
2025-02-01T12:28:25.8136638Z     Random testing has revealed a problem in test_karatsuba_multiplication
2025-02-01T12:28:25.8137291Z     Please report this bug!  You may be the first
2025-02-01T12:28:25.8137783Z     person in the world to have seen this problem.
2025-02-01T12:28:25.8138288Z     Please include this random seed in your bug report:
2025-02-01T12:28:25.8142063Z     Random seed: 108989663366345573243852144936891050366
2025-02-01T12:28:25.8142576Z     NTLError('FFT prime index too large')
2025-02-01T12:28:44.7428637Z **********************************************************************
2025-02-01T12:28:44.7429725Z 1 item had failures:
2025-02-01T12:28:44.7430350Z    1 of  13 in sage.rings.tests.?
2025-02-01T12:28:44.7521085Z     [62 tests, 1 failure, 823.68s wall]

https://github.com/sagemath/sage/actions/runs/13088275053/job/36522122850