BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Cryptanalysis with SAT - a propositional programming environment -
  Mateusz Srebrny
DTSTART:20070814T120000Z
DTEND:20070814T130000Z
UID:TALK7762@talks.cam.ac.uk
CONTACT:Thomas Tuerk
DESCRIPTION:In this talk\, a polynomial time translation of integer factor
 ization and the cryptographic hash functions MD5 and SHA-1 into propositio
 nal formulas will be presented and discussed\, along with some interesting
  experimental\nresults obtained with the use of the current best SAT solve
 rs. Those computational problems can also serve as benchmark for various S
 AT solvers.\n\nPropositional satisfiability\, SAT\, is one of the best kno
 wn NP-complete problems. There is no feasible algorithm known for testing 
 satisfiability of the propositional formulas in general. Nevertheless\, th
 ere are algorithms (implemented by so-called SAT solvers\, or SAT checkers
 ) that turn out to be feasible and very efficient on many instances of pro
 positional formulas.\n\nOn the other hand\, no one knows any polynomial ru
 n-time solving algorithm for the problem of integer factorization. The fam
 ous and challenging cryptosystem RSA was built on the problem in 1977 and 
 has been widely applied since then.
LOCATION:Computer Laboratory\, William Gates Building\, Room SS03
END:VEVENT
END:VCALENDAR