Design and Analysis of Algorithms

486 Design and Analysis of Algorithms

(1) modulo a polynomial of the form X

r

– 1 for an appropriately chosen small r. In other words, test if the

following equation is satisfi ed.

(X + a)

n

= X

n

+ a(mod X

r

– 1, n) (2)

From the Lemma it is immediate that all primes n satisfy the equation (2) for all values of a and r. The

problem now is that some composites n may also satisfy the equation for a few values of a and r (and indeed

they do). However, we can almost restore the characterization: we show that for appropriately chosen r if the

equation (2) is satisfi ed for several a’s then n must be a prime power. The number of a’s and the appropriate ...