Analysis on Implementation and its further improvements of AKS class algorithms
IR@C-MMACS: CSIR-Centre for Mathematical Modelling and Computer Simulation, Bangalore
View Archive Info| Field | Value | |
| Title |
Analysis on Implementation and its further improvements of AKS class algorithms
|
|
| Creator |
Patra, G K
|
|
| Subject |
Cryptography & Cryptanalysis
|
|
| Description |
The present work has been carried out at CSIR Centre for Mathematical Modeling and
Computer Simulation (C-MMACS). The paper deals with the implementation of AKS
class primality tests and various issues relating to it. AKS algorithm is the first
deterministic polynomial time primality test named after its authors Manindra Agarwal,
Neeraj Kayal and Ntin Saxena. A primality-testing algorithm is one that checks whether a
given number is prime or not.
“Deterministic” means that operations carried out by the algorithm are determined
entirely by (1) the algorithm (2) the input. In particular the algorithm does not make any
2
random choices. “Polynomial time” means that there is some polynomial p such that, for
every input n, the algorithm takes at most p (length of n) steps.
This algorithm is presented in the paper “ Primes in P” [4] and since then many efforts
are being made to implement the same. In this paper we have implemented the AKS
algorithm and have provided the complexity at each step of the algorithm. We have
explored new and efficient methods for this implementation. Most of our efforts have
been focussed on speeding up the time consuming congruence loop. We have further
provided some observations on the implementation, which can be used to speedup the
primality test. Though this work deals with the basic AKS algorithm but some of the
methods suggested could also be used in various algorithm of the same class now called
the “cyclotomic AKS class”.
|
|
| Publisher |
CSIR Centre for Mathematical Modelling and Computer Simulation
|
|
| Date |
2003-08
|
|
| Type |
Monograph
NonPeerReviewed |
|
| Format |
application/pdf
|
|
| Identifier |
http://cir.cmmacs.ernet.in/203/1/rrcm0307.pdf
Patra, G K (2003) Analysis on Implementation and its further improvements of AKS class algorithms. Technical Report. CSIR Centre for Mathematical Modelling and Computer Simulation, C-MMACS,Bangalore 560037,India. (Unpublished) |
|
| Relation |
http://cir.cmmacs.ernet.in/203/
|
|