hf3.mws

3. Házi feladat: 2004-02-25/26

1. Írjunk egy Exp nevű hatékony hatványozó programot, melyre Exp(a,n,m) = `mod`(a^n,m) , és az eljárás a négyzetreemelés és az -val való szorzás műveleteit használja. Adjunk egy rekurzív és egy iteratív megoldást is!

2. Írjunk egy prímtesztelő függvényt, mely a Solovay-Strassen-algoritmust használja, s amely az
 a^((n-1)/2) = `mod`(J(a,n),n)
kongruencia ellenőrzésével eldönti egy pozitív n egészről, hogy prím-e. A függvény hívása PrimTeszt(n,epsilon) , ahol annak valószínűsége, hogy a függvény prímnek találja az n számot, de az mégis összetett kisebb, mint epsilon . Az a véletlen számot ellenőrizni kell, hogy relatív prím-e az n -hez. Az algoritmushoz írjuk meg a Jacobi-jelet kiszámoló rutint is, mely a
J(1,n) = 1 , J(a,n) = J(a/2,n)*(-1)^((n^2-1)/8) , J(a,n) = J(`mod`(n,a),a)*(-1)^((a-1)*(n-1)/4)
képleteket használja.