RSACracker

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <inttypes.h>
#include <limits.h>
#include <time.h>
#include <pthread.h>

bool isComprime(uintmax_t p, uintmax_t q, uintmax_t expectedResult);
uintmax_t gcd(uintmax_t p, uintmax_t q);
void generateErathostenesSieve(uintmax_t number, bool* erathostenesSieve);
uintmax_t zsqrt(uintmax_t number);
bool isPrime(uintmax_t number, bool* erathostenesSieve);
int main(int argc, char **argv);

struct arg_struct {
    uintmax_t from;
    uintmax_t to;
    uintmax_t searchedNumber;
    unsigned int threadNumber;
    bool* erathostenesSieve;
    bool* isComplete;
};

void generateErathostenesSieve(uintmax_t number, bool* erathostenesSieve) {
    for (uintmax_t i=0; i<number; i++) {
        erathostenesSieve[i] = true;
    }
    for (uintmax_t i=2; i<zsqrt(number); i++) {
        if (erathostenesSieve[i] == true) {
            for (uintmax_t j=i*i; j<number; j=j+i) {
                erathostenesSieve[j] = false;
            }
        }
    }
}

uintmax_t zsqrt(uintmax_t number)
{
    if(number==0) return 0;
    uintmax_t nextEstimate = number;
    uintmax_t result = 0;
    uintmax_t prevEstimate;
    do{
        prevEstimate = result;
        result = nextEstimate;
        nextEstimate = (result + number/result) >> 1;
    }while(nextEstimate != prevEstimate);
    return result;
}

bool isPrime(uintmax_t number, bool erathostenesSieve[]) {
    if (number <= 1) {
        return false;
    } else if (number == 2) {
        return true;
    } else {
        if (erathostenesSieve[number] == true) {
            return true;
        } else {
            return false;
        }
    }
}

void *searchForComprimesThread(void *vargp) {
    struct arg_struct *args = vargp;

    printf("Thread %d started its job! (searching from %"PRIuMAX" to %"PRIuMAX")\n", args->threadNumber, args->from, args->to);

    for (uintmax_t i = args->from; i<=args->to; i++) {
        if (*(args->isComplete) == true)
            break;
        if (isPrime(i, args->erathostenesSieve) == true) {
            for (uintmax_t j = i; j<=args->to; j++) {
                if (i*j > args->searchedNumber)
                    break;
                if ((isPrime(j, args->erathostenesSieve) == true) && (j != i)) {
                        if (i*j == args->searchedNumber) {
                            printf("[Thread %d] Found combination for %"PRIuMAX"! p = %"PRIuMAX", q = %"PRIuMAX"\n", args->threadNumber, args->searchedNumber, i, j);
                            *(args->isComplete) = true;
                            break;
                        }
                }
            }
        }
    }

    printf("Thread %d finished its job!\n", args->threadNumber);

    return NULL;
}

int main(int argc, char **argv) {
    char* endPointer;
    if (argc != 3) {
        printf("usage: %s [number to crack] [threads to be used]", argv[0]);
        return 1;
    } else {
        if (strtol(argv[2], NULL, 10) <= 0) {
            printf("Number of threads to be used must be greater than zero!\n");
            return 1;
        }

        int threadCount = (int)strtol(argv[2], NULL, 10);
        time_t beginning = time(NULL);
        uintmax_t searchedNumber = strtoumax(argv[1], &endPointer, 10);
        struct arg_struct args[threadCount];
        pthread_t searchingThreads[threadCount];
        bool *erathostenesSieve = malloc(searchedNumber*sizeof(bool));
        bool isComplete = false;
        printf("Searching for combinations for number %"PRIuMAX"\n", searchedNumber);
        printf("Generating Erathostenes' Sieve...\n");
        generateErathostenesSieve(searchedNumber, erathostenesSieve);
        printf("Creating arguments for threads...\n");

        for (int i = 0; i<threadCount; i++) {
            if (i == 0) {
                args[i].from = 2;
            } else {
                args[i].from = (searchedNumber/threadCount)*i;
            }
            if (i == threadCount-1) {
                args[i].to = searchedNumber;
            } else {
                args[i].to = (searchedNumber/threadCount)*(i+1);
            }
            args[i].searchedNumber = searchedNumber;
            args[i].erathostenesSieve = erathostenesSieve;
            args[i].threadNumber  = i+1;
            args[i].isComplete = &isComplete;
        }

        printf("Starting threads...\n");

        for (int i = 0; i<threadCount; i++) {
            printf("Starting thread %d...\n", i+1);
            pthread_create(&searchingThreads[i], NULL, searchForComprimesThread, (void *)&args[i]);
        }

        printf("Waiting for threads to finish their job...\n");

        for (int i = 0; i<threadCount; i++) {
            printf("Waiting for thread %d...\n", i+1);
            pthread_join(searchingThreads[i], NULL);
        }

        free(erathostenesSieve);

        time_t end = time(NULL);


        if (isComplete) {
            printf("Successfully found a combination for number %"PRIuMAX" in %ld seconds\n", searchedNumber, (long)(end-beginning));
            return 0;
        } else {
            printf("Didn't find any combinations for number %"PRIuMAX" in %ld seconds\n", searchedNumber, (long)(end-beginning));
            return 1;
        }
    }
}