[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.


>
>  Is the uni approved calculator meant to be able to do this, mine
> doesnt seem to have a (mod n) button..? If not can someone remind be
> of the relevant discrete math one needs in order to evaluate that
> expression by hand?
>
> Thanks,
> Tim
>
>
> _______________________________________________
> CST-2 mailing list
> CST-2@srcf.ucam.org
> http://www.srcf.ucam.org/mailman/listinfo/cst-2
>

--
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.