I know what you are thinking: What is a recursive prime number? Why would I want to generate a list of them?
Ok, never mind the second question, how do I generate recursive safe prime numbers? I presume I will learn to generate primes along the way.

The first question is easy to answer… sort of. The short answer is: A recursive safe prime number is a member of a set of prime numbers I discovered (invented/defined). As far as I know it is a set of prime numbers I was the first to define. Essentially it is a safe prime number (2p+1) such that the Sophie Germain number (p) is also a safe prime. In other words it is a prime number such that the middle number has a number on either side that are prime such that the middle number has a number on either that are prime such that recursive etc. (e.g. 2(2(2(2(2p+1)+1)+1)+1)+1 will be a recursive safe prime if p is a safe prime and the result is also prime).

The second question is not as easy to answer but I’ll try.

1. You want to show off what Tom showed you in hopes that you might share in that remote possibility that he’d win a Fields medal for it. The clock is ticking on my eligibility.

2. You want to improve your understanding of safe primes and Sophie Germain primes supportive of your understanding of strong primes in RSA standards and figure that T-SQL might be easier to read than C or any of the cryptic diagrams you find in cryptography texts.

3. You want to.

The third question is the reason I wrote this post. And yes we will generate primes. First we will need a place to put them. Since we are using T-SQL a table seems a reasonable enough place to put them.

CREATE TABLE [dbo].[primes](
	[n] [int] IDENTITY(1,1) NOT NULL PRIMARY KEY,
	[p] [int] NOT NULL
)

Next we will need to generate some primes to put in our table. I use a simple counter with a trial division to test primality and insert those that don’t fail. I did some trial and error to get @n. It runs in under 10 minutes on my laptop. Your mileage may vary.

DECLARE @n INT; SET @n = POWER(2,20)-1;
DECLARE @m INT; SET @m = 1;
DECLARE @k INT;
WHILE @m <= @n
BEGIN 	 
SET @k = FLOOR(SQRT(@m)); 	
     WHILE @k > 1 
	BEGIN
	IF @m % @k = 0 GOTO NotPrime;	
	SET @k = @k - 1;
	END

PRINT @m
INSERT INTO [prime].[dbo].[primes]
           ([p])
     VALUES
           (@m)
NotPrime:
SET @m = @m + 1;
END

As of the writing of this post the largest prime in my table is 1048343. If we set @n in the above script to 1048344 we can run it again to get more prime numbers. Unfortunately, the largeR the numbers we test the larger their square roots and subsequently the greater the number of modulus tests performed in the inner loop. That means each successive prime we find will take longer than the last. Fortunately, finding the subset of primes we are looking for is a selection from a table.

WITH sophie_germain AS (
SELECT p.[n]
      ,p.[p] sophie_germain
	  ,sp.[p] safe
  FROM [prime].[dbo].[primes] p
INNER JOIN [prime].[dbo].[primes] sp
	ON (2 * p.[p]) + 1 = sp.[p]
	--AND p.[p] > 1
)
SELECT sg.n, sg.sophie_germain, sg.safe
, rs.safe recursive_safe
	FROM sophie_germain sg
		LEFT JOIN
		sophie_germain rs
		ON (2 * sg.safe + 1) = rs.safe
ORDER BY n

There would also be a subset of subsets implied such that they are recursive primes with a recursive prime for their Sophie Germain number. And another set would then be implied as is the nature of recursion. These I would call these double recursive primes, triple recursive primes, n-tuple recursive primes.