Maths

I've been digging around some, and have failed to see this information demonstrated, at least not in a way that I could identify, so...

I propose the following:

For all p, p being a safe prime (with a corresponding Sophie Germain prime s,) implies that for all y in [2, p-1], y^s mod p is either 1 or p-1.

Furthermore, a discrete logarithm only exists under the following circumstances:

• 0^k = z mod p is only true for z = 0, with k in {1, 2, 3, ...}
  
• 1^k = z mod p is only true for z = 1, with k in {1, 2, 3, ...}
  
• (p-1)^k = z mod p is only true for z in {1, p-1}.
  (p-1)^k = p-1 mod p for all odd k values, and
  (p-1)^k = 1 mod p for all even k values.
  
• Otherwise, let y be in [2, p-2]:
  
  
  • if y^s = p-1 mod p:
    for all z in [1, p-1], there is some k such that y^k = z mod p.
    Let the set of all such y values be represented as Y.
    
  • if y^s = 1 mod p:
    y^k = z mod p has a solution k if and only if p - z is in Y.
    
  
  

I have managed to show that this is true for all safe primes under one thousand, I just need to figure out how to prove it for all safe primes. Hopefully there will be more to come here.

For a follow up, here's an interesting chart showing this information for the safe prime 11. The columns represent the y values, the rows represent the z values, and the numbers in the cells (if present) represent the k values. The relevant Sophie-Germain prime powers are highlighted in green.

A			5				5	5	5		1
9			6	2	3	4	4	8	2	1
8			3				7	9	1
7			7				3	1	9
6			9				1	7	3
5			4	3	2	1	6	2	8	4
4			2	4	1	3	8	6	4	2
3			8	1	4	2	2	4	6	3
2			1				9	3	7
1		1	A	5	5	5	A	A	A	5	2
0	1
	0	1	2	3	4	5	6	7	8	9	A

---

2007/11/08: Here's a similar chart for the safe primes 5 and 7:

4			2	2	1
3			3	1
2			1	3
1		1	4	4	2
0	1
	0	1	2	3	4

6				3		3	1
5				5		1
4			2	4	1	2
3				1		5
2			1	2	2	4
1		1	3	6	3	6	2
0	1
	0	1	2	3	4	5	6

Compare these against a non safe-prime (not even prime) base 12:

B												1
A											1
9				2						1
8			3						1
7								1
6							1
5						1
4			2		1				2		2
3				1
2			1
1		1				2		2				2
0	1						2
	0	1	2	3	4	5	6	7	8	9	A	B

---

I've written a program to show these tables, available here

I'm going to start solving all my problems with violence

My phone was working for the most part, but the memory card I got for it wasn't being recognized. The card worked in other phones (same make and model) and other memory cards also wouldn't work in my phone. Seems my phone was the problem. Then, on Friday, I stepped out onto my balcony to make a phone call, pulled out my phone, and flipped it open. Here, my toddler-like reflexes got the better of me and the phone went sailing off the balcony. I watched as it fell down seven floors, and hit a tree. It made a nice loud crack as it hit. Figuring I was fucked, I ran downstairs to collect the pieces, and found my phone sitting on the ground, seemingly unaware that it just fell a good 70 feet. Later on during the weekend I tried the memory card again, and it works fine. So from now on, when something or someone doesn't do what I want, I'm going to throw it, or them, off my balcony. Just a heads up.

Bad time to upgrade

Step 1: Get a new iPod, one of the latest-generation "iPod classic" ones.
Step 2: Realize that, while compatible with my iBook, it's not compatible with the OS I was running (10.3.something)
Step 3: Decide that, since I was planning on upgrading anyway, now would be a good time to do it.
Step 4: Go out and buy OS 10.4.
Step 5: Realize today that OS 10.5 is due to come out in a month, and is also compatible with my iBook.

I wonder if I'll be able to upgrade to OS 10.5 at a discount since my purchase of 10.4 was so recent. Google hasn't been much help on that end, so I guess it's "wait and see" for the time being.

Bored

I'm bored, so I'm going to bore you with some computer stuff...

When working in any programming language that supports C-style commenting (both /* */ and //), there is a simple way to have a large block of code that can easily be commented and uncommented. You start the comment block normally: /*, but you end the comment somewhat differently: //*/, with no code following on the line of the end-comment code. To un-comment the block of code, type another / before the opening /*, resulting in //*:

// Commented out:
/*
foo("bar");
...
//*/

// Not commented out:
//*
foo("bar");
...
//*/

Okay, back to work.

Stardust

So last night I saw Stardust: that new movie based on the novel by Neil Gaiman. The movie was excellent; on par with Pan's Labyrinth, with the added bonus of me not having to read subtitles or learn Spanish (which, really, I should learn anyway.) This post is not, however, going to be a review of the movie. Just go see it.

A little later that night, I was standing outside with my field of vision unintentionally pointing upwards, when I saw a meteor (more precisely, a fireball, boldie, or detonating fireball.) Now, I've seen meteors before: individual unexpected meteors, meteor showers I've decided to go outside and watch, I've even briefly owned a couple meteorites. This one was a vibrant green, a color I've seen before in meteors, and lasted a good two to three seconds. Towards the end of it's path it slowed down and disintegrated into several smaller chunks, some falling behind to make a short trail of meteors. One of the more impressive displays I've seen. I'd guess it's apparent magnitude was at least as bright as -5.

Statistical Linguistics + Music

A class I'm taking this semester on computational linguistics, which is a continuation of the one I took last semester, is covering statistical analysis of linguistics. The subject covers everything from calculating how often specific words occur by simply counting them and dividing by the total number of words, to automatically grouping words by grammatical class and determining simple rules of grammar, to determining the author of unknown works by comparing them to samples of works by known authors. It's not what I thought the field would be when I started taking the course, but it's extremely interesting (to me, at least.) I've been wondering what else you could do with this, and then it hit me.

What if, instead of words, letters, or sounds, you used musical notes. You could create, more or less, the same type of analysis for music as you can for language. Some applications could be interesting, like determining the composer of unknown works, but the same tools that allow you to describe language, or in this case music, allow you to go the other way: you can create random variations based on what you've seen and analyzed. I tried this a while ago with my blog, and while a lot of the text it produced is garbage (you need a ton of sample text to get consistently good English, and my blog isn't that large), there were a few gems. Like "Tim can confiscate your property if he wants to." I'm looking into what's necessary to do this with music. I have a ton of Scott Joplin sheet music that I could run the analysis on, create a model, then generate novel music from. Chances are a lot of it will be crap, but with a basic understanding of music theory I could add some assumptions on how music is structured that could improve the results.

The only thing holding me back is that, while I really want to do this, I would have to translate all the sheet music into something a program could understand, which will involve a ton of typing. I could also do it on waveforms taken from MP3s on my computer, but that'll add an extra layer to the problem: figuring out the notes from the sound, which seems trivial but is actually fairly hard, especially with all the distortion used in a lot of my music. Maybe if I stick around another 4 years after I get my linguistics degree and get a music degree it'll all come together.

If I pull my act together and do this, I'll post some MP3s. Just don't hold your breath.