README

Multithreaded factoring

Factors a small RSA-style composite n = p · q using parallel trial division.

The program designed to have a Master-Worker architecture. The Master batches the range of numbers to check for divisibility, and enques those batches. Workers concurrently dequeue and check. The first worker to find a factor publishes it and triggers a global early stop. Coordinator prints p and q = n/p and blocks till other threads terminate using the POSIX join call.

Usage

1. To compile on new machine do:
   gcc -O2 -pthread rsa_factor.c -o rsa_factor -lm -lrt

   OR

   execute the compile.sh file

2. To run compiled executable do:
   ./rsa_factor -n 591026828771 -w 16 -q 1024 -c 5000 > log.txt arguments:

• -n : number

• -w : number of workers

• -q : bounded buffer size

• -c : chunk size

  OR

  execute the test.sh file

  the output is saved to output.txt file, and logs are saved to log.txt file in the same directory.

Implementational details

Queue operations:

Enqueue and Dequeue operations are thread safe. using condition variables for full and empty buffer.

Chunking strategy:

1. The data is divided into chunks and enqueued(producer) in the main function, after the creation of worker threads so that workers can concurrently begin processing before all chunks are pushed to the queue. This ensures that there is no deadlock (buffer full before starting consumer threads - producers will wait forever) \

![](./images/thread_creation.png)

2. These chunks are independantly processed by each worker.\

![](./images/worker.png)

5. Early exit:

   1. the global found flag is set and finished_cond condition variable is signaled when a factor is found.

   2. If factor is not found, parent thread main waits untill all chunks are processsed. This is signaled by the finished_cond condition variable.