Code Monkey home page Code Monkey logo

gmprime's Introduction

gmprime

gmprime is a software that can perform a Lucas-Lehmer-Riesel primality test for numbers of the form h*2n-1.

Motivation

The main motivations for why gmprime has been written are:

  • Implement in C, the Lucas-Lehmer-Riesel test as implemented by lucas.cal.
  • Implement optimized search for V(1) values that satisfy the Rödseth criteria.
  • Implement the Lucas-Lehmer-Riesel primality test using GNU MP library calls.
  • Allow for detailed debugging of each computational sub-step including each square, subtract 2 and modulus operations.
  • Allow to check the correctness of computational sub-step using calc.

The gmprime code is open source to serve as a generic learning base for all those interested in understanding how the Lucas-Lehmer-Riesel primality test works. If you are trying to find very large prime numbers, such as a new largest known prime, there currently is much better software for that purpose. It can be used also for finding new prime numbers, but finding new prime numbers is not the purpose for why it was written.

Results

Generating V(1)

Generating V(1) is the fastest sub-step, but at the same time the most difficult to understand part of the Lucas-Lehmer-Riesel primality test. We used the Rödseth method to generate the initial V(1) value.

In general, we found the Rödseth algorithm to be the most straightforward to implement and we recommend to use it, given that it performs well in comparison with the other methods.

Generating U(2)

Generating U(2) = V(h) requires to compute approximately log2(h) terms of the {Vi} sequence. Each iteration of this sub-step works by computing V(2x+1) and V(2x) until we reach V(h).

We found out that, during every iteration, the operations of computing V(2x+1) and V(2x) can be easily parallelized and do not need to be done sequentially and reduce the computation time of this sub-step by about 50%. For simplicity, this code does not perform this parallelized optimization. See goprime for an example of this type of optimization.

Generating U(n)

Generating U(n) is the most time consuming sub-step of the Lucas-Lehmer-Riesel primality test, as it requires to compute n terms of the {Ui} sequence where each term depends on the previous term (which makes it hard to parallelize).

At the time this code was written, squaring using FLINT was FLINT is slightly faster than GNU MP. For this code, we chose to use GNU MP as that library is more commonly used. For an example of an implementation using FLINT, see goprime's C implementation.

You may wish to explore other squaring solutions. We expect that approaches based on Crandall's transform, George Woltman's Gwnums library, Colin Percival paper or hardware-specific hand tuned code (such as using C with inline assembly to access special hardware instructions) can achieve results at least one order of magnitude faster than what we observed so far.

Again, the purpose of this code is NOT to be the fastest. This code was written to help people understand how to implement the Lucas-Lehmer-Riesel primality test.

Usage

gmprime

# compile
#
$ make all

# perform some consistency checks
#
$ make check
$ make small_composite_check
#
# see the Makefile for an more extensive list of check rules

# Run gmprime with any h and n
#
$ ./gmprime 9448 9999
$ ./gmprime 1 23209
$ ./gmprime 391581 216193

# Run with verbose mode
#
$ ./gmprime -v 199815 163
$ ./gmprime -v 3545685 3187

# Use calc to verify correctness of the calculation
# This part requires calc to be installed and in your path
#     See https://github.com/lcn2/calc
#
$ ./gmprime -c 418791945 71 | calc -p
$ ./gmprime -c 2566851867 5634 | calc -p

Future work

  • Add checkpoint and restart functionality, periodically saving state and allowing for a later restart from such a state.

Contribute

Please feel invited to contribute by creating a pull request to submit the code or bug fixes you would like to be included in gmprime.

You can also contact us using the following email address: gmprime-contributors (at) external (dot) cisco (dot) com. If you send us an email, please include the phrase "gmprime author question" somewhere in the subject line or your email may be rejected.

License

This project is distributed under the terms of the Apache License v2.0. See file "LICENSE" for further reference.

gmprime's People

Contributors

lcn2 avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.