is_prime for ideals uses factorization, can be VERY slow #33360
Description
The implementation of is_prime() for ideals uses pari idealfactor(). This is a bad idea if the norm of the ideal is hard to factor.
Pari has ismaximalideal(), but it is broken in pari 2.13.3. As a workaround, since a prime ideal has prime power norm, we avoid factorization except on this (easy) case.
Was: VERY slow doctest in sage/rings/number_field/number_field.py
With sage 9.5:
$ time sage -t --long --warn-long 60.0 --random-seed=40834229707572602474454926153679777311 src/sage/rings/number_field/number_field.py
Running doctests with ID 2022-02-16-15-58-06-58d0ee96.
Using --optional=build,pip,sage,sage_spkg,void
Features to be detected: 4ti2,benzene,bliss,buckygen,conway_polynomials,csdp,database_cremona_ellcurve,database_cremona_mini_ellcurve,database_jones_numfield,database_knotinfo,dvipng,graphviz,imagemagick,jupymake,kenzo,latte_int,lrslib,mcqd,meataxe,pandoc,pdf2svg,plantri,pynormaliz,rubiks,sage.combinat,sage.geometry.polyhedron,sage.graphs,sage.plot,sage.rings.number_field,sage.rings.real_double,sage.symbolic,sage_numerical_backends_coin,sagemath_doc_html,sphinx,tdlib
Doctesting 1 file.
sage -t --long --warn-long 60.0 --random-seed=40834229707572602474454926153679777311 src/sage/rings/number_field/number_field.py
**********************************************************************
File "src/sage/rings/number_field/number_field.py", line 2180, in sage.rings.number_field.number_field.NumberField_generic.?
Warning, slow doctest:
while not K.random_element().is_prime(): # long time
pass
Test ran for 1319.62 s
[2265 tests, 1367.95 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 1368.3 seconds
cpu time: 1364.7 seconds
cumulative wall time: 1367.9 seconds
Features detected for doctesting:
real 22m51.641s
user 22m47.153s
sys 0m1.272s
CC: @yyyyx4 @fchapoton
Component: number fields
Author: Gonzalo Tornaría, Lorenz Panny
Reviewer: Lorenz Panny
Issue created by migration from https://trac.sagemath.org/ticket/33360