Thursday, December 23, 2010

If you need newgrp, you dun goofed (and "setuidgid" may be the culprit)

Recently, on a machine with custom upstart init scripts, I couldn't figure out why I couldn't access serial ports or USB devices, even though my username was in the dialout and plugdev groups in /etc/group.

Running the "groups" command, I could see that my groupset only contained my own personal group:

$ groups

I found that I could run "newgrp dialout" to get it added to my groupset:

$ newgrp dialout
$ groups
dialout credentiality

And looking online, I found various tricks people would use to run the commands they needed using newgrp.  (It's not trivial, since newgrp insists on creating a subshell).

But I kept getting the sense that newgrp should almost never be necessary anymore, now that modern unix systems have the notion of a groupset.

Turns out the culprit was "setuidgid", which we were using in the upstart scripts to run programs as me.  They said things like:

exec setuidgid credentiality startx

Now that I know to look for it, setuidgid's manpage points out that it "remov[es] all supplementary groups".  Which isn't very helpful if, for instance, a process needs to access files from both the "dialout" and "plugdev" groups.

Fortunately, there are several alternatives to setuidgid that preserve the group memberships you expect, and you can use the "groups" command to verify that:

# setuidgid credentiality groups

# su -c groups credentiality
credentiality adm disk dialout cdrom floppy sudo audio dip video plugdev

# sudo -u credentiality groups
credentiality adm disk dialout cdrom floppy sudo audio dip video plugdev

# start-stop-daemon -c credentiality -S --exec /usr/bin/groups
credentiality adm disk dialout cdrom floppy sudo audio dip video plugdev

# # chpst is in package runit (yet another init system, ugh.), and lets you specify a list of groups explicitly:
# chpst -u credentiality:credentiality:plugdev:dialout groups
credentiality plugdev dialout

Thursday, December 02, 2010

Carmichael numbers and Fermat primality

I did some recreational mathematics today, and created this plot, showing the number of values for which a^(n-1) = 1 (mod n), for all composite n in the range [3..10000]:

The formula a^(n-1) mod n appears in Fermat's Little Theorem, which says that for prime values of n, the result will always be 1, no matter what a you choose.  If you get a value other than 1, you know that n is composite.

That's neat because it lets us test whether a given n is composite much more quickly than by trying to factor it.  We call that the Fermat Primality Test.  

However, the converse doesn't always hold: sometimes a^(n-1)=1 (mod n) even if n is composite.  When  that happens for some a and n, we say that a is a false witness for n, since it incorrectly suggests that n might be prime.

And that's what the above graph shows: how many false witnesses there are for each value n up to 10,000.  In particular, I scaled the y axis so that it shows the percentage of relatively prime a values that are false witnesses.

Carmichael Numbers

Most interesting are the vertical lines in the graph that reach all the way to the top.  Those are the falsest of the pseudoprimes (with respect to the Fermat test).  They're called the Carmichael Numbers, and I've always found them fascinating, because the smallest of them is 561!  That's the leftmost line in the graph that reaches all the way to the top.

Just how prime are you?

The other thing I was surprised to find in this graph are what we might call the halfway-prime numbers -- numbers for which half of the witnesses will suggest primality with the Fermat test.  And there are one-third-prime numbers, and so on.

Merry Christmas!

All that graphing got me wondering how often a^(n-1) produces numbers other than 1.  So I created this image, which shows increasing values of n as you work downward, and shows how often we get a remainder r.  r is shown on the X axis, while the number of times it came up is shown as a color:

 0=black, 1=dark gray, 2=light gray, 3=blue, 4=orange, 5=red, 6 or more = white

The other trick is that in number theory, we sometimes talk about negative remainders.  If you're working (mod 5), you might get remainders of 0,1,2,3,4, but since the next remainder after 4 is 0 again, sometimes it's easier to think of a remainder of 4 as -1.  So instead of 0,1,2,3,4, we call them 0,1,2,-2,-1, and that's what I've done here. 

Consider the topmost orange pixel in the above image.  It's the 5th pixel from the top, so that whole row represents n=5.  The orange pixel (and all the ones below it) are the "remainder=1" column.  The column to the left of it is the "remainder=0" column, and the one to the right is "remainder=2".  Since 5 is prime, we expect a^4 to be 1 (mod 5) for all 4 possible values of a: 1,2,3 and 4.  And indeed, orange is the color for 4.

Two pixels down, you'll see a white pixel telling us that 7 is prime, since a^6=1 (mod 7) for a=1,2,3,4,5,6.  In the above image, you can keep counting down from the orange pixel at n=5 and see all the primes as white pixels, with 31 at the very bottom.

Give me one of everything

One surprise to me was row 6 (just below the topmost orange pixel).  It has a solid dark gray line extending all the way across.  That means that the five values of a: 1,2,3,4,5 in the equation a^5 (mod 6) produced... the values 1,2,3,4,5!  (Try it: 2^5=32, mod 6=2.  3^5=243, mod 6=3.)

And you can see that lots of other numbers have this behavior: 10, 14, (but not 18!), 22, 26, 30 and so on.

I need a bigger tree

Here's how the image looks if we keep going all the way to 100: