Cayley–Purser algorithm: Difference between revisions

Revision as of 19:29, 17 November 2008

Revision as of 21:11, 1 February 2009

Line 69:

Recovering the private key <math>\chi</math> from <math>\gamma</math> is computationally infeasible, at least as hard as finding square roots mod ''n'' (see [[quadratic residue]]). It could be recovered from <math>\alpha</math> and <math>\beta</math> if the system <math>\chi\beta = \alpha^{-1}\chi</math> could be solved, but the number of solutions to this system is large as long as elements in the group have a large order, which can be guaranteed for almost every element.

However, the system wascan be broken when a method forby finding a multiple <math>\chi'</math> of <math>\chi</math> using the public parameters by solving the congruence:

:<math>\delta\left(\beta_{11}^{-1} - \alpha_{11}\right) \equiv \epsilon \pmod n</math>