Introduction

A Mersenne Prime is a type of prime number of the form  2ⁿ - 1, where n is also a prime number [1]. While seemingly simple, this formula of 2ⁿ - 1 has consistently produced the largest prime numbers in the world. The current largest prime number, 2^82,589,933 - 1,  is a Mersenne Prime and has 24,862,048 digits [2]. While Mersenne Primes seem like they serve little use aside from being astoundingly large numbers, massive prime numbers actually have many uses especially for cryptography and information technology [3]. Finding new Mersenne Primes has been a goal of the mathematics community for centuries, with the origins of  Mersenne Primes dating back to 1536. Currently the search for prime numbers has led to some major advancements in the field of distributed computing.

Existing Methodology

Currently there have been 51 Mersenne Primes identified, with the last 17 Mersenne Primes having been discovered by the Great Internet Mersenne Prime Search (GIMPS) [1]. GIMPS is one of the largest distributed computing projects in the world. Volunteers sign up and download the GIMPS software to their machines. The GIMPS software then runs in the background of every volunteer’s computer looking for large primes and reporting its findings. The GIMPS software is specially built to be hyper efficient for finding large Mersenne Primes and is not a general purpose prime finding software.

Motivations and Methodology

Rather than trying to outperform GIMPS, the scope of this project was narrowed down to using a Mersenne Prime search as a tool for benchmarking different tools created by Distributive and demonstrating the potential for distributed computing to tackle cutting edge problems. Four methodologies were employed in this project, two conventional approaches to the problem and two distributed computing approaches to the problem.

Approach 1: Python is one of the most popular coding languages especially for computation and data analytics. Python is one of the most accessible languages and gives users the ability to create powerful programs with relatively little programming experience. Its main issue is that it is a computationally slow language.

Approach 2: JavaScript is the main programming language used in web development. It is also  the coding language that the Distributive Compute Protocol (DCP) uses. While it is less user friendly than Python it is significantly faster.

Approach 3: The Distributive Compute Protocol (DCP) is the flagship product of Distributive. This product allows users to create programs that utilize distributed computing to greatly accelerate their workflow. DCP runs JavaScript code as it is a web based application.

Approach 4: Bifrost is a tool built around DCP that allows users to write Python code and run that code through the DCP protocol.  This makes creating code for DCP much easier as Python is generally considered a more accessible language, while still allowing users to harness the power of distributed computing. Bifrost is slower than DCP because it has to set up an environment where it can run Python code.

This project follows suit with century-old mathematicians in finding large Mersenne primes, this time using DCP with both JavaScript and Python. The JavaScript code works with DCP, but the Python part works with Bifrost. In detail, this program splits the number range for finding Mersenne primes into slices, and then distributes slices to workers. The slice size can be controlled by the program user. Each of the workers takes one slice at a time. All workers run the Lucas-Lehmer test on the slice assigned to them at the same time, and return results back once a test is completed. ‍

Data Collection

For each approach, multiple runs of the prime searching program were completed with each run being timed and recorded. The parameters of each run would change between runs with the amount of numbers being investigated for primality changing. The range of numbers being investigated spanned from n=0 to n=10000 in  2ⁿ -1. Data on the time until completion for each approach was collected and plotted.

Results

The graph below contains the data on the timed runs of the distributive search program with JavaScript, Python, DCP and Bifrost. Note that for DCP and Bifrost, the slice size represents how much work each computer would receive when performing its computation.

‍

The results of this experiment yielded interesting findings. Python proved to be far slower than JavaScript, a known but important quality to quantify. Bifrost outperformed Python after only roughly a minute of work, showing Bifrost’s potential to greatly speed up Pythonic workloads. Bifrost has not been shown to outperform JavaScript, but the trends from this graph indicate it is likely to outperform JavaScript at higher number ranges. DCP outperformed JavaScript but only at the higher end of the number range employed. Further testing would yield even more information about DCP’s ability to outperform JavaScript.

Conclusion and Future Work

Results show that Bifrost will outperform traditional computing methods for tasks that only take minutes, while DCP outperforms JavaScript for slightly larger jobs. While this project yielded interesting results, it would be interesting to perform experiments with larger number ranges to truly test the limits of distributed computing. It would also be beneficial to compare the examined methodologies in this project with the C programming language as it is among the fastest programming languages in the world. Another potential expansion of this project is creating Python code with a C engine and using that with Bifrost as it would provide a considerable speed boost to Bifrost. Overall, the project was a success and revealed interesting insights into Distributive’s technology and future avenues of exploration for subsequent projects.

Citations

[1] GIMPS, “Great internet mersenne prime search - primenet,” 2^P-1. [Online]. Available: https://www.mersenne.org/.

[2] J. Palca, “The world has a new largest-known prime number,” NPR, 21-Dec-2018. [Online]. Available: https://www.npr.org/2018/12/21/679207604/the-world-has-a-new-largest-known-prime-number. 

[3] B. Smith, “This is how prime numbers keep your online shopping secure,” ABC News, 19-Jan-2018. [Online]. Available: https://www.abc.net.au/news/science/2018-01-20/how-prime-numbers-rsa-encryption-works/9338876#:~:text=The%20reason%20prime%20numbers%20are,17%2C%20or%20187%20and%201. 

Watch the presentation here.