1. crypto thought crackme #4

Continued fractions of the square roots of non-square integers are periodic. The period itself is a palindrome followed by twice the first term:

sqrt(5) = [2; 2,4, 2,4, 2,4,...]
sqrt(13) = [3; 1,1,1,1,6, 1,1,1,1,6, ...]
sqrt(29) = [5; 2,1,1,2,10, 2,1,1,2,10, ...]
sqrt(31) = [5; 1,1,3,5,3,1,1,10, 1,1,3,5,3,1,1,10, ...]

See http://mathworld.wolfram.com/ContinuedFraction.html for more details about continued fractions.

This proggy uses that fact to check serial numbers. The code takes an integer and verifies that the continued fraction representation of its square root matches the following checks:

Each term in the continued fraction except the first and last must be a number between 1 and 27, where 27 indicates a space, and 1-26 are A-Z. The first five are CACCG, while the last five are (of course) GCCAC. The middle ones encode the username forwards and backwards.

For example,

sqrt(serial) =
[(x); C,A,C,C,G,M,I,K,E,E,K,I,M,G,C,C,A,C,(2*x), ...]

In order to win this one, you've got to post a serial with your handle in it.

Easy question: Why CACCG?

2. Two words.... yay Mathematica!

Serial for Kythen = 1375676437308924001678248151500557858
ContinuedFraction = [1172892338328170682; 3, 1, 3, 3, 7, 11, 25, 20, 8, 5, 14, 14, 5, 8, 20, 25, 11, 7, 3, 3, 1, 3, 2345784676656341364, ...]

BTW... mike, the serial for your nick is 20285330574668271999128210 and the Continued Fraction is [4503923908623; 3, 1, 3, 3, 7, 13, 9, 11, 5, 5, 11, 9, 13, 7, 3, 3, 1, 3, 9007847817246, ...]

Thanks to a couple of my math professors for their book/course on number theory!

3. What functions did you use? Did you bruteforce something, or solve it explicitly in Mma.?

4. Well, I originally tried bruteforcing with FromContinuedFraction[], but of course that wasn't very efficient or necessary. What I ended up doing was plugging in x and 2x and solving for what the serial must look like. Of course, it always ends up being a quadratic formula. Now, you figure out a value for x that will make this quadratic formula result in a integer. The second degree coefficient appears to always be 1, so it ends up reducing the problem to finding an x value that will make the (Bx + C) component of the quadratic formula an integer. Most, if not all of the time, B and C will be fractions with the same denominator. Let the numerator of B be r, the numerator of C be s, and the denominator be t. Solve the linear congruence rx = -s mod t to find the value of x. Plug this x back into the quadratic formula to get the serial.

I didn't write the functions I used to do this. My number theory book included a Mathematica package that has a function to find the form of N given the continued fraction of sqrt(N).

5. Cool! I wasn't aware you could solve it that way, though it makes sense now. You might like to look at the paper I got the idea from. It's by J McLaughlin, multivariate polynomial solutions to pell's equation. Google search on "polypel2c" to find it. It gives a closed form solution (I suspect it's the one your book used). It also shows that there are patterns which can't occur.

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•