[HGI-News] Vortragsankündigung 29.1.04 - Pseudopowers and Cryptography

[hgi-news at lists.ruhr-uni-bochum.de]

--------------------------- Ankündigung ---------------------------

Frau Dr. Siguna Müller (University Calgary, Canada) wird
am Donnerstag, den 29. Januar 2004, zwischen 14 und 15 Uhr
in Raum NA 02/257 vortragen.

************************************************************************
***

Pseudopowers and Cryptography

The recent ideas of Agrawal, Kayal, and Saxena have produced a milestone
in the area of deterministic primality testing. Unfortunately, their
method, as well as their successors are mainly of theoretical interest,
as they are much too slow for practical applications.

Via a totally different approach, Williams et al. Have developed a test
which is conjectured to prove the primality of $N$ in time only
$(\lg N)^{3+o(1)}$.
Their (plausible) conjecture concerns the distribution of pseudosquares.
These are numbers which locally behave like a perfect square but are
nevertheless not a perfect square.

While not completely explored yet, this new theory involving the
pseudosquares allow a number of interesting applications in
cryptography.

Altough squares are much easier to deal with, this naturally gives rise
to the question if the pseudosquares can be replaced by more general
types of
numbers.
We have succeeded in extending the theory to the cubic case. To capture
pseudocubes we rely on interesting properties of elements in the ring of
Eisenstein integers and suitable applications of cubic residuacity.
Surprisingly, the test itself is very simple as it can be formulated in
the
integers only. Moreover, the new theory suggests to lead to an even more

powerful primality testing algorithm than the one based on the
pseudosquares.

Joint work with H.C. Williams (Calgary, CA), and P. Berrizbeitia
(Caracas, VE)

************************************************************************
***