Generating Recursive Safe Prime Numbers Using T-SQL

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.
 

Mixed Mode and Windows Authentication Considerations

One question that comes up when you are installing and configuring a SQL Server instance is whether to use Windows Authentication or Mixed Mode Authentication. Mixed Mode Authentication allows the use of both SQL Server and Windows Authentication. In SQL Azure there is only SQL Server authentication.

In Windows Authentication the Windows local or domain user account is authenticated by the Windows OS or Domain Controller. In the case of a local account that account is effectively a domain account with the domain being the local machine. Windows Authentication can be further differentiated into service accounts and user accounts. Service accounts should have an SPN and either be trusted for delegation or a managed service account. Fortunately, those decisions and some of the more complex scenarios involving cross domain authentication and Kerberos are externalized to Windows. That is to say that those concerns are removed from the database and put into Windows. The instance trusts the domain to vouch for the user accounts.

Each Windows Login has a SID associated with it. In the event that the Windows user is dropped from the domain the login will persist in the SQL Server instance. If the domain user is recreated from the tombstone object it will re-associate based on its SID. In the event that the tombstone is lost we can use Sidwalk migration components to map the SID. If you lost the SID from Windows you can still use Aaron Bertrand’s conversion function “GetWindowsSID” to get the Windows SID from the server_principals table for the login.

SQL Server logins authenticate at the SQL Server instance. This means that the same user and password combination won’t work for each and every database instance, unless they have been specifically configured to. SQL Logins can also be created for credentials and certificates. Credentials can be used to allow SQL Server logins to have specific permissions outside of instance the login lives on. Certificates are used to stored encryption keys which can be used to authenticate as well but are primarily for encrypting and decrypting messages. SQL Server logins can be recreated using a SID to enable access to databases in the event that the login had been dropped.

Like the Windows login each SQL User has a SID associated with it. And like the Windows login the SQL Login can be dropped and recreated in a manner that will disassociate the name from the SID. This happens at a different level than with the Windows login. The users associated with the SQL Login in the databases will persist, similar to when a domain user is dropped from Windows and the login persists. That means that if we recreate the login by name, the new login will not match the SID of the dropped login unless we specify it. We can usually retrieve that SID from the database. Greg Low points out that you can also update the database user SID, though he advises recreating the login with the user SID.

 

Word VBA Macro for Journal Entries

I have been using this macro for years. I have rewritten it several times. I find it to be quiet useful. It is comprised of four subroutines. The first two are the work I need done. The third evaluates the conditional that work is predicated on and calls the 2nd or 1st and 2nd. The 4th calls the 3rd and is bound to a keyboard shortcut in order to decouple the execution from the keyboard binding.

The first subroutine is called date header. As the name suggests it inserts a date header. I use header one for the date. For the purpose of keeping a journal, this is useful as it displays at the top level of the navigation pane (which has a checkbox on the view tab).

Sub DateHeader()
'
' DateHeader Macro
' Insert H1 Current Date
'
    Selection.Style = ActiveDocument.Styles("Heading 1")
    Selection.InsertDateTime DateTimeFormat:="dddd, MMMM dd, yyyy", _
        InsertAsField:=False, DateLanguage:=wdEnglishUS, CalendarType:= _
        wdCalendarWestern, InsertAsFullWidth:=False
    Selection.TypeParagraph
End Sub

The second subroutine is called time header. This subroutine inserts the current time in header 2. This appears subordinate to the date which is in header 1 on the navigation pane. This allows collapsing the navigation pane to the date level.

Sub timeHeader()
'
' timeHeader Macro
' Insert current time in H2
'
    Selection.Style = ActiveDocument.Styles("Heading 2")
    Selection.InsertDateTime DateTimeFormat:="h:mm am/pm", InsertAsField:= _
        False, DateLanguage:=wdEnglishUS, CalendarType:=wdCalendarWestern, _
        InsertAsFullWidth:=False
    Selection.TypeParagraph
End Sub

The third is called find today. This macro searches for an existing current date header and inserts one if there isn’t one. It also inserts the time. The same work can be accomplished with 4 fewer lines of code. Comment if you see it.

