Arija A.'s Webshrine for Safe & Sophie Germain Prime Numbers

Safe and Sophie Germain primes form the set Kn, numbers where p is prime, 2p+1 is prime, and (p-1)/2 is prime. These numbers captivate me because they combine rarity, structure, and aesthetic symmetry. Each of these primes tickle my brain due to their interesting mathematical and aesthetic properties.

# Origin of My Obsession

The obsession began in early 2024 when I was going down the quantum computing rabbit hole and ended up on the Wikipedia page for Safe & Sophie Germain prime numbers. These special primes caught my eye because they have properties that make them resistant to some classes of attack, even some quantum-level ones. That felt interesting. I asked myself: Maybe RSA isn't entirely doomed in the quantum future after all? Which further deepened my curiosity, and has turned into a hyperfixation since.

# Aesthetic Fascination

The numbers alone weren't "aesthetic" enough for me on their own per se, doesn't mean that the numbers aren't beautiful - they are - but I mean bit level aesthetics and properties. I started adding my own extra rules to make them both interesting and cryptographically secure...er?

Every member of Kn has n bits exactly, n/2 transitions from 0 to 1 or 1 to 0, and exactly half its bits set. It's neat, it's symmetric, and it feels good. These constraints give a nice balance of entropy and structure, make the primes ridiculously hard to find, and make them really satisfying and beautiful. Modern CPUs struggle to stumble on one by chance.

# Cryptographic Implications

These primes make me wonder: would a quantum computer actually do any better?

If yes, that might mean RSA still has a pulse, but also that these primes could be useful for something else entirely. Maybe they could form the core of a new cryptosystem - one that uses the encoding feature of primes: p, (p−1)/2, and 2p+1. It's an elegant idea, using structure itself as security. True that ECC exists for security purposes, but I am not here for pure pragmatic implications, but to find something stranger, more symmetric, unique, maybe even more powerful? Who knows.

And honestly, they just make me happy. There's no proof that infinitely many exist. Nobody knows how the bit rules affect their density. The maths around them is like a fog - you can see shapes moving but can't tell what they are yet.

# Generation Program

Back when my obsession started I wrote my own generator program - genprime.c, efficiently compiled with compile.sh - and I've been refining it for a while now. It started slow, painfully slow, and now it can find a 512-bit Kn with all my bit restrictions in just a few seconds, and a 1024-bit one in about 20-30 minutes. Every new optimisation feels like another little victory.

# Safe and Sophie Germain primes database

There's a Safe and Sophie Germain prime number database at https://iczelia.net/sophie-germain/ where you can find thousands of primes and contribute your own. It's awesome :3 You should contribute - at least I contributed my favourite primes, and I am the only contributor in the 4096 bit space because I submitted my favourite number! I adore this database.

# Properties of These Primes

  1. Primality Conditions

    1. p is prime
    2. 2p+1 is prime
    3. (p-1)/2 is prime

  2. Bitwise Structure

    1. p is exactly n bits long
    2. Half of the bits in p are set
    3. Transitions between 0 & 1 occur n/2 times

  3. Modular Constraints

    1. p mod 12 is 11
    2. 3 and 12 are quadratic residues
    3. p - {3, 4, 9, 12} are quadratic nonresidues

These are pretty much the most useful ones in using digital computing to find these primes. There are other properties though!

# Favourite Primes

  1. 894627877922431597134515203709762589998700435180763273639715207089837060219844344783604754082603859518959107241490534812493374071641623761611998892742719833336808796138910977474168536205485419580947916785402729868752234509799136536148808391770057813706627329453071602565554412102725908562352206953946149068696111061613887417310544092716950154837578161555969969957963653707318011356516756334451749330018053377844532649438730888347784543256747358224452825167655645083913529061312178958222144238131888041971591783336334701190151375479565140052546251891006929672599407544078255651762054013741392403146915669028271565511846690404090994992658047204429830200292191922016042323743777918229333522893078811383714526070618932442927402308048418654147971571602447272363344838681371295555362545226018117061145997569862532229595077017187476305536811429423340680174373226243080002658529732659118557043337536038550246885648922266791804412299406938271554896788577723681937469105430669972571444052192348763796879902124025926888494786452121782382825657954779270667907209611694984788053640720331895602337885224215338975382514431052102595919618337833546288578440871345907629535667760714358957497337300757644001224791354963749415423240873244243927583101483 (THANK YOU SO MUCH PL3B ON BSKY, I'VE BEEN LOOKING FOR THIS PRIME FOR MONTHS AND YOU FOUND IT IN ONE DAY!!!)
    • I've been looking for this prime for months 24/7 and pl3b on bsky has given me the Christmas blessing of running the genprime program on 384 CPU threads. This number is relatively perfect: bit distribution, bit count, size, everything it PERFECT. Finally!! I've been looking for such a prime for months upon months now and pl3b, after finding my silly post on bsky and having 384 8xEPYC 7443 CPU threads computed the prime in one day. I am eternally grateful for this sacrifice. Now having this prime I have actual cryptographic power at my disposal - sure it's public, but it's actually here now. I want to see how SSGs stand against normal primes and/or even RSA in application. I don't have much compute, but I am so happy now!!! I am shaking as im typing this right now like giu8ehugfwehigfwehiweufhwfue. I can no longer put away researching these primes in greater death and Today it begins. —2025, December 5th
  2. 17533046421132021796857791897465644968146809455990366530806058132585600975387877385336523206676920015718305188725329192003004993041300670314023014496494840976678389134279418320723672504341559751583943820720539525712415674995661058364889113572816923710290486193828400489264649823632451000198262233036831252236697374384459598432496470857631908780255908198112850704155412223902608362354071760685437900931592268455834367713836033752301914405407348247605499717144203311890210226114365986163693547802287263571221263413494899357422611992140773589324261186988084912417571492940984972166315100103805599927901264432241618044359 (thank you [person] on the fediverse, I don't quite remember who you are but please contact me if you find who it is!)
  3. TBD :D

<- Back to shrines list