creation of certain prime finite fields is double dog slow (compared to Magma)

[williamstein]

sage: time FiniteField(10^310+733)  # approx 30 CPU seconds
magma: time FiniteField(10^310+733)  // approx 0.01 CPU seconds

This is a prime field.

---

Apply only attachment: trac_10975.2.patch to the Sage library.

Component: basic arithmetic

Keywords: sd32

Author: William Stein

Reviewer: David Roe, Tom Boothby

Merged: sage-4.7.2.alpha3

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

[williamstein]

comment:1

More output:

d-69-91-173-38:~ wstein$ magma
Magma V2.17-4     Mon Mar 21 2011 14:09:50 on d-69-91-173-38 [Seed = 1755486988]
Type ? for help.  Type <Ctrl>-D to quit.
> time FiniteField(10^310+733)
time> ;
Finite field of size 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000733
Time: 0.040
> time DefiningPolynomial(FiniteField(10^310+733));
$.1 + 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000\
    000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000\
    0000000000000000000000000000000000000000000000000000000000000000000000000000732
Time: 0.040

sage: time FiniteField(10^310+733)
CPU times: user 34.35 s, sys: 0.04 s, total: 34.40 s
Wall time: 34.41 s
Finite Field of size 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000733

[williamstein]

comment:2

Also:

sage: time k = FiniteField(10^310+733)
CPU times: user 34.35 s, sys: 0.04 s, total: 34.40 s
sage: time k = FiniteField(10^310+733)
CPU times: user 17.14 s, sys: 0.02 s, total: 17.16 s
Wall time: 17.17 s

[sagetrac-lmartel]

comment:3

And here is more:

         156 function calls (155 primitive calls) in 33.016 CPU seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        3   24.749    8.250   24.749    8.250 {method 'is_prime' of 'sage.rings.integer.Integer' objects}
        1    8.266    8.266    8.266    8.266 {method 'is_prime_power' of 'sage.rings.integer.Integer' objects}
        1    0.000    0.000    8.258    8.258 finite_field_prime_modn.py:42(__init__)
        3    0.000    0.000   24.749    8.250 arith.py:404(is_prime)
        1    0.000    0.000   33.016   33.016 <string>:1(<module>)
        1    0.000    0.000    0.000    0.000 integer_mod_ring.py:172(__init__)

the difference probably comes from proven prime vs pseudo prime...

(and also:

magma: time IsPrime(10^310 + 733) --> true Time: 28.130

)

[roed314]

comment:5

Attachment: trac_10975.patch.gz

Positive review assuming that the doctests pass...

[jdemeyer]

Reviewer: David Roe

[jdemeyer]

Author: William Stein

[jdemeyer]

comment:7

sage -t  -long -force_lib devel/sage/sage/structure/sage_object.pyx
**********************************************************************
File "/mnt/usb1/scratch/jdemeyer/merger/sage-4.7.alpha3/devel/sage-main/sage/structure/sage_object.pyx", line 1053:
    sage: print "x"; sage.structure.sage_object.unpickle_all()  # long time (4s on sage.math, 2011)
Expected:
    x...
    Successfully unpickled ... objects.
    Failed to unpickle 0 objects.
Got:
    x
     * unpickle failure: load('/scratch/jdemeyer/merger/sage-4.7.alpha3/home/.sage/temp/sage.math.washington.edu/27992/dir_2/pickle_jar/_class__sage_coding_linear_code_LinearCode__.sobj')
[...]
    Failed:
    _class__sage_coding_linear_code_LinearCode__.sobj
    _class__sage_crypto_mq_sbox_SBox__.sobj
    _class__sage_crypto_mq_sr_SR_gf2__.sobj
    _class__sage_crypto_stream_LFSRCryptosystem__.sobj
    _class__sage_groups_matrix_gps_general_linear_GeneralLinearGroup_finite_field__.sobj
    _class__sage_groups_matrix_gps_matrix_group_element_MatrixGroupElement__.sobj
    _class__sage_homology_chain_complex_ChainComplex__.sobj
    _class__sage_modular_abvar_homology_Homology_over_base__.sobj
    _class__sage_modular_modform_ambient_R_ModularFormsAmbient_R__.sobj
    _class__sage_modular_ssmod_ssmod_SupersingularModule__.sobj
    _class__sage_rings_finite_field_ext_pari_FiniteField_ext_pari__.sobj
    _class__sage_rings_finite_field_morphism_FiniteFieldHomset__.sobj
    _class__sage_rings_finite_field_prime_modn_FiniteField_prime_modn__.sobj
    _class__sage_rings_polynomial_polynomial_ring_PolynomialRing_dense_mod_p__.sobj
    _type__sage_matrix_matrix_modn_sparse_Matrix_modn_sparse__.sobj
    _type__sage_rings_finite_field_givaro_FiniteField_givaroElement__.sobj
    _type__sage_rings_finite_field_givaro_FiniteField_givaro__.sobj
    _type__sage_rings_finite_field_ntl_gf2e_FiniteField_ntl_gf2eElement__.sobj
    _type__sage_rings_finite_field_ntl_gf2e_FiniteField_ntl_gf2e__.sobj
    _type__sage_rings_morphism_RingHomomorphism_im_gens__.sobj
    _type__sage_rings_polynomial_polynomial_gf2x_Polynomial_GF2X__.sobj
    Successfully unpickled 565 objects.
    Failed to unpickle 21 objects.
**********************************************************************