Sub FindToday()
'
' FindToday Macro
' This macro searches for the existence of the date header and inserts it at the end of the document if it is not found.
' If the date header is found it inserts the time at the end.
Dim vToday As String
vToday = Format(Now(), "dddd, MMMM dd, yyyy")
    Selection.Find.ClearFormatting
    Selection.Find.Style = ActiveDocument.Styles("Heading 1")
    With Selection.Find
        .Text = vToday
        .Replacement.Text = ""
        .Forward = True
        .Wrap = wdFindContinue
        .Format = True
        .MatchCase = False
        .MatchWholeWord = False
        .MatchWildcards = False
        .MatchSoundsLike = False
        .MatchAllWordForms = False
    End With
    Selection.Find.Execute
    
    If Selection.Text = vToday _
    Then
Selection.EndOf Unit:=wdStory, Extend:=wdMove
Selection.TypeParagraph
Application.Run "timeHeader"
    Else
Selection.EndOf Unit:=wdStory, Extend:=wdMove
Selection.TypeParagraph
Application.Run "DateHeader"
Application.Run "timeHeader"
  End If
    
End Sub

The third subroutine is call run ctrl alt D. This decouples the key binding from the execution. It affords the option to run additional or different subroutines for the ctrl alt D keyboard combination (this can done via a dialog launched by the customize button under the commands pane of the customize ribbon dialog of the options window launched from the home/file tab). I can also delete this macro if I need to start using that keyboard shortcut for its default purpose which is to insert a footnote reference to the current cursor location.

Sub runCtrlAltD()
'
' runCtrlAltD Macro
' Replace insert footnote with macro execution.
'
    Application.Run MacroName:="FindToday"
End Sub

Cortana’s Quiet Hours Could Be Better

In my last post I made it a point to laud the Gestures app for Window 8.1 (Lumia Denim). In this post I am going to briefly describe an issue I have with Quiet Hours. Quiet Hours is a feature to Cortana that allows you to configure just how silent you want silent mode to be and when. You can turn Quiet Hours on Right Now, at specific times, or when one or several calendars have an appointment marked as busy. You can also configure rules for breakthrough (e.g. if it is a member of the “inner circle”, or they call 2 times in 3 minutes). You can also configure a response message to your callers indicating you are unavailable.

I would like to see the option to allow breakthrough for the 1st call or for contacts associated with an appointment. My reason for this is that I mark appointments as busy so that I do not get interrupted on an important call. The problem comes when my important calls are for contacts not in my inner circle and they are calling me. If they don’t call me before the time the appointment is set for, they get blocked.

So Brilliant All of Humanity Should Be Ashamed It’s New.

It is now 2015 and I finally got my Lumia updated. Initially, I was expecting to get what was last year called the Cyan update which would bring my Window 8 phone to 8.1. I had my fun with Cortana for New Year’s. She is a bit more fun than Siri. I haven’t had the opportunity to take advantage of location aware reminders, but I have set up quite time. My post isn’t about Cortana. As brilliant as voice recognition is in an digital assistance no one should be ashamed it has taken so long to get it working. Digital sampling rates and short time Fourier analysis combined with ambient noise and the vocal affectations that make every person’s voice different leaves me kind of proud the technology is in my hands, even if it does tend to annoy people in line at the grocery store and bank.

No, this post is about something so brilliant it could only be simple. I downloaded and installed an app Microsoft has called gestures. It does specifically 4 things:

1. If the phone is ringing and I lift it to my ear, it picks up.
2. Silences incoming calls if I place the phone face down on a surface.
3. Mutes the microphone if I place the phone face down during a call.
4. Puts the call on speaker phone if I place the phone face up during a call.

Career advice you should never follow

2. Is one that seems self serving to mention as I am looking more at contract oriented work. It seems to me that the unspoken assumption that some employers expect this piece of unwisdom to be motive to turn a blind eye to unethical, unprofessional, and possibly illegal activities just to keep from job hopping. I work for pay and a sense of achievement (mostly from that pay), not win approval for sacrificing my ambition and potential in the name of loyalty hat is not reciprocated.

Lights Out (Merlin)

