  Modern conflict-driven clause learning (CDCL) SAT solvers are very good in
solving conjunctive normal form (CNF) formulas. However, some application
problems involve lots of parity (xor) constraints which are not necessarily
efficiently handled if translated into CNF. This paper studies solving CNF
formulas augmented with xor-clauses in the DPLL(XOR) framework where a CDCL SAT
solver is coupled with a separate xor-reasoning module. New techniques for
analyzing xor-reasoning derivations are developed, allowing one to obtain
smaller CNF clausal explanations for xor-implied literals and also to derive
and learn new xor-clauses. It is proven that these new techniques allow very
short unsatisfiability proofs for some formulas whose CNF translations do not
have polynomial size resolution proofs, even when a very simple xor-reasoning
module capable only of unit propagation is applied. The efficiency of the
proposed techniques is evaluated on a set of challenging logical cryptanalysis
instances.
