Jason Worth Martin
Assistant Professor of Mathematics

Department of Mathematics and Statistics
113 Roop Hall
MSC 1911
James Madison University
Harrisonburg, Virginia 22807

Voice: (540) 568-5101
Fax: (540) 568-6857
Email: martinjw@jmu.edu

If you need to send me an encrypted message, please use my GPG public key. The key's fingerprint is:

37EE A97A 15E7 5ACB 4B1E A47E CF8C 1250 0561 FA7A

Of course, anyone who could hack this web server could replace both the key and finger print, so if you're really paranoid you can call me to confirm the key finger print.

Teaching (Fall 2008)

Course Add/Drop/Override/etc.

I have no power to do anything related to course registration. If you cannot accomplish what you need via e-campus, then you should see Brenda Wilkinson in person in her office in Roop 308. Due to the large number of students that Ms. Wilkinson needs to assist, and in order to be fair to all of them, Ms. Wilkinson can only assist students in person. Please do not call or email her about course registration issues (that's like trying to sneak to the front of the line).

My Fall 2008 Courses

CS/Math 227: Discrete Math

Math 430: Abstract Algebra

Office Hours

Day of Week Time
Mon. 10:00am-Noon
Wed. 7:00am-8:00am
10:00am-Noon



Research

Cryptographic Hashing

A cryptographic hashing algorithm is a method for reducing digital data down to a small string of bits which we call the "hash" of the data. A hash is often referred to as a "message digest" or a "digital fingerprint" because the chance of two different messages (even if they only differ by a tiny bit) producing the same hash should be so small as to be inconsequential. Since the early 1990s, the U.S. Federal standard for cryptographic hashing has been a collection of algorithms referred to as SHA. However, in 2005 Chinese cryptographers Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu demonstrated a serious weakness in SHA-1. This led the National Institute of Standards and Technology to hold a competition to determine a new Federal standard.

My submission to the NIST competition is called ESSENCE. Here is the full NIST Submission for ESSENCE. A description of the submission contents is available in this README file.

  • ESSENCE is a hybrid design using both the traditional Merkle-Damgard construction and Merkle hashing trees. The tree structure allows ESSENCE to use parallel computations to take advantage of multiple cores available on modern processors. Here is the technical specification for ESSENCE, which describes everything except the compression functions.

  • The ESSENCE compression functions have been designed to have high instruction-level parallelism which allows them to take advantage of the large SIMD registers in modern processors. Here is the technical specification for the ESSENCE compression functions.

  • The ESSENCE compression functions are constructed from non-linear feedback shift registers run in parallel with linear combining. The entire construction uses only the bitwise operations AND, XOR, NOT, and SHIFT.

  • The compression function does not require lookup tables, but the linear portion can be accelerated by using pre-computed tables. Using lookup tables can make an implementation vulnerable to cache-timing attacks, but in situations where the hashing algorithm will not be hashing secret data the lookup tables provide a 300% speedup.

  • On a quad-core Intel Xeon based Linux server, using hand-tuned assembly code and OpenMP parallel C, ESSENCE can hash at better than 12.1 cpu cycles per byte. Systems with more cpu cores should see even better performance.

  • I have fixed several typographical and expository errors that were in the original NIST submission. None of the corrections affect the algorithm. The on-line versions listed here are the most current versions. To see an explicit list of all changes, please view this errata.

    Number Theory

    I received my PhD in August, 2006 under the direction of Ravi Ramakrishna. For my dissertation, I found new upper bounds on Martinet Constants which describe how we expect discriminants to grow in number fields. For a PDF-slide show that describes the results, click here.

    I'm also developing a library to do linear algebra over exact rings (for example, computing the Smith Normal Form of a matrix over a Dedekind Domain) on massively parallel systems. I'm starting with LinBox, and adding MPI calls to the dense linear algebra subroutines. Hopefully this will be useful to projects such as SAGE . If you are working on something similar or want to help, please let me know!

    Papers

    Improved Bounds for Discriminants of Number Fields (Submitted)


    GMP for Intel Core 2 (Intel64) Machines (Including Core 2 Mac OS X machines)

    Download Here

    GMP is the GNU Multi Precision Library. It is the heart of most computational number theory packages. The official GMP distribution is available at http://www.gmplib.org (Please send questions and bug reports about this patch to me. Please do not bother the GMP developers!)

    GMP is extremely high quality, modular, software (and it is released under the GNU LGPL), so I was able to create a patch that will allow it to run faster on Core 2 Macs. This patch also offers a significant speed up (about 30%), and this speed up works for Linux Core 2 machines as well. For details, download the tarball here.

    If you were looking for the GMP patch for AMD64 processors, such as the Athlon and Opteron, then check out Pierrick Gaudry's work. He has some very clever assembly code that I used as a starting point for the Core 2 patch.

    If you want to see a very nice exposition of how these routines work, see Eric Bainville's work.

    If you want to see the single best guide to optimizing assembly code, take a look at Agner Fog's work.

    Here are answers to some questions I've received:

    1. My installation script doesn't detect all Core 2 processors. (I should fix it, but Intel keeps changing the cpuid values). If you know that you have a Core 2 processor, then just copy in the relevant files by hand. See the readme file for details.
    2. Intel64 is Intel's new catch-all name for processors using the Core 2 micro-architecture. So, any CPU labeled Intel64 can use this patch.
    3. Newer model Xeon processors (such as those in the Mac Pro) are Core 2 chips. Older Xeons use a different micro-architecture and cannot use this patch.
    4. The "Intel Core 2 Duo" is a Core 2 processor. However, the "Intel Core Duo" is not. The patch will not work on "Core Duo" machines because those CPUs are only 32 bit processors.
    5. If your results in GMPbench don't seem to change, make sure that you are linking against the correct library! For example, RedHat has copies of the gmp libraries in /usr/lib64 which may be picked up before /usr/local/lib.
    6. By default, my code uses the lahf/sahf instructions. These instructions work on AMD64 and Intel64 processors. However, the Pentium4 and older Xeon processors do not support lahf/sahf. So, if you use my code to compile a binary on an Intel64 machine, don't expect that binary to run on a Pentium4. This is a deliberate choice because the lahf/sahf instructions provide the fastest method for saving the carry flag on Intel64 processors (other common methods such as conditional moves, bit tests, and add-with-carry can create a false dependency on the carry flag with nearby arithemetic operations thus adding latency to a critical loop). I am considering re-writing this section of code to eliminate the lahf/sahf instruction, but I don't want to sacrifice any speed.
    7. Yes, I have given my code to the GMP maintainers. However, don't expect my code in the official GMP release anytime soon for exactly the reason given above (the lahf/sahf instructions).