Earlier today I was watching a video from The Great Courses series. The lecturer was Arthur T. Benjamin of Harvey Mudd College. He was discussing strategies to solve a 3 x 3 lights out puzzle. It inspired me to write a T-SQL version of the game.

USE Experiment

/** Thanks to Professor Arthur T. Benjamin of Harvey Mudd Univserity for the inspiration. */

IF OBJECT_ID(‘lightsout’) IS NOT NULL DROP TABLE lightsout;–Technically Merlin.

CREATE TABLE lightsout

(

column1 BIT,

column2 BIT,

column3 BIT,

rownumber INT IDENTITY(1,1)

)

GO

We’ll use a trigger to enforce the one button push rule as well as to update the adjacent cell with their bitwise negation.

CREATE TRIGGER onebutton ON lightsout

INSTEAD OF UPDATE

AS

BEGIN

–Trigger to assure a single button push

IF @@ROWCOUNT > 1 OR

(SELECT TOP 1

ABS(

CAST(d.column1 AS INT)-CAST(i.column1 AS INT)

+ CAST(d.column2 AS INT)-CAST(i.column1 AS INT)

+ CAST(d.column3 AS INT)-CAST(i.column1 AS INT)

)

FROM deleted d

INNER JOIN

inserted i

ON d.rownumber = i.rownumber

) > 1

BEGIN

PRINT ‘Rule Break.’

ROLLBACK

END

ELSE

–Triggers to update on update

IF (SELECT TOP 1 rownumber FROM deleted) = 1

BEGIN

IF (SELECT TOP 1 deleted.column1 ^ inserted.column1

FROM deleted

INNER JOIN

inserted

ON deleted.rownumber = inserted.rownumber) <> 0

BEGIN

UPDATE l SET column1 = ~(l.column1) FROM lightsout l WHERE rownumber = 1;

UPDATE l SET column1 = ~(l.column1) FROM lightsout l WHERE rownumber = 2;

UPDATE l SET column2 = ~(l.column2) FROM lightsout l WHERE rownumber = 1;

END

IF (SELECT TOP 1 deleted.column2 ^ inserted.column2

FROM deleted

INNER JOIN

inserted

ON deleted.rownumber = inserted.rownumber)<>0

BEGIN

UPDATE l SET column1 = ~(l.column1) FROM lightsout l WHERE rownumber = 1;

UPDATE l SET column2 = ~(l.column2) FROM lightsout l WHERE rownumber = 1;

UPDATE l SET column2 = ~(l.column2) FROM lightsout l WHERE rownumber = 2;

UPDATE l SET column3 = ~(l.column3) FROM lightsout l WHERE rownumber = 1;

END

IF (SELECT TOP 1 deleted.column3 ^ inserted.column3

FROM deleted

INNER JOIN

inserted

ON deleted.rownumber = inserted.rownumber)<>0

BEGIN

UPDATE l SET column3 = ~(l.column3) FROM lightsout l WHERE rownumber = 1;

UPDATE l SET column3 = ~(l.column3) FROM lightsout l WHERE rownumber = 2;

UPDATE l SET column2 = ~(l.column2) FROM lightsout l WHERE rownumber = 1;

END

END

IF (SELECT TOP 1 rownumber FROM deleted) = 2

BEGIN

IF (SELECT TOP 1 deleted.column1 ^ inserted.column1

FROM deleted

INNER JOIN

inserted

ON deleted.rownumber = inserted.rownumber)<>0

BEGIN

UPDATE l SET column1 = ~(l.column1) FROM lightsout l WHERE rownumber = 1;

UPDATE l SET column1 = ~(l.column1) FROM lightsout l WHERE rownumber = 2;

UPDATE l SET column2 = ~(l.column2) FROM lightsout l WHERE rownumber = 2;

UPDATE l SET column1 = ~(l.column1) FROM lightsout l WHERE rownumber = 3;

END

IF (SELECT TOP 1 deleted.column2 ^ inserted.column2

FROM deleted

INNER JOIN

inserted

ON deleted.rownumber = inserted.rownumber)<>0

BEGIN

UPDATE l SET column2 = ~(l.column2) FROM lightsout l WHERE rownumber = 1;

UPDATE l SET column1 = ~(l.column1) FROM lightsout l WHERE rownumber = 2;

