The Sophie Germain Prime Project primarily aims to collect, analyse and distribute Sophie Germain primes. Such special prime numbers p have the additional condition that 2p + 1 is also prime (called a safe prime). Additional categorisation is provided for Safe primes (prime p with (p-1)/2 also prime) and Blum primes (p = 3 mod 4). Sophie Germain primes find extensive use in public key cryptography (like the Diffie-Hellman key exchange, SGCM and BBS) and primality testing (in the AKS primality test). A conjecture states that there are infinitely many Sophie Germain primes, but this remains an open question in number theory. A heuristic estimate for the amount of Sophie Germain prime numbers below n is given by V. Shoup's A Computational Introduction to Number Theory and Algebra as approximately 2Cn/ln(n)^2 ≈ 1.32032n/ln(n)^2 where C is the twin prime constant. The estimate asymptotically attains the real value of 2C∫₂ᴺdx/(log x · log(2x + 1)). It is surprisingly good:

The project is maintained by Kamila Szewczyk. It was first created to facilitate her research on the Blum-Blum-Shub random number generator and related cryptographic algorithms (like the Blum-Goldwasser cryptosystem). Large Sophie Germain primes (as big as 4096 bits) are used in the BBS generator to fulfill elementary security requirements; unfortunately they also take a long and generally unpredictable amount of time to find.

Some bounds on the security of BBS, like the one given by A. Sidorenko and B. Schoenmakers, Concrete Security of the Blum-Blum-Shub Pseudorandom Generator, suggest that the security of the BBS generator is strictly tied to the hardness of QRP and factorization, providing concrete values of n=pq and j. They suggest n=6800 bits in the modulus for a tangible level of security (under some assumptions about the running time of the GNFS), much higher than previously understood as safe estimates of n=768 bits.

The API is intended to be used as follows:

• GET /sophie-germain/count - Yields comma-separated output with fields total, safe and blum, representing the amount of primes recorded of each type in the database. Additional filtering is possible by setting the fields min_bits, max_bits, submitter, start_date, end_date. An explanation for their intended values can be found below.
• POST /sophie-germain/submit?prime=...&submitter=... - Submits a prime number to the database. The number is checked for validity and additional conditions (like Safe or Blum primes). Only 1000 hourly failed/duplicate requests to this end-point are allowed.
• GET /sophie-germain/get - Queries the database. Always returns a comma-separated pair of numbers where the first one is the ID, and the second one is the prime number. The optional parameter id allows retreiving a prime number by its ID; by default a random prime number that satisfies the criteria is returned. The parameters min_bits and max_bits specify the requested size of the prime number. Additional constraints may be placed using the flags safe and blum - by setting them to true. The date of submission can be constrained via start_date and end_date (UTC UNIX timestamps). submitter allows filtering by a specific submitter handle.

Contributing

