WolframAlpha cannot calculate A*inv(A) correctly.

Calculating A*inv(A) results in clearly the identity matrix. However, WolframAlpha cannot get this right.
This is what I got from them:

A*inv(A)

The result can be previewed here:

Obviously, WolframAlpha should try harder to make sure their result is correct before they put ADs on their page. They might be interested in Pepper and Ginger, or the more general area of Verifiable computation.

Update: Their customer service team replies super fast. I guess it’ll be fixed soon.

Generate cyclic group of prime order and one of its generator

In cryptography, the follow sentence appears very common: “Let G be cyclic group of Prime order q and with a generator g.” This is the first step in many encryption/signature scheme such as ElGamal encryption.
But how is this accomplished exactly? It turns out that this problem is not that trivial. Some research finds the following commonly used method.

Zp*={1,2,…,p-1} is known to be a cyclic group of order p-1 if p is a prime number. When p=2q+1 where q is also a prime number, p is said to be a safe prime number. q is very interesting here because p-1=2q means that any subgroup of Zp* can only have order 2 or order q.. Moreover, they are all cyclic groups. Let’s call the subgroup of order q Gq. This is the group we are interested in (cyclic group of prime order q).

Now we need to find one of its generator. If we find an element of order q in Zp*, is it a generator of Gq? The answer is yes. For any element, the order of the element can only be 2,q or p-1. If an element g is of order q, it follows from definition of cyclic group that Gq=. Actually, any element other than the identity in Gq is a generator.

Now we have sketched the outline of an algorithm to generate a cyclic group Gq of prime order q with generator g.

1. Generate random prime q until p=2q+1 is also a prime.
2. Randomly generate an integer 2<=g<=p-1.
3. If g^2 = 1 mod p, goto 2
4. If g^q != 1 mod p, goto 2.
5. Output p,q,g.

I implemented this algorithm in Golang, you can easily port the code into other programming language if you are interested.

package main
import (
    "crypto/rand"
    "math/big"
)

func gen(n int) (*big.Int, *big.Int, *big.Int) {
    for {
        q, err := rand.Prime(rand.Reader, n - 1)
        if err != nil {
            panic(err.Error())
        }
        n := new(big.Int).Mul(q, big.NewInt(2))
        p := new(big.Int).Add(n, big.NewInt(1))
        // p = 2q + 1, order(p)=n=2q
        if p.ProbablyPrime(40) {
            for {
                a, err := rand.Int(rand.Reader, p)
                if err != nil {
                    panic(err.Error())
                }                                                                         
                if b := new(big.Int).Exp(a, big.NewInt(2), p); b.Cmp(big.NewInt(1)) == 0 {
                    continue
                }
                if b := new(big.Int).Exp(a, q, p); b.Cmp(big.NewInt(1)) == 0 {
                    return p, q, a
                }
            }
        }
    }
    return nil, nil, nil
}
func main() {
    p, q, g := gen(1024)
    fmt.Println(p)
    fmt.Println(q)
    fmt.Println(g)
}

Running the above code can generate p,q,g of 1024 bits. Note that if there is not enough randomness on your computer, the above code can take a long time (10 minutes or longer). One way to increase randomness on a linux computer is to use the keyboard, mouse and send/receive network packages.

Go lang “http: invalid Read on closed request Body”

When using Go to write a simple HTTP web server, you might encounter this annoying error “http: invalid Read on closed request Body” with even extremely teeny-tiny web server logic. For example, the following code snippets do nothing but write a greeting “hello, ” as response when you submit the form:
index.html:

<form action="/submit" method="POST">
    <input type="text" name="yourname" />
    <input type="submit" value="Say hello!" />
</form>

httpserver.go

package main
import(
    "fmt"
    "net/http"
)
func handler(w http.ResponseWriter, r *http.Request) {
    fmt.Fprintf(w, "hello,")
    r.ParseForm()
    fmt.Fprintf(w, r.FormValue("yourname"))
}
func main() {
    http.HandleFunc("/submit", handler)
    http.Handle("/", http.FileServer(http.Dir("./")))
    http.ListenAndServe(":8080", nil)
}

The above code compiles with ease with “go build”. Then you can run it with “./httpserver” in linux. After it starts, you should be able to visit http://localhost:8080 and see a form like this:
Say hello form
The server logic will parse the form and write “hello, ” as response. But when you type in your name and click “say hello”, you see only “hello, “. It seems that nothing in the form is ever sent to the server side. Strange enough, huh?

However, the solution is pretty simple. You only need to make sure you call ParseForm() before writing anything to the ResponseWriter. The reason is once you write anything in the response, the request body will be closed which prevents you from reading anything from it. Looking into the reason on this will be talked about in a future post.

Though the problem is simple, I spent about half an hour to find this problem. The correct code is:

func handler(w http.ResponseWriter, r *http.Request) {
    fmt.Fprintf(w, "hello,")
    r.ParseForm()
    fmt.Fprintf(w, r.FormValue("yourname"))
}

The lesson learnt here is that if I tried to catch errors returned by r.ParseForm() I could have saved the half an hour. It’s a very good habit to write code to catch and handle all errors which is one of Golang’s design choice.

if err := foo(); err != nil {
    fmt.Println(err.Error())
}

Meeting with Roger Dingledine

I got a chance to meet with Roger Dingledine for a one-on-one meeting today.

In the meeting, we discussed that it is possible to make Tor faster and more robust separately. To make it faster, it’s mostly about scheduling Tor packages more wisely among all nodes in the Tor network. To make it more robust, the basic technique is to make Tor packages just look like normal HTTP packages.

However, the challenge here is how to build a Tor that is fast and robust against blockage/censorship which is still an open question right now. I’ll look more into it.

Good luck.

Remove the three annoying confirmations when replying emails in Mutt

I am new to Mutt. It’s an awesome text-based email client which carries all features I want  - configurable text editor, shortcut key binding, thread-folding, multiple-inbox support, imap support, quote text in reply – to name a few.

But one annoyance I found was that when I tried to reply an email. Mutt first asks me to confirm the address to reply to. Then it asks me confirm the subject of my reply. Lastly, it asks me if I want to include the original emails as quoted text in my reply. Too often, all answers to the three confirmation are “yes” which consumes three “Enter” key strokes. It will be very nice if I can avoid this 99% of the times and only change them when necessary.

After a thorough research on the manual, I found the solution to this annoyance. Put the following two lines in your .muttrc will completely remove them.

set fast_reply=yes
set include=yes

fast_reply=yes turns off the first two confirmation. By default, it replies to the sender’s email address. include=yes tells Mutt to always include original message as quoted text in your reply. If you don’t want this, set include=no.