UPDATE l SET column2 = ~(l.column2) FROM lightsout l WHERE rownumber = 2;

UPDATE l SET column3 = ~(l.column3) FROM lightsout l WHERE rownumber = 2;

UPDATE l SET column2 = ~(l.column2) FROM lightsout l WHERE rownumber = 3;

END

IF (SELECT TOP 1 deleted.column3 ^ inserted.column3

FROM deleted

INNER JOIN

inserted

ON deleted.rownumber = inserted.rownumber)<>0

BEGIN

UPDATE l SET column3 = ~(l.column3) FROM lightsout l WHERE rownumber = 1;

UPDATE l SET column3 = ~(l.column3) FROM lightsout l WHERE rownumber = 2;

UPDATE l SET column2 = ~(l.column2) FROM lightsout l WHERE rownumber = 2;

UPDATE l SET column3 = ~(l.column3) FROM lightsout l WHERE rownumber = 3;

END

END

IF (SELECT TOP 1 rownumber FROM deleted) = 3

BEGIN

IF (SELECT TOP 1 deleted.column1 ^ inserted.column1

FROM deleted

INNER JOIN

inserted

ON deleted.rownumber = inserted.rownumber)<>0

BEGIN

UPDATE l SET column1 = ~(l.column1) FROM lightsout l WHERE rownumber = 3;

UPDATE l SET column1 = ~(l.column1) FROM lightsout l WHERE rownumber = 2;

UPDATE l SET column2 = ~(l.column2) FROM lightsout l WHERE rownumber = 3;

END

IF (SELECT TOP 1 deleted.column2 ^ inserted.column2

FROM deleted

INNER JOIN

inserted

ON deleted.rownumber = inserted.rownumber)<>0

BEGIN

UPDATE l SET column1 = ~(l.column1) FROM lightsout l WHERE rownumber = 3;

UPDATE l SET column2 = ~(l.column2) FROM lightsout l WHERE rownumber = 3;

UPDATE l SET column2 = ~(l.column2) FROM lightsout l WHERE rownumber = 2;

UPDATE l SET column3 = ~(l.column3) FROM lightsout l WHERE rownumber = 3;

END

IF (SELECT TOP 1 deleted.column3 ^ inserted.column3

FROM deleted

INNER JOIN

inserted

ON deleted.rownumber = inserted.rownumber)<>0

BEGIN

UPDATE l SET column3 = ~(l.column3) FROM lightsout l WHERE rownumber = 3;

UPDATE l SET column3 = ~(l.column3) FROM lightsout l WHERE rownumber = 2;

UPDATE l SET column2 = ~(l.column2) FROM lightsout l WHERE rownumber = 3;

END

END

END

GO

Let’s insert some random bits.

–Random bits

INSERT INTO lightsout

SELECT CAST(ROUND(RAND(),0) AS BIT) column1

,CAST(ROUND(RAND(),0) AS BIT) column2

,CAST(ROUND(RAND(),0) AS BIT) column3

UNION ALL

SELECT CAST(ROUND(RAND(),0) AS BIT) column1

,CAST(ROUND(RAND(),0) AS BIT) column2

,CAST(ROUND(RAND(),0) AS BIT) column3

UNION ALL

SELECT CAST(ROUND(RAND(),0) AS BIT) column1

,CAST(ROUND(RAND(),0) AS BIT) column2

,CAST(ROUND(RAND(),0) AS BIT) column3

Correlation and Causation

Today’s email newsletter from Brent Ozar linked Flowing Data’s best of 2014 data visualization. Hidden among the bar charts and rose diagrams and the New York Times standard stunning collection of visualizations was Tyler Vigen’s Spurious Correlations. I am in awe, from the time that I found excuses not to correlate the population of wild asses and election results for a contest Tableau was sponsoring until I saw a graphic using Godzilla to compare military spending by country (guess who is Godzilla and who is a midsize high rise) I have been enamored by data visualization, and even more so when it is done to humorous effect. I particularly disturbed by possibility that someone might be particularly disturbed by the fact that for every billion dollars in sales at General Mills 2.3-2.5 women in California die by slipping and falling.

http://tylervigen.com/view_correlation?id=28625