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

# 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.

# I Was Wrong! - 2026-01-04

During my quantum rabithole somewhere I saw that these primes protected against some quantum-level attacks. That felt interesting, but odd. 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.

What I've been doing is mainly academic research, writing programs to analyse SSGs of different sizes, and seeing how easy is it to factor these primes — so far, with my limited resources, my research has been futile (as of January 4th of 2026)

In late 2025 to early 2026 I did more research (as I had a little more time on my hands) and I finally answered this question: No. These primes do NOT provide any quantum resistance. — Shor's algorithm still defeats these primes. In practice, having large prime subgroups does help in classical computing (and I think that's where I fell short in my research), so it's still quite important to have this in short-term, but long-term security is still doomed. Sad, disappointing, but maybe I can still do more with it.

Detour: Okay... what's special about them??

This experience got me thinking: am I just being overly optimistic? Finding too much beuty in complexity and rarity?

I don't know. I've been looking for something truly special and hard-hitting for two years now and have not found anything so impressive it would blow one's socks off. Like "oh wow! They're hard to factor on classical computers!" like what's so special about that — given a big enough prime product you could not for the life of you factor them.

All my tries to prove whether there's an infinite amount of such primes have also been fruitless as well, but I guess I'm no professional mathematician either, so... Just a person fucking around and that's about it.

I'll keep them on my backburner for a bit, but my research on small-sized primes is probably over, I was not able to find anything truly new or interesting, though, to be fair, I don't have much time to dedicate to these primes, this is just a side-side-side-hobby :) I think I'll move onto something that's been on the roster since I discovered these primes: maybe I can make a cryptographic algorithm based on these primes?

The idea is appealing and there's both binary and mathematical properties that I could maybe use? I don't know. It's midnight for me as of writing this, so I'll revisit this another day.

However the new group of arbitrary conditions I haven't explored: the perefect SSGs — I have not done much research. I just came up with these conditions on aesthetics as my favourite number matched these conditions :)

# Aesthetic Fascination

Anyway, 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? This is arbitrary, generally optimising for as much entropy as possible.

Every member of K_n 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.

# 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 K_n 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 (custom stuff, not specifically for SSGs but set K_n)

   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 (i.e., gray_code - 1)

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!

# Perfect SSGs?

Not to be confused with perfect numbers, perfect SSGs are primes p that exibit the following properties:

1. p is prime
2. 2p+1 is prime
3. (p-1)/2 is prime
4. Bit length of p is a power of 2
5. Set bit (1) count of p is exactly n/2 (where n is bit length of p)
6. Transition count of p is exactly n/2
7. p is considered cryptographically secure:
   1. p is at minimum 2048 bits
   2. p is generated with a cryptographically secure pseudorandom number generator (CSPRNG), or a secure pseudorandom number generated that's seeded with a CSPRNG (this number should be: unpredictable, uniform, and use a secure entropy source)
   3. p must pass three levels of Miller-Rabin primality test: weak (minimum 2 reps), medium (minimum 4 if n < 32, else min(n / 8, 16) if n >= 32 reps), and strong (minimum n / 4 reps)
8. 2p+1 must pass three levels of Miller-Rabin primality test: weak (minimum 2 reps), medium (minimum 4 if n < 32, else min(n / 8, 16) if n >= 32 reps), and strong (minimum n / 4 reps)
9. (p-1)/2 must pass three levels of Miller-Rabin primality test: weak (minimum 2 reps), medium (minimum 4 if n < 32, else min(n / 8, 16) if n >= 32 reps), and strong (minimum n / 4 reps)
10. p is a blum prime (i.e., p = 3 (mod 4))

# 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!!!) -- ID ssg20251205-1704-4096p-pl3b
   • 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. 583749536150146011536016914419746424344146731751668377125685271216639917191008738171471883191542822972117805209527523323508307046577182808371876924711939099740123649609928626204933259019474742772316539057484394715163342143069584704449767105158344325831863405480838089307542206974007003456605048478023594754457720547156405347419213998720666498116762564881388245297275787650442814063684787640855918904924698061312896889177190718936635257983850763617889069576486460904984455192916366944885871770637151021870572044713677314332298557052429831477069740370510639458044729893334256912973119933369629369222236677649615685797185989227506376261501429828317256943796442684994087705503176444196773649519581090450188273266022035891494826355006067213703546724727460440825929239235575481411594838801904314560531838062628927892403720409671148173151389512400373429662983877440392226153729862606467279074494102353634882771047897874265921664844306212317225195913976511566416552727008141286556604115115119286110813915697987209224825307812894345762770686057982531498480687587229044706663329281855788349779845061246660542995056874303072565818590319020012142387482255737752327057970081857597484592134894783305664547735581556367815204613045206778302395975813847212294140992520519762435174905522393207416776408099995091957442309376461640149294410280226675698596315464164727524085810635729009696056107735349389857298829756641884596990744386756711006349183683383891056916982225304528936156803248819541342224472716605714639588592021552498605296662305304408253852774827045698161637833126725650114562142182516806176618607597013982436110935374516610113249862147285134918834893769407726541036522755520321738574357966780050941326792027547260651265621497187642184648231211784760430916832611731388720438185065189910601800984602717042438028333175599872776043135456883207411769397820752651636627931838826948324150913053049189419385081591568394803172172930614689715756505187154140249784895814617910851094616425690450726053616258911538400501825028578335990525890174031561182090625334384290906042362863083120718167964868966629259322404733228826882323942385532139722999551415154826923282452332927135744463164802303672215506233142419628020948850724997662084240167329430953089365167153797400985296173391534829557960562495881989344383346577260052535152586856047611157805595934474829675699927378832715077442484150847253269739441713798538928076083104757618117456129018919223366004991588982363435950969483531947319 -- ID ssg20251220-0111-8192-pl3b (thanks again, pl3b on bsky!!)
3. 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! - still, thanks for the ~6.5 hours on your 16-core CPU :D) -- ID ssg20241230-2200-2048u-anonfediverseperson
4. TBD :D

ID is in this format: ssgYYYYMMDD-HHMM-n(optional: [flags: p (perfect), u (uncertain credit/author/discovery/...)])-discoverer, e.g., ssg20140101-0100-512p-ari - a 512-bit perfect SSG prime discovered in 2014, January 1st, at 1 AM UTC by 'ari'. The ID must always be lowercase to stay case insensitive (for indexing reasons)