From: "Nicolas J. Hammond" <njhm@ns.njh.com>
Date: Mon, 13 Jan 1997 09:02:04 -0800 (PST)
To: cypherpunks@toad.com
Subject: Re: RSA over Rubics cube?
In-Reply-To: <32D9D750.7053@europa.com>
Message-ID: <199701131721.MAA16352@ns.njh.com>
MIME-Version: 1.0
Content-Type: text/plain


Pass me another! wrote ...
> cypherpunks@toad.com wrote:
> > 
> > Just for fun, not that I am sugesting it as a serious encryption
> > method, but has anyone tried exponetion cyphers on the group
> > defined by the Rubics cube? :)
> 
> well....I guess you didn't want a reply to your real email address,
> considering you'd be flamed like a 'mother$##@*(%'.  anyways....Just so
> YOU know I figured out the infamous Rubik's cube when I was 9 years
> old...no solution book, nothing, and beat the world record(ooooo what an
> accomplishment).  I just figured it out...so if I was 9.........geee 
> what do you think?  I could sit down and give you the mathmatical<sp>
> computations...but I have better things to do.  I hope your just trying
> to have a better understanding of cryptography standards, and future
> methods.  Maybe reading some information on algorithms....that might
> help....maybe calc 101  or ignorant 111..or jeez...do you even know
> binary?
> 
> -spanky

Am impressed that you were able to do this aged 9, though 9-yrs-olds
have been known to win US regional championships (back in the early 80s).

The mathematics behind the Rubik's cube are fairly complex and involve
set theory. One of the easiest ways to solve the cube is to find
commutators such that A.B.A'.B' can affect a small group.
Choose A and B so that they intersect in that small group.
Solve the cube by solving a small area and then incrementally build on 
that area until you have your solution. You need 4 "moves" - one
to flip corners, one to move corners, one to flip edges and one to
move edges. They are relatively easy to find if you know what to look for.

There are two "world records" associated with the cube - one is the
fastest time to solve a cube, normally done in competitions, one
is the shortest algorithm in terms of number of moves.
The former makes great TV. Minh Thai of the US won the only
world competition I'm aware of. His average time was 23 seconds.
Problem with competitions is that occasionally you can solve
it very quickly because of the initially pattern and that is why
competitions use averages, typically of at least 3 different timings.
I assume this is your "I beat the world record" claim.
It is common for someone to occasionally solve a cube in under 30 seconds, 
it is almost impossible to get an average under about 25 seconds.

[The only exception is what magicians Paul Daniels (British will know of him)
and David Copperfield (Americans know of him) have done on their TV shows.
They take a cube in front of a studio audience, throw it up in the air
and it is solved by the time it comes down. No camera tricks involved.
Paul did his in a show around 1981-1982, I saw David's TV show around 1988
but it was a repeat so I don't know when it first aired.]

The other "world record", shortest number of moves, is of much more
interest to mathematicians. God's algorithm (the theoretically minimum
number of moves) is 18 (see article on "Magic Cubology", Scientific American,
either March 81 or July 82). In others words you can, in theory, generate any 
pattern (or the reverse, solve any pattern) in 18 moves. 
The shortest actual algorithm used to be 52 moves my
Morwen B. Thistlewaite of England (early 1980s) however I hear that the 
Dutch Cube Club got this down to below 35 (1992).

Getting closer to God's Algorithm is an interesting exercise in 
Set Theory and in solving puzzles. It has some relevance to Cryptography,
but not too much.
Difference is in the mathematical basis of the underlying algorithms.

-- 
Nicolas Hammond                                 NJH Security Consulting, Inc.
njh@njh.com                                     211 East Wesley Road
404 262 1633                                    Atlanta
404 812 1984 (Fax)                              GA 30305-3774