ZenithSearchPrimary MenuSkip to contentSearch for:Computer ScienceWolframAlpha cannot calculate A*inv(A) correctly.November 20, 2012 Awaken2 CommentsCalculating 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.Verifiable computationWolframAlphaComputer ScienceGenerate cyclic group of prime order and one of its generatorNovember 17, 2012 Awaken12 CommentsIn 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 2Golang, you can easily port the code into other programming language if you are interested.package mainimport ("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=2qif 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