Opened 9 years ago

Last modified 8 years ago

#10975 closed enhancement

creation of certain prime finite fields is double dog slow (compared to Magma) — at Version 11

Reported by: was Owned by: AlexGhitza
Priority: critical Milestone: sage-4.7.2
Component: basic arithmetic Keywords: sd32
Cc: Merged in:
Authors: William Stein Reviewers: David Roe, Tom Boothby
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by leif)

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 trac_10975.2.patch to the Sage library.

Change History (13)

comment:1 Changed 9 years ago by was

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

comment:2 Changed 9 years ago by was

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

comment:3 Changed 9 years ago by lmartel

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

)

comment:4 Changed 9 years ago by was

  • Status changed from new to needs_review

Changed 9 years ago by was

comment:5 Changed 9 years ago by roed

  • Status changed from needs_review to positive_review

Positive review assuming that the doctests pass...

comment:6 Changed 9 years ago by jdemeyer

  • Authors set to William Stein
  • Reviewers set to David Roe

comment:7 Changed 9 years ago by jdemeyer

  • Status changed from positive_review to needs_work
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.
**********************************************************************

Changed 8 years ago by was

fix the issue with pickling that was pointed out.

comment:8 Changed 8 years ago by was

  • Status changed from needs_work to needs_review

comment:9 Changed 8 years ago by boothby

  • Status changed from needs_review to positive_review

New patch fixes the pickling issue in a sensible way.

comment:10 Changed 8 years ago by was

  • Keywords sd32 added

comment:11 Changed 8 years ago by leif

  • Description modified (diff)
  • Reviewers changed from David Roe to David Roe, Tom Boothby
Note: See TracTickets for help on using tickets.