1. 18 Jul, 2022 1 commit
  2. 13 Jul, 2022 1 commit
    • Andreas Enge's avatar
      Replace delegation of Cornacchia's algorithm to PARI by a new function. · e6ef0077
      Andreas Enge authored
      The new function should use some fewer multiplications, but supposedly all
      time is spent in halfgcd inside PARI anyway. For 10^3000+1027 on 640 cores,
      both implementations take 24s.
      * lib/cm-impl.h (cm_nt_mpz_cornacchia): Remove function declaration.
      * lib/nt.c (cm_nt_mpz_cornacchia): Remove function.
      * lib/pari.c (cm_pari_cornacchia): Replace the complete delegation to the
        cornacchia2_sqrt function of PARI to an implementation that uses only
        the function halfgcd from PARI.
  3. 11 Jul, 2022 4 commits
    • Andreas Enge's avatar
      Enable reading and writing of stage 2 partial results in any order. · f84fdf41
      Andreas Enge authored
      Change suggested by Greg Childers <gchilders@fullerton.edu>.
      * lib/cm-impl.h (cm_write_ecpp_cert2_line): Add parameter no in declaration.
      * lib/file.c (read_ecpp_cert2_line): Change type of return value and read
        number of curve.
        (cm_write_ecpp_cert2_line): Add parameter no and write it to file.
        (cm_file_read_ecpp_cert2): Handle line number. Swap pointers instead of
        copying mpz.
      * lib/ecpp.c (ecpp2): Adapt function calls. Change the logic to submit
        precisely the missing jobs, and write all received results.
      * NEWS: Document the incompatibility for the .cert2 files.
    • Andreas Enge's avatar
      Implement the command line option -2. · b70721e4
      Andreas Enge authored
      * lib/ecpp.c (ecpp1): Add parameter onlyread.
        (cm_ecpp): Adapt function call and implement the case that phases == 2.
    • Andreas Enge's avatar
      Implement the command line option -1. · 3f915b89
      Andreas Enge authored
      * lib/ecpp.c (cm_ecpp): Implement the case that phases == 1.
    • Andreas Enge's avatar
      Prepare the use of the -1 and -2 options for ECPP. · 4d107371
      Andreas Enge authored
      * lib/cm.h (cm_ecpp), lib/ecpp.c (cm_ecpp),
        src/params.c (evaluate_parameters): Add phases parameter.
      * src/params.c (print_phase_options): New function.
        (print_help): Call new function.
        (evaluate_parameters): Add phases parameter and code to handle it. Make
        sure the '-n' option is given.
      * src/ecpp.c (main), src/ecpp-mpi.c (main), tests/tecpp.c (test_ecpp):
        Adapt function calls.
      * doc/cm.texi, NEWS: Document planned changes.
  4. 08 Jul, 2022 3 commits
    • Andreas Enge's avatar
      Split the numbers to be trial divided between the split communicators. · 57e1eb80
      Andreas Enge authored
      This gains a factor of about 8 in the trial division step, which should
      more than offset the about 3 bits per step lost in the previous commit.
      * lib/cm-impl.h (cm_mpi_submit_tree_gcd, cm_mpi_get_tree_gcd): Rename
        parameter m to n and no_m to no_n.
      * lib/mpi.c (cm_mpi_submit_tree_gcd): Rename parameters and send data
        to all split communicators.
        (cm_mpi_get_tree_gcd): Rename parameters and combine results from all
        split communicators.
        (mpi_worker): Include the workers of all split communicators.
    • Andreas Enge's avatar
      Use only the first split communicator for tree gcds. · 142b02d5
      Andreas Enge authored
      Together with its size being about 8 times smaller, this implies that
      the effective B is 8 times smaller, so we expect to gain 3 bits less
      in each iteration.
      * lib/mpi.c (mpi_send_mpz, mpi_recv_mpz, mpi_bcast_send_mpz,
        mpi_bcast_recv_mpz): Add a communicator parameter.
        (cm_mpi_broadcast_N, cm_mpi_broadcast_sqrt, cm_mpi_get_tonelli,
        cm_mpi_submit_ecpp_one_step2, cm_mpi_get_ecpp_one_step2,
        cm_mpi_get_curve_cardinalities, cm_mpi_submit_is_prime): Adapt function
        (cm_mpi_submit_tree_gcd, cm_mpi_get_tree_gcd, mpi_worker): Adapt
        function calls and limit participation in the gcd computations to the
        first split communicator.
    • Andreas Enge's avatar
      Create split communicators for later use in the tree gcd phase. · a8258430
      Andreas Enge authored
      * lib/cm-impl.h (cm_mpi_compute_B): Declare new function.
      * lib/ecpp.c (ecpp1): Use new function.
      * lib/mpi.c (split_comm): New global variable.
        (mpi_compute_split_m, cm_mpi_compute_B, mpi_communicator_split,
        mpi_communicator_free): New functions.
        (mpi_server_init, mpi_worker): Use new functions to create split
  5. 07 Jul, 2022 1 commit
  6. 04 Jul, 2022 4 commits
    • Andreas Enge's avatar
      Print fewer file opening debug messages in ECPP. · a9a1c311
      Andreas Enge authored
      * lib/file.c (cm_file_write_h, cm_file_read_h, cm_file_write_primorial,
        cm_file_read_primorial): Use fopen and fclose instead of cm_file_open_*
        and cm_file_close.
    • Andreas Enge's avatar
      Enable reading and writing of primorials. · 863392e7
      Andreas Enge authored
      * lib/cm.h (cm_ecpp): Remove qualifier "const" from tmpdir, since it
        collides with MPI_Bcast.
      * lib/cm-impl.h (cm_file_write_primorial, cm_file_read_primorial): Declare
        new functions.
        (cm_mpi_submit_primorial): Add parameter tmpdir.
      * lib/ecpp.c (ecpp1, cm_ecpp): Remove qualifier const from parameter tmpdir.
      * lib/mpi.c (cm_mpi_submit_primorial): Add parameter tmpdir and broadcast
        it to the workers.
        (mpi_worker): Handle broadcast tmpdir and read and write primorial files.
      * lib/file.c (cm_file_write_primorial, cm_file_read_primorial): New
        (write_stat, read_stat): Add missing keyword "static".
      * NEWS: Document the change.
    • Andreas Enge's avatar
      Enable reading and writing of class numbers. · cae97347
      Andreas Enge authored
      * lib/cm-impl.h (cm_file_write_h, cm_file_read_h): Declare new functions.
      * lib/file.c (cm_file_write_h, cm_file_read_h): New functions.
        (cm_file_open_write, cm_file_open_read, cm_file_open_read_write): Flush
      * lib/ecpp.c (compute_h): Change prototype and enable reading and writing
        of class numbers depending on tmpdir.
        (ecpp1): Adapt function call.
    • Andreas Enge's avatar
      Prepare the use of data files for ECPP. · a90948a8
      Andreas Enge authored
      * lib/cm.h (cm_file_open_write, cm_file_open_read, cm_file_gzopen_write,
        cm_file_gzopen_read): Declare file name parameter as const.
      * lib/cm-impl.h (cm_file_open_read_write): Declare file name parameter
        as const.
      * lib/ecpp.c (ecpp1): Add parameter for temporary directory.
        (cm_ecpp): Add parameter for temporary directory and adapt function call.
        Make unrelated trivial change to timing output.
      * lib/file.c (cm_file_open_write, cm_file_open_read,
        cm_file_open_read_write, cm_file_gzopen_write, cm_file_gzopen_read):
        Make file name parameter const.
      * src/ecpp.c (main), src/ecpp-mpi.c (main): Adapt function call and use
        CM_ECPP_TMPDIR environment variable.
      * tests/tecpp.c (test_ecpp): Adapt function call.
      * doc/cm.texi: Document changes.
      * doc/version.texi: Update date.
  7. 01 Jul, 2022 3 commits
    • Andreas Enge's avatar
      Discretise the maximum discriminant more. · 82e26fff
      Andreas Enge authored
      * lib/ecpp.c (ecpp1): Choose Dmax as the minimum power of 2 not below the
        previous value, with a minimum of 2^20. Catch an out of memory error.
    • Andreas Enge's avatar
      Use a bound on B depending only on the number of workers in ecpp-mpi. · 0cb86389
      Andreas Enge authored
      This simplifies the code for parallelising trial division jobs: Each worker
      handles all numbers and a fixed chunk of the primorial.
      * lib/cm-impl.h (cm_mpi_get_tree_gcd): Drop now unused parameter in function
      * lib/ecpp.c (trial_div): Drop now unused parameter in function. Adapt
        function call.
        (find_ecpp_discriminant): Adapt function call.
        (ecpp1): Set B to 2^29 times the number of workers, independently of the
        size of the number to be proved.
      * lib/mpi.c (compute_no_prim): Remove function.
        (cm_mpi_get_tree_gcd): Drop function parameter. Simplify code.
        (mpi_worker): Adapt function call and simplify code.
    • Andreas Enge's avatar
      Count timings for class numbers only once. · 9019085b
      Andreas Enge authored
      * lib/ecpp.c (compute_h): Do not cumulate class number timings over several
  8. 29 Jun, 2022 2 commits
    • Andreas Enge's avatar
      Replace the BPSW test of gmp by a Miller-Rabin test to base 2 from 3000 bits. · 7b41a7c5
      Andreas Enge authored
      * lib/nt.c (miller_rabin): New function.
        (cm_nt_is_prime): Use new function.
      * lib/cm-impl.h (cm_nt_is_prime): Refine prototype.
      * NEWS: Add entry for change.
    • Andreas Enge's avatar
      Flush stdout. · 5e53e4b2
      Andreas Enge authored
      This seems to make a difference when running ecpp-mpi with srun instead
      of mpirun.
      * lib/ecpp.c (contains_ecpp_discriminant, find_ecpp_discriminant, ecpp1,
        cm_ecpp_one_step2, ecpp2): Flush stdout.
      * src/params.c (print_libraries): Flush stdout.
  9. 28 Jun, 2022 1 commit
    • Andreas Enge's avatar
      Add more progressive debug information. · 0ad91f25
      Andreas Enge authored
      * lib/ecpp.c (contains_ecpp_discriminant): Add debug parameter and output.
        (find_ecpp_discriminant): Adapt function call. Add debug output.
        (ecpp1): Change indentation and slightly adapt debug output.
  10. 27 Jun, 2022 1 commit
    • Andreas Enge's avatar
      Let MPI sleep less. · 91b740a4
      Andreas Enge authored
      This follows a performance degradation observed by
      Hervé Mathieu <herve.mathieu@inria.fr>.
      This is a follow-up to commit 4a9a084a .
      * lib/mpi.c (mpi_worker): Reduce sleep from 1/100s to 1/10000s.
  11. 17 Jun, 2022 1 commit
  12. 01 Jun, 2022 2 commits
    • Andreas Enge's avatar
      Output debug information concerning qstar. · 44a8f136
      Andreas Enge authored
      * lib/ecpp.c (find_ecpp_discriminant): Add a debug parameter and output
        information during the search for qstar and discriminants.
    • Andreas Enge's avatar
      Move some ECPP output from debug to verbose mode. · e7bd118a
      Andreas Enge authored
      * lib/cm-impl.h (cm_ecpp_one_step2): Add a parameter for the job number.
      * lib/ecpp.c (cm_ecpp_one_step2): Print the job number instead of the size.
        (ecpp1, cm_ecpp_one_step2, ecpp2): Slightly reformat output and enable
        some output in verbose instead of debug mode.
        (ecpp2): Adapt function call.
      * lib/mpi.c (mpi_worker): Adapt function call.
  13. 16 May, 2022 7 commits
    • Andreas Enge's avatar
      Add an optional primality test before starting ECPP. · 41c4bcef
      Andreas Enge authored
      * lib/cm.h (cm_ecpp): Add a boolean parameter trust.
      * lib/ecpp.c (cm_ecpp): Add parameter trust and call to primality test.
      * src/params.h (evaluate_parameters_ecpp): Add parameter trust.
      * src/params.c (print_t_options): New function.
        (print_help_ecpp): Call new function.
        (evaluate_parameters_ecpp): Add and handle parameter.
      * src/ecpp (main), src/ecpp-mpi.c (main), tests/tecpp.c (test_ecpp):
        Adapt function calls.
      * NEWS: Document the change.
      * doc/cm.texi: Document the changes and drop the description of a
        parameter that has not been present for a while.
    • Andreas Enge's avatar
      Drop the tower parameter in ECPP, since it should always be set to true. · a446b199
      Andreas Enge authored
      * lib/cm.h (cm_ecpp): Drop tower parameter.
      * lib/cm-impl.h (cm_ecpp_one_step2, cm_mpi_submit_ecpp_one_step2): Drop
        tower parameter.
      * lib/ecpp.c (ecpp2, cm_ecpp_one_step2, cm_ecpp): Drop parameter and adapt
        function calls.
      * lib/mpi.c (cm_mpi_submit_ecpp_one_step2): Drop parameter and sending it.
        (mpi_worker): Drop receiving the value.
      * src/ecpp.c (main), src/ecpp-mpi.c (main): Adapt function call.
      * tests/tecpp.c (test_ecpp): Adapt function call.
      * doc/cm.texi: Adapt documentation.
    • Andreas Enge's avatar
      Prevent MPI from busy waiting by putting it to sleep. · 4a9a084a
      Andreas Enge authored
      Change suggested by Greg Childers <gchilders@fullerton.edu>.
      * lib/cm-impl.h: Include unistd.h.
      * lib/mpi.c (mpi_worker): Alternate non-blocking MPI message probing and
    • Andreas Enge's avatar
      Document the Primo file output. · 38ebe05c
      Andreas Enge authored
      * doc/cm.texi: Add a sentence on Primo file output. Remove the date from
        the PARI/GP bibliography key.
      * NEWS: Rewrite entries more verbosely.
    • Andreas Enge's avatar
      When ECPP file output is enabled, also create a file in Primo format. · 22149462
      Andreas Enge authored
      * lib/cm-impl.h (cm_file_write_ecpp_cert_primo): Declare new function.
      * lib/file.c (mpz_out_hex, cm_file_write_ecpp_cert_primo): New functions.
      * lib/ecpp.c (cm_ecpp): Create an additional .primo file if file output is
        enabled for the certificate.
      * NEWS: Add items for the next release.
    • Andreas Enge's avatar
      Make CM aware of its own version. · fe9275ed
      Andreas Enge authored
      * lib/get_version.c: New file.
      * lib/Makefile.am (libcm_la_SOURCES): Register new file.
      * lib/cm-impl.h (cm_get_version): Declare new function.
        CM_VERSION_STRING): New constants.
      * src/params.h: Include cm-impl.h.
      * src/params.c (print_libraries): Print new constants and call new function.
    • Andreas Enge's avatar
      Rename a function. · 35e69e96
      Andreas Enge authored
      * lib/cm-impl.h (cm_file_pari_write_ecpp_cert2): Rename to...
        (cm_file_write_ecpp_cert_pari): ...this.
      * lib/file.c (cm_file_pari_write_ecpp_cert2): Rename to...
        (cm_file_write_ecpp_cert_pari): ...this.
      * lib/ecpp.c (cm_ecpp): Adapt function call.
  14. 13 May, 2022 3 commits
    • Andreas Enge's avatar
      Save memory when computing prime products. · 38656379
      Andreas Enge authored
      * lib/pari.c (cm_pari_init): Use a smaller initial PARI stack.
        (cm_pari_prime_product): Instead of using zv_prod_Z, compute the prime
        product with mpz numbers. Free the PARI stack by a call to
    • Andreas Enge's avatar
      Do not require a minimal gain for the parallel version. · c628306e
      Andreas Enge authored
      This is expected to speed up proofs for difficult primes; instead of
      increasing the number of qstar beyond reason, we sidestep the issue by
      hoping to find an easier next prime of similar size. The certificate
      size is expected to increase, but since the parallel version treats many
      curves at once and chooses the one with the best gain, the difference
      should be small in most cases with sufficient parallelism.
      * lib/ecpp.c (ecpp1): Set delta to 2 in the parallel version.
    • Andreas Enge's avatar
      Make the minimal expected number of almost prime point orders lower. · cbe169cb
      Andreas Enge authored
      * lib/ecpp.c (find_ecpp_discriminant): Reduce the starting value of
        min_prime, and make it smaller than 1 in successive rounds. This should
        require fewer square roots in difficult cases.
  15. 04 May, 2022 3 commits
  16. 19 Jan, 2022 3 commits
    • Andreas Enge's avatar
      Document MPI and the -f parameter. · 8835db52
      Andreas Enge authored
      * doc/cm.texi: Document the MPI version of ECPP and the -f parameter for
        writing the certificate and checkpoints to a file.
    • Andreas Enge's avatar
      Rename ECPP option -o to -p. · 475edb14
      Andreas Enge authored
      * src/ecpp.c (main), src/ecpp-mpi.c (main): Rename variable output to print.
      * src/params.c (print_o_options): Rename to...
        (print_p_options): ...this and modify help text.
        (print_help_ecpp): Modify help text and function call.
        (evaluate_parameters_ecpp): Rename variable and parameter code.
      * doc/cm.texi: Update the documentation.
    • Andreas Enge's avatar
      Use less memory for the class number table. · 739dc683
      Andreas Enge authored
      This ends up being the main memory consumer on the main node; using int
      instead of long int cuts this consumption in half on 64 bit machines.
      * lib/cm-impl.h (cm_ecpp_compute_h_chunk, cm_mpi_get_h_chunk): Modify
      * lib/ecpp.c (cm_ecpp_compute_h_chunk, compute_h, compute_discriminants,
        compute_sorted_discriminants, expected_no_curves): Modify prototypes.
        (find_ecpp_discriminant): Modify prototype and adapt allocation.
      * lib/mpi.c (cm_mpi_get_h_chunk): Modify prototype and adapt MPI reception.
        (mpi_worker): Adapt allocation and MPI sending.