Laboratory of Mathematical Logic at PDMI

Cреда, 31 мая, комната 412. Начало в 14:00.

Докладчик: В. Баргачев.

TITLE: OVERVIEW OF PROBABILISTIC PRIMALITY TESTS, ESPECIALLY THE "VERY STRONG PRIMARILITY TEST" BY WILLIAM ADAMS AND DANIEL SHANKS.
There is no known "good" deterministic algorithm for deciding if the given number p is prime. "Good" means algorithm whose running time is bounded by polynomial of log(p). however, there are some "probabilistic" algorithms: they can decide whether given number is composite or prime with probability (1-a). It is a rather convenient form since after running such an algorithm n times, we obtain either p is composite or p is prime with probability (1-a^n).
Well known are euler test with a=1/2, and Miller-Rabin's test with a=1/4. adams and shanks introduced a test for which most probably a=1/216 -- this will be the focus of our talk.