If you want to occasionally change the reply-to address, after you compose your reply, press “t” (default-binding) to change it. If you want to change the subject (which is usually “Re:<original subject>”, press “s” (default-binding) to change it. For quoted text, if by default they are included and you use Vim as your editor, you can press “ggdG” in a row to remove them in your editor.

Go Programming Language Syntax Highlighter Brush

This is a syntax highlighter brush of Go Programming Language (Golang) for SyntaxHighlighter.

I was pretty amazed that there wasn’t one syntax brush for Go when I checked this collection of available syntax brushes. And it seems that nobody has made one yet. So I started to write it myself. It is not hard at all. All I need to do is to write several regular expressions.

You can download the brush here. Together with WP-SyntaxHighlighter, you can post Golang code in your WordPress blog post as I do here.
Here is one example of highlighted Golang code snippets:

package main

import (
    "fmt"
)

func main() {
    fmt.Println("Hello, world!")
}

Toggle between source file and test file in vim

Do you often switch between source file and test file while you code?
Usually source file and test file are named as source.xxx and source_test.xxx/sourceTest.xxx where xxx is language specific (e.g x=c, cpp, java, etc.).
You are writing foo_test.c and want to take a look at the source file foo.c to make sure you put the expected results in the test case correctly. What do you do?
With key mapping in VIM, you can do this with two keystrokes.
I put these two lines in my .vimrc file.

nnoremap ,t :e %:r:s?_test??_test.%:e <CR>
nnoremap ,s :e %:r:s?_test??.%:e <CR>

Now let me explain how it works. For the following discussion, we assume that the current file is foo/bar.c (or foo/bar_test.c in case of test file)

% is the current file name (i.e. foo/bar.c)
:r is root of the current file name with the last extension removed (i.e. foo/bar)
:s?pattern?sub? substitutes the first occurrence of pattern with sub. (i.e. %:r:s?_test?? returns foo/bar for sure no matter whether the file you are editing is foo/bar.c or foo/bar_test.c)
:e is the extension of the file. (i.e. .c in this case)

Together, %:r:s?_test??_test.%:e converts foo/bar.c and foo/bar_test.c to foo/bar_test.c.
And :e %:r:s?_test??.%:e converts foo/bar.c and foo/bar_test.c to foo/bar.c.
I mapped them to ,t (for test file) and ,s (for source file) respectively.

In case you name your source file and test file as source.xxx and sourceTest.xxx, (e.g. for java code) please use these two lines in your .vimrc.

nnoremap ,t :e %:r:s?Test??Test.%:e <CR>
nnoremap ,s :e %:r:s?Test??.%:e <CR>

Now you can type ,t (comma followed by t) to go to test file and ,s (comma followed by s) to go to source file.
Enjoy!

Watching a folder for new files on Mac OS X

One feature I was longing for from an OS was an automatically classified folder in which files are grouped automatically by their types (which can largely be determined from its extension).
There are several ways to implement this feature.
Considering that most new files comes from downloads in your browser, a browser extension/plugin might suffice. For example, if you are using Firefox, there is one such extension called Automatic Save Folder. But if you are a Chrome user, as I do, you are out of luck because an alternative for Chrome is not available because Google doesn’t provide the API needed to develop such an extension.

Another way of doing this is to use some commercial software such as Hazel. It’s pretty good. But it’s not free.

The last way I am going to talk about today is to do it yourself. The tool we are going to leverage is launchd. launchd is used to manage daemons running in the background of your OS. Each daemon is defined with a plist file. One feature is that you can define a folder to watch in the plist file and set which command to execute when new files appear in that folder.

<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">
<plist version="1.0">
<dict>
    <key>Label</key>
    <string>com.zuochengren.fsort</string>
    <key>ProgramArguments</key>
    <array>
        <string>/Users/me/bin/fsort</string>
    </array>
    <key>WatchPaths</key>
    <array>
        <string>/Users/me/Downloads</string>
    </array>
    <key>RunAtLoad</key>
    <true/>
</dict>
</plist>

For example, the above plist file defines a daemon to watch my download folder at /Users/me/Downloads and when new file appears, call a script at /Users/me/bin/fsort.
The Label should be a unique string to identify the daemon. The first parameter of ProgramArguments is always the name of the script/executable, and you can pass other parameters one by one in the ProgramArguments list.
The script fsort can do anything you want to do such as move files to different folders and delete files that is older than 30 days.
For example, this is my fsort script (simple but works pretty good given all the folders exist):

#! /bin/bash
mv /Users/ren/Downloads/*.torrent /Users/ren/Downloads/torrent/
mv /Users/ren/Downloads/*.dmg /Users/ren/Downloads/installer/
mv /Users/ren/Downloads/*.{tar.gz,zip,rar} /Users/ren/Downloads/archive/
mv /Users/ren/Downloads/*.{jpeg,jpg,png} /Users/ren/Downloads/image/

Make sure to use absolute path (both in the plist definition file and fsort script) and make the script executable.

Google Hotel Finder finds me a wrong hotel!

My girlfriend and I drove back from Mountain View California to Austin Texas two weeks ago.
We planed to stop in El Paso for one night. So, we tried to book a hotel in El Paso TX USA.
I searched for El Paso hotels in Google Search and the first result was www.google.com/hotelfinder (which is great!)
search-results Then I found and booked one really cheap Holiday Inn.
cheap-holiday-inn

But later, when we tried to navigate to the hotel, we found out that the hotel was in Mexico…
The reservation was nonrefundable which I noticed when I booked it.
So we contacted Expedia immediately to see if there was anything they could do to help.
Unfortunately they could do nothing but help us book another hotel at our own cost.

The result was that we gave up entering Mexico and drove overnight all the way to Austin. When I arrived in Austin, I tried to investigate more on this problem.

  • First of all, the fundamental problem was my carelessness.
  • Secondly, on hotel finder, no address of the hotel was listed on a prominent location. I have to scroll down the description and the address was at the very bottom of the page. (Interestingly, the landing page on Expedia didn’t show the address in an obvious location either.)
  • Thirdly, hotel finder shouldn’t list the hotel in the result in the first place. I tried to do the same search on Expedia, this hotel was not listed in the result, which prevented this tragedy from its origin.

In all, I believe that there are improvements for Hotel Finder to make. I’ve submitted my feedback to this Google product and am now waiting for their update.

Update: It’s now 6 weeks later (Oct 11 2012), the problem is still there.

Some notes on goroutine and channel in Go programming language

Goroutines and channels are easy to use to implement simple multi-threading tasks in Go programming language.
However, there are some mistakes a novice is easy to make.
For example, the following program demonstrates how to implement producer and consumer problem in go language.

package main 
import "fmt"
var queue chan int
func produce() { 
    for { 
        queue <-1 
    }
}
func consume() { 
    for { 
        product := <-queue 
        fmt.Println(product) 
    }
}
func main() { 
    queue = make(chan int) 
    go produce() 
    go consume()
}

But when you try it out, you get nothing outputted.
The problem is that the main thread ends before any go routine actually takes place.
In order to fix, it we should ask the main thread to block and wait for other thread to run.
Then we change the main function to

func main() { 
    queue = make(chan int) 
    go produce() 
    go consume() 
    for{} 
}

However, this time again, nothing is outputted.
That is because the main thread occupies every time slot of CPU and no goroutine can get a chance to be scheduled.
So, the correct way to wait is to use select clause.
So we change the main function to:

func main() { 
    queue = make(chan int) 
    go produce() 
    go consume() 
    select{} 
}

This time, it’s correct.
But I want to mention one more thing.  Actually, if we remove the initialization of queue, the code can still compile and run without panic.
However it will not produce any output because the channel is a null channel. This can be very annoying because it is very difficult to realize this is the real cause of some unexpected behavior.I have just experienced such a painful debugging experience. Hope this helps.