Christopher Monico, a University of Notre Dame post-doctoral mathematics researcher, solved a math problem on Oct. 15.p. That a mathematics post-doc answered a problem may not seem noteworthy, except that this was the most difficult elliptic curve discrete logarithm (ECDLP) ever computed— and arguably the toughest math computation in history.p. Cracking the hardest ECDLP may not seem noteworthy, either, but it actually has significant application to most of our lives. ECDLP is the basis for a powerful cryptosystem, which is a technology used to secure electronic communications and commerce on the Internet, in wireless applications such as phones, and on hand-held organizers.p. Monico solved the problem in response to the “ECCp-109 Challenge” issued by the Toronto security firm Certicom. The company wanted to encourage researchers to test the security of ECDLP, which is the basis for its cryptosystem.p. Monico had a lot of help in solving the problem because he employed “distributed computing,” an innovative technique that uses the collective processing power of idle computers to take on complex mathematical calculations.p. “If you are using your PC for word processing, for example, you’re using maybe 5 percent of the unit’s computing power,” Monico said. “We make use of the CPU cycles you’re not using.” Distributed computing is being used for everything from the search for extraterrestrial intelligence to the design of new therapeutic drugs.p. Monico developed a computer program to perform the computations on thousands of distributed PCs. The solution took 549 days and involved 10,308 members and 247 teams. The home page Monico created for the project was accessed more than 235,000 times.p. On the surface, it would seem that Certicom would be dismayed that its challenge has been met and Monico will be walking away with its $10,000 challenge prize. Yet, nothing could be further from the truth.p. Monico points out that the encryption standard Certicom actually uses is many orders of magnitude stronger than the problem he solved. For example, the “109” in the challenge’s title refers to the prime that was used in solving the problem – a 109-bit integer. A problem using a 192-bit integer would be 2,000,000,000,000 times harder to solve.p. Monico earned a bachelor of science degree in mathematics, with a minor in computer science, from Monmouth College. He completed one year of graduate work in mathematics at Notre Dame before moving to New Jersey to work for Ilex Systems doing systems analysis, programming, and maintenance on real-time embedded systems. He returned to Notre Dame in 1998 and completed his doctorate last May.p. Monico is completing post-doctoral research under the direction of Joachim Rosenthal, a professor of mathematics and concurrent professor of electrical engineering. He doesn’t plan on tackling Certicom’s next challenge, called ECC2-109, but he’s willing to share his source codes with any takers.p. For those of you who might want to tackle the problem Monico solved, here’s what you’ll need to get started: the challenge consisted of two points P and Q in the same simple-subgroup of a particular elliptic curve. This is the value of k such that Q= kP.p. After you contact a few thousand friends and borrow their unused CPUs for more than a year, the answer you should come up with is:p. k=ddd09fd44accb22abbebc0917c. p. Unless, of course, you’re using base-10, in which case the solution is:p. k=28118384031601949668207954530684.
TopicID: 2713