D.12.1 aksaka_lib

Library:

aksaka.lib

Purpose:

Procedures for primality testing after Agrawal, Saxena, Kayal

Authors:

Christoph Mang

Overview:

Algorithms for primality testing in polynomial time based on the ideas of Agrawal, Saxena and Kayal.

Procedures:

D.12.1.1 fastExpt		a^m for numbers a,m; if a^k>n n+1 is returned
D.12.1.2 log2		logarithm to basis 2 of n
D.12.1.3 PerfectPowerTest		checks if there are a,b>1, so that a^b=n
D.12.1.4 wurzel		square root of number r
D.12.1.5 euler		phi-function of Euler
D.12.1.6 coeffmod		polynomial f modulo number n (coefficients mod n)
D.12.1.7 powerpolyX		(polynomial a)^q modulo (poly r,number n)
D.12.1.8 ask		ASK-Algorithm; deterministic Primality test