[CST-2] advanced algorithms 1996/9/6 (fwd)

[Matej Pfajfar]

> > a^(n-1) (mod n) for n=65, a=1,2,8,12
> Arrange for n-1 to be 2^k * v for some odd v. In this case,
> k=6, v = 1.
> Compute a^v -> easy.
> Then just square k times and you get for a=12, a^(n-1)=1.

Another point - all this is not necessary if n is prime.
THen you know the result is 1 by Fermat.
hth,
Mat
--
Matej Pfajfar
St John's College, University of Cambridge, UK

GPG Public Keys @ http://matejpfajfar.co.uk/keys
WARNING: THIS E-MAIL ACCOUNT WILL BE DELETED ON
         15/07/2002. PLEASE USE mp@cantab.net.