In order to contribute to the Sophie Germain Prime Project, you can submit your own Sophie Germain primes using the form above or to the author in bulk via e-mail. The following C language program generates suitable primes of specified bit widths that are then automatically submitted to the database:

    1 #include <stdint.h>
    2 #include <stdio.h>
    3 #include <stdlib.h>
    4 #include <string.h>
    5 #include <gmp.h>
    6 #include <curl/curl.h>
    7 #define ASSERT(x, c, f) if (!(x)) { f; exit(c); }
    8 void get_random_safe_prime(mpz_t p, mpz_t q, size_t bits) {
    9   ASSERT(bits >= 10, 1,
   10     fprintf(stderr, "<bit-size> must be at least 10.\n"));
   11   FILE * f = fopen("/dev/urandom", "rb");
   12   ASSERT(f, 2, perror("Failed to open /dev/urandom"));
   13   size_t nbytes = (bits + 7) >> 3, mask = 1 << ((bits + 7) & 7);
   14   uint8_t buf[nbytes];  mpz_t two;  mpz_init_set_ui(two, 2);
   15   uint64_t P = 5ul * 7ul * 11ul * 13ul * 17ul * 19ul * 23ul * 37ul;
   16   for (;;) {
   17     ASSERT(fread(buf, 1, nbytes, f) == nbytes, 3,
   18       perror("Failed to read random bytes"));
   19     buf[0] = (buf[0] & (mask - 1)) | mask;
   20     mpz_import(p, nbytes, 1, 1, 0, 0, buf);
   21     mpz_sub_ui(p, p, ((unsigned) mpz_fdiv_ui(p, 12) + 1u) % 12u);
   22     uint64_t r = mpz_fdiv_ui(p, P);
   23     if ((r % 5u) >> 1 == 0 || (r % 7u) >> 1 == 0 ||
   24         (r % 11u) >> 1 == 0 || (r % 13u) >> 1 == 0 ||
   25         (r % 17u) >> 1 == 0 || (r % 19u) >> 1 == 0 ||
   26         (r % 23u) >> 1 == 0 || (r % 37u) >> 1 == 0) continue;
   27     r = mpz_fdiv_ui(p, 29ul * 31ul * 41ul * 43ul * 47ul * 53ul);
   28     if ((r % 29u) >> 1 == 0 || (r % 31u) >> 1 == 0 ||
   29         (r % 41u) >> 1 == 0 || (r % 43u) >> 1 == 0 ||
   30         (r % 47u) >> 1 == 0 || (r % 53u) >> 1 == 0) continue;
   31     r = mpz_fdiv_ui(p, 59ul * 61ul * 67ul * 71ul * 73ul);
   32     if ((r % 59u) >> 1 == 0 || (r % 61u) >> 1 == 0 ||
   33         (r % 67u) >> 1 == 0 || (r % 71u) >> 1 == 0 ||
   34         (r % 73u) >> 1 == 0) continue;
   35     mpz_powm(q, two, p, p);
   36     if (mpz_cmp(q, two) != 0) continue;
   37     mpz_fdiv_q_2exp(q, p, 1);
   38     if (mpz_tstbit(p, bits - 1) && mpz_probab_prime_p(q, 40) &&
   39         mpz_probab_prime_p(p, 50))
   40       break;
   41   }
   42 }
   43 typedef struct { char * ptr; size_t len; } rstr;
   44 size_t cwrite(void * ptr, size_t size, size_t nmemb, rstr * s) {
   45   size_t new_len = s->len + size * nmemb;
   46   s->ptr = realloc(s->ptr, new_len + 1);
   47   ASSERT(s->ptr, 5, perror("Failed to reallocate memory"));
   48   memcpy(s->ptr + s->len, ptr, size * nmemb);
   49   s->ptr[new_len] = 0;  s->len = new_len;
   50   return size * nmemb;
   51 }
   52 int main(int argc, char * argv[]) {
   53   ASSERT(argc == 3, 6,
   54     fprintf(stderr, "Usage: %s <bits-1> <submitter>\n", argv[0]));
   55   int bits = atoi(argv[1]);  char * submitter = argv[2];
   56   ASSERT(strlen(submitter) < 16, 7,
   57     fprintf(stderr, "Submitter name too long\n"));
   58   mpz_t p, q;  mpz_inits(p, q, NULL);
   59   get_random_safe_prime(p, q, bits);
   60   char * q_str = mpz_get_str(NULL, 10, q);
   61   CURL * curl = curl_easy_init();
   62   ASSERT(curl, 8,
   63     fprintf(stderr, "Failed to initialize libcurl\n"));
   64   size_t sz = strlen(q_str) + strlen(submitter) + 128;
   65   char * post = malloc(sz);
   66   snprintf(post, sz, "prime=%s&submitter=%s", q_str, submitter);
   67   rstr response; response.len = 0; response.ptr = NULL;
   68   curl_easy_setopt(curl, CURLOPT_URL,
   69     "https://palaiologos.rocks/sophie-germain/submit");
   70   curl_easy_setopt(curl, CURLOPT_POST, 1L);
   71   curl_easy_setopt(curl, CURLOPT_POSTFIELDS, post);
   72   curl_easy_setopt(curl, CURLOPT_WRITEFUNCTION, cwrite);
   73   curl_easy_setopt(curl, CURLOPT_WRITEDATA, &response);
   74   curl_easy_setopt(curl, CURLOPT_USERAGENT, "sophie-c-client/1.0");
   75   CURLcode res = curl_easy_perform(curl);
   76   ASSERT(res == CURLE_OK, 9,
   77     fprintf(stderr, "curl: %s\n", curl_easy_strerror(res)));
   78   long http_code = 0;
   79   curl_easy_getinfo(curl, CURLINFO_RESPONSE_CODE, &http_code);
   80   printf("Server response:\n%s\n", response.ptr);
   81   ASSERT(http_code == 200, 10,
   82     fprintf(stderr, "HTTP error: %ld\n", http_code));
   83 }

Then, using GNU parallel, this code can be compiled and executed as follows:

    1 #!/bin/bash
    2 cc search.c -o search -lgmp -lcurl -O2
    3 seq 1 5000 | parallel -j$(nproc) ./search 2048 "${USER:0:16}"

Please mind the API rate-limit of the /submit endpoint. Do not try to submit primes smaller or as big as 32 bits, as they are in the database already. In order to not exhaust the API on fast computers, consider submitting larger primes, such as 4096 bits or more.