NAME: SATYAM PANDEY

REGISTRATION NUMBER: 2025RMA13

TUTORIAL
TOPIC:
[Link] and analyze the AKS algorithm pseudo
code and its complexity. Justify why it is not
usable.
[Link] the factorization methods viz., Pollard
p-1, Pollard rho, Number Field Sieve and
Quadratic Sieve methods and their time
complexities.
[Link] and analyze Attacks on RSA and OAEP
Protocol
[Link] and analyze other SHA versions viz.,
SHA-1, SHA-224, SHA-256 and SHA-384.
[Link] the security attacks on digital
signature schemes

1: Explore and analyze the AKS algorithm

pseudo code and its complexity. Justify why
it is not usable
1. What is the AKS Algorithm?
The AKS primality test (Agrawal–Kayal–Saxena,
2002) is the first algorithm that:
 Always gives the correct answer
(deterministic)
 Works for all integers n(general)
 Runs in polynomial time in log n (i.e., in the
size of the input)
So, it proved the famous result:
PRIMES is in P (deciding whether a number is
prime can be done in polynomial time).
However, even though it is polynomial time, it is
not usable in practice because the polynomial
is of very high degree and constants are huge
compared to fast probabilistic tests like Miller–
Rabin.

2. High–Level Idea of AKS

AKS is based on a polynomial identity that holds
for primes:
For a prime number p:
¿

for all integers a. This comes from the binomial

theorem:
¿, and modulo a prime p, all middle binomial
coefficients ( p )for 0< k < pare multiples of p, so they
k
vanish mod p.
For composite n, this polynomial identity fails for
many choices of a.
AKS modifies this idea:
 It does not check the identity for all
polynomials or all a.
 It checks the identity only modulo a
cleverly chosen polynomial X −1and only r

for small values of a.

 If the identity holds for all those cases, it
proves nis prime.

3. Pseudocode of the AKS Algorithm

Here is a commonly used version of the AKS
pseudocode:
Input: integer n>1

[Link] if nis a perfect power

If there exist integers a> 1, b> 1such that
b
n=a

then return COMPOSITE.

[Link] the smallest suitable r
Find the smallest integer r such that the order
of nmodulo r is greater than ¿.
That is, the smallest r such that:
 ord r (n)> ¿

where ord r (n)is the smallest positive k such that:

k
n ≡1(mod r )

[Link] for small prime factors using gcd ⁡

For all integers afrom 2to r :

o Compute d=gcd ⁡(a , n).

o If 1<d <n , then return COMPOSITE (we

found a non-trivial factor).
[Link] n ≤ r , declare prime
If n ≤ r, then return PRIME.
[Link] main polynomial congruence test
Let:
limit =⌊ √ ϕ( r)⋅log ⁡2 n ⌋

where ϕ (r )is Euler’s totient function.

For all integers afrom 1to limit:
o Check whether the polynomial
congruence:
¿

holds.
“(mod (X −1 , n))” means:
r

 Do all arithmetic modulo n.

 Reduce polynomials modulo X −1, so r

any X with k ≥ r is reduced using X ≡ 1.

k r
 o If for some a, the congruence does not
hold, then return COMPOSITE.
[Link] all tests passed
Return PRIME.
That’s the bare algorithm. Now let’s unpack
what’s happening.

4. Explanation of Each Step

Step 1: Perfect Power Test
If n=a with b> 1, then nis composite (e.g., 16=2 , 27=3 ).
b 4 3

This step quickly removes obvious composite

numbers that are perfect powers.
There are efficient methods (binary search over b

and integer b-th roots) to test this in polynomial

time.

Step 2: Finding r with Large Multiplicative

Order
This is the trickiest and most expensive step.
We want a small integer r such that:
ord r (n)> ¿

where ord r (n)is the multiplicative order of nmodulo r .

Intuitively:
 This condition on the order ensures that the
polynomial congruence in step 5 is strong
 enough to force nto be prime if it passes all
tests.
 In simpler terms, a large order means n
“behaves randomly enough” modulo r so that
fake primes are ruled out.
Finding such an r takes a lot of time because we
may need to test many candidates and compute
orders, which involves modular exponentiation
and gcds.

Step 3: GCD Checks (Quick Composite

Detection)
For 2 ≤ a ≤r , we compute gcd ⁡(a ,n).

 If we ever find a gcd that is neither 1 nor n,

we have found a non-trivial factor of n.
 This means nis composite, and we can stop
early.
This step is relatively cheap compared to the
others, using Euclid’s algorithm.

Step 4: Small nCase

If n ≤ r, then the problem is already small.
The way r is chosen in step 2 ensures that such
small numbers are prime if they survive the
previous steps, so we can safely say PRIME.
Step 5: Polynomial Congruence Test
This is the core of AKS. For each ain the range:
1 ≤ a≤ ⌊ √ ϕ (r )⋅ log ⁡2 n ⌋ ,

we check:
¿

What does this mean computationally?

 Expand ¿using fast exponentiation (repeated
squaring) but keep coefficients modulo nand
degrees reduced modulo r using the relation
X ≡ 1.
r

 Compare the resulting polynomial with X + a,

n

also reduced modulo X −1. r

If nis prime, this congruence holds for all such a.

If nis composite, for “most” such ait will fail. AKS
proves that checking up to that limit is enough to
guarantee primality.

5. Time Complexity of AKS

Let nbe the input number and let L=log ⁡2 n(the

number of bits of n).

 The original AKS algorithm had time
complexity roughly:
~ 12
O( L ) ,

where ~
O hides polylogarithmic factors (like ¿).

 Later improvements reduced this to about:

 ~ 6
O( L ),

under some number-theoretic assumptions.

Still, this is a very high-degree polynomial in L

.
Where does this complexity come from?
[Link] r :
You may need to test many values of r up to
about L (roughly), and for each r , you perform
5

modular exponentiations and gcds. This

already contributes a big cost.
[Link] operations:
In step 5, you perform up to O(√ ϕ (r ) log ⁡n)
polynomial congruence checks.
Each check requires multiplying and reducing
polynomials of degree up to r , with
coefficients modulo n.
Using naive multiplication, one multiplication
is O(r ). Even with FFT-based multiplication, the
2

constant factors are large.

[Link] is in terms of log n:
Although each individual operation is
polynomial in L=log ⁡n, the exponents and
constants are big.

6. Why AKS is Not Usable in Practice

Even though AKS is a huge theoretical
achievement, it is not used in real cryptographic
systems. Reason:
1. Too Slow Compared to Probabilistic Tests
Miller–Rabin (probabilistic primality test):
 Time roughly:
~ 3
O(k ⋅ L )

for k rounds, which is very small in practice.

 For 1024-bit or 2048-bit numbers, Miller–
Rabin runs in milliseconds, and with enough
rounds, the probability of error is
astronomically small (e.g. less than 2 ).
−80

AKS:
 Even at the improved ~O( L ) complexity, for
6

1024-bit or 2048-bit numbers, the runtime is

many orders of magnitude larger than
Miller–Rabin or ECPP.
 So for real-world cryptography (RSA key
generation, etc.), AKS is simply too slow.
2. Big Hidden Constants and Memory Use
 The polynomial operations with degree up to
r ≈ L or so require storing and manipulating
5

huge polynomials.
 This means large memory consumption
and heavy constant factors.
  Practical libraries aim for speed and
simplicity; AKS is complex and heavy.
3. We Don’t Need Deterministic Polynomial
Time in Practice
In cryptography:
 A tiny probability of error (like 2
−100
) is
perfectly acceptable.
 So probabilistic tests (Miller–Rabin, Baillie–
PSW) are more than enough in practice.
 There also exist fast deterministic tests for
most sizes using additional assumptions
(e.g., using precomputed small primes or
under GRH).
Thus, the “extra guarantee” of AKS (absolute
certainty in polynomial time for all n) doesn’t give
practical benefits compared to the huge
performance cost.
4. Complexity of Implementation
 AKS involves advanced number theory and
tricky polynomial arithmetic modulo both n
and X −1.
r

 Probabilistic tests are much simpler and well-

tested; easy to implement and verify.
Because of all this, AKS is mainly a theoretical
milestone, not a practical tool.
7. Summary
 Goal of AKS: Provide the first
deterministic, general, polynomial-time
primality test.
 Core idea: Use a polynomial identity
¿

which characterizes primes when checked for a

suitable range of aand a carefully chosen r with
large multiplicative order.
 Steps:
[Link] if nis a perfect power.
[Link] smallest r with ord r (n)> ¿.

[Link] gcds to find small factors.

[Link] n ≤ r, declare prime.
[Link] the polynomial congruence for
1 ≤ a≤ √ ϕ (r ) log ⁡n.

 Complexity: Originally about ~ O( L ), improved

12

to ~
O( L ) , still far slower than practical tests.
6

 Why not usable:

o Very high-degree polynomial time and
huge constants
o Lots of heavy polynomial arithmetic and
memory usage
 o Much slower than simple probabilistic
tests that are already good enough for
real-world applications.
1. What is the AKS Algorithm?
The AKS primality test (Agrawal–Kayal–Saxena,
2002) is the first algorithm that:
 Always gives the correct answer
(deterministic)
 Works for all integers n(general)
 Runs in polynomial time in log n (i.e., in the
size of the input)
So, it proved the famous result:
PRIMES is in P (deciding whether a number is
prime can be done in polynomial time).
However, even though it is polynomial time, it is
not usable in practice because the polynomial
is of very high degree and constants are huge
compared to fast probabilistic tests like Miller–
Rabin.

2. High–Level Idea of AKS

AKS is based on a polynomial identity that holds
for primes:
For a prime number p:
¿
for all integers a. This comes from the binomial
theorem:
¿, and modulo a prime p, all middle binomial

coefficients ( p )for 0< k < pare multiples of p, so they

k
vanish mod p.
For composite n, this polynomial identity fails for
many choices of a.
AKS modifies this idea:
 It does not check the identity for all
polynomials or all a.
 It checks the identity only modulo a
cleverly chosen polynomial X −1and only r

for small values of a.

 If the identity holds for all those cases, it
proves nis prime.

3. Pseudocode of the AKS Algorithm

Here is a commonly used version of the AKS
pseudocode:
Input: integer n>1

[Link] if nis a perfect power

If there exist integers a> 1, b> 1such that
b
n=a

then return COMPOSITE.

 [Link] the smallest suitable r
Find the smallest integer r such that the order
of nmodulo r is greater than ¿.
That is, the smallest r such that:
ord r (n)> ¿

where ord r (n)is the smallest positive k such that:

k
n ≡1(mod r )

[Link] for small prime factors using gcd ⁡

For all integers afrom 2to r :

o Compute d=gcd ⁡(a , n).

o If 1<d <n , then return COMPOSITE (we

found a non-trivial factor).
[Link] n ≤ r , declare prime
If n ≤ r, then return PRIME.
[Link] main polynomial congruence test
Let:
limit =⌊ √ ϕ( r)⋅log ⁡2 n ⌋

where ϕ (r )is Euler’s totient function.

For all integers afrom 1to limit:
o Check whether the polynomial
congruence:
¿

holds.
“(mod (X −1 , n))” means:
r
  Do all arithmetic modulo n.
 Reduce polynomials modulo X −1, so r

any X with k ≥ r is reduced using X ≡ 1.

k r

o If for some a, the congruence does not

hold, then return COMPOSITE.
[Link] all tests passed
Return PRIME.
That’s the bare algorithm. Now let’s unpack
what’s happening.

4. Explanation of Each Step

Step 1: Perfect Power Test
If n=a with b> 1, then nis composite (e.g., 16=2 , 27=3 ).
b 4 3

This step quickly removes obvious composite

numbers that are perfect powers.
There are efficient methods (binary search over b

and integer b-th roots) to test this in polynomial

time.

Step 2: Finding r with Large Multiplicative

Order
This is the trickiest and most expensive step.
We want a small integer r such that:
ord r (n)> ¿

where ord r (n)is the multiplicative order of nmodulo r .

Intuitively:
 This condition on the order ensures that the
polynomial congruence in step 5 is strong
enough to force nto be prime if it passes all
tests.
 In simpler terms, a large order means n
“behaves randomly enough” modulo r so that
fake primes are ruled out.
Finding such an r takes a lot of time because we
may need to test many candidates and compute
orders, which involves modular exponentiation
and gcds.

Step 3: GCD Checks (Quick Composite

Detection)
For 2 ≤ a ≤r , we compute gcd ⁡(a ,n).

 If we ever find a gcd that is neither 1 nor n,

we have found a non-trivial factor of n.
 This means nis composite, and we can stop
early.
This step is relatively cheap compared to the
others, using Euclid’s algorithm.

Step 4: Small nCase

If n ≤ r, then the problem is already small.
The way r is chosen in step 2 ensures that such
small numbers are prime if they survive the
previous steps, so we can safely say PRIME.

Step 5: Polynomial Congruence Test

This is the core of AKS. For each ain the range:
1 ≤ a≤ ⌊ √ ϕ (r )⋅ log ⁡2 n ⌋ ,

we check:
¿

What does this mean computationally?

 Expand ¿using fast exponentiation (repeated
squaring) but keep coefficients modulo nand
degrees reduced modulo r using the relation
X ≡ 1.
r

 Compare the resulting polynomial with X + a,

n

also reduced modulo X −1. r

If nis prime, this congruence holds for all such a.

If nis composite, for “most” such ait will fail. AKS
proves that checking up to that limit is enough to
guarantee primality.

5. Time Complexity of AKS

Let nbe the input number and let L=log ⁡2 n(the

number of bits of n).

  The original AKS algorithm had time
complexity roughly:
~ 12
O( L ) ,

where ~
O hides polylogarithmic factors (like ¿).

 Later improvements reduced this to about:

~ 6
O( L ) ,

under some number-theoretic assumptions.

Still, this is a very high-degree polynomial in L

.
Where does this complexity come from?
[Link] r :
You may need to test many values of r up to
about L (roughly), and for each r , you perform
5

modular exponentiations and gcds. This

already contributes a big cost.
[Link] operations:
In step 5, you perform up to O(√ ϕ (r ) log ⁡n)
polynomial congruence checks.
Each check requires multiplying and reducing
polynomials of degree up to r , with
coefficients modulo n.
Using naive multiplication, one multiplication
is O(r ). Even with FFT-based multiplication, the
2

constant factors are large.

[Link] is in terms of log n:
Although each individual operation is
 polynomial in L=log ⁡n, the exponents and
constants are big.

6. Why AKS is Not Usable in Practice

Even though AKS is a huge theoretical
achievement, it is not used in real cryptographic
systems. Reason:
1. Too Slow Compared to Probabilistic Tests
Miller–Rabin (probabilistic primality test):
 Time roughly:
~ 3
O(k ⋅ L )

for k rounds, which is very small in practice.

 For 1024-bit or 2048-bit numbers, Miller–
Rabin runs in milliseconds, and with enough
rounds, the probability of error is
astronomically small (e.g. less than 2 ).
−80

AKS:
 Even at the improved ~O( L ) complexity, for
6

1024-bit or 2048-bit numbers, the runtime is

many orders of magnitude larger than
Miller–Rabin or ECPP.
 So for real-world cryptography (RSA key
generation, etc.), AKS is simply too slow.
2. Big Hidden Constants and Memory Use
  The polynomial operations with degree up to
r ≈ L or so require storing and manipulating
5

huge polynomials.
 This means large memory consumption
and heavy constant factors.
 Practical libraries aim for speed and
simplicity; AKS is complex and heavy.
3. We Don’t Need Deterministic Polynomial
Time in Practice
In cryptography:
 A tiny probability of error (like 2
−100
) is
perfectly acceptable.
 So probabilistic tests (Miller–Rabin, Baillie–
PSW) are more than enough in practice.
 There also exist fast deterministic tests for
most sizes using additional assumptions
(e.g., using precomputed small primes or
under GRH).
Thus, the “extra guarantee” of AKS (absolute
certainty in polynomial time for all n) doesn’t give
practical benefits compared to the huge
performance cost.
4. Complexity of Implementation
  AKS involves advanced number theory and
tricky polynomial arithmetic modulo both n
and X −1.r

 Probabilistic tests are much simpler and well-

tested; easy to implement and verify.
Because of all this, AKS is mainly a theoretical
milestone, not a practical tool.

7. Summary
 Goal of AKS: Provide the first
deterministic, general, polynomial-time
primality test.
 Core idea: Use a polynomial identity
¿

which characterizes primes when checked for a

suitable range of aand a carefully chosen r with
large multiplicative order.
 Steps:
[Link] if nis a perfect power.
[Link] smallest r with ord r (n)> ¿.

[Link] gcds to find small factors.

[Link] n ≤ r, declare prime.
[Link] the polynomial congruence for
1 ≤ a≤ √ ϕ (r ) log ⁡n.
  Complexity: Originally about ~ O( L ), improved
12

to ~
O( L ) , still far slower than practical tests.
6

 Why not usable:

o Very high-degree polynomial time and
huge constants
o Lots of heavy polynomial arithmetic and
memory usage
o Much slower than simple probabilistic
tests that are already good enough for
real-world applications.
2. Explore the factorization methods viz.,
Pollard p-1, Pollard rho, Number Field Sieve
and Quadratic Sieve methods and their time
complexities.
1. Pollard’s p–1 Method
Idea:
Works fast if one factor pof nhas p−1that is
composed of only small primes (smooth number).
How it works (brief):
 Compute a M
mod nfor a large M (lcm of small
numbers).
 Find gcd ⁡(a −1, n).
M

 If the gcd is not 1 or n, then it is a factor.

Time Complexity:
 O(B log ⁡B log ⁡n)

(B = smoothness bound)
Fast when: a factor’s p−1is smooth.
Slow when: p−1contains large prime factors.

2. Pollard’s ρ (Rho) Method

Idea:
Uses a pseudo-random sequence and the
“birthday paradox” to find a cycle modulo a
factor of n.
How it works (brief):
 Use function: 2
f ( x)=x +c ( mod n)

 Detect cycle using two pointers (Floyd’s

method)
 Compute gcd ⁡(∣ x− y ∣ ,n)

Time Complexity:
1/ 4
O(n )

Best suited for: Finding small factors of large

numbers.
Very simple and efficient in practice.

3. Quadratic Sieve (QS)

Idea:
Find numbers where:
2 2
x ≡ y (mod n)⇒( x− y)(x + y )≡ 0(mod n)
Then compute:
gcd ⁡( x− y , n)

Uses a factor base of small primes and linear

algebra.
Time Complexity (sub-exponential):
exp ( √ ln ⁡n ln ⁡ln ⁡n)

Best for: Numbers up to about 100 digits

Much faster than trial division or Pollard methods
for big numbers.

4. Number Field Sieve (NFS)

Idea:
Advanced version of QS using algebraic number
fields. Still based on finding
2 2
x ≡ y (mod n)

but in a deeper mathematical structure.

Fastest known algorithm for factoring large
integers.
Time Complexity (sub-exponential – best known):
exp ¿ ¿

Best for: Numbers larger than 100–110 digits

Used in breaking large RSA numbers in research.

5. Comparison Table (Short View)

Method Best Use Time Complexity
Special case
Pollard p–1 when p–1 O(B log ⁡B log ⁡n)

smooth
Pollard ρ Small factors O(n
1/ 4
)

Quadratic Up to ~100
exp ⁡( √ ln ⁡n ln ⁡ln ⁡n)
Sieve digits
Number 100+ digits
exp ⁡¿
Field Sieve (best)

Conclusion
Pollard methods are simple and fast for
small/special cases, while Quadratic Sieve and
Number Field Sieve are powerful sub-exponential
algorithms for large numbers, with NFS being the
fastest known classical factoring method.

3. Attacks on RSA and OAEP Protocol

(A) Attacks on RSA
[Link] Force Attack
o Try all possible private keys.
o Not practical for large key sizes (2048+
bits).
[Link] Attack
 o If attacker factors n=p × q , private key can
be found.
o Uses algorithms like NFS (Number Field
Sieve).
o Main real threat to small RSA keys.
[Link] Exponent Attack
o If public exponent e is small (like 3) and
message is not padded,
attacker can directly find the plaintext.
[Link] Ciphertext Attack (CCA)
o Attacker sends chosen ciphertexts and
observes decrypted output.
[Link] / Side-Channel Attack
o Measures time, power or EM signals
during decryption to leak key info.

(B) Attacks on OAEP (Optimal Asymmetric

Encryption Padding)
OAEP is actually a defense, not a weakness. It
protects RSA from many attacks by adding
randomness.
However, weak implementation can lead to:
[Link] Oracle Attack
 o If system reveals whether padding is
correct or not, attacker can slowly
decrypt data.
[Link] Number Weakness
o Bad random number generator reduces
security.
Note: Proper OAEP implementation makes RSA
secure against
chosen-plaintext and chosen-ciphertext attacks.

4. Other SHA Versions

SHA Output
Security Status
Version Size
❌ Broken (collisions
SHA-1 160 bits
found)
SHA-224 224 bits ✅ Secure
✅ Very secure (widely
SHA-256 256 bits
used)
SHA-384 384 bits ✅ Very high security
Brief Analysis
 SHA-1: Vulnerable to collision attacks, no
longer used in TLS or certificates.
 SHA-224: Shorter, used when less output is
needed.
  SHA-256: Most used (blockchain, SSL, digital
signatures).
 SHA-384: Stronger than SHA-256, used in
high-security systems.
All except SHA-1 belong to SHA-2 family and are
safe.

5. Security Attacks on Digital Signature Schemes

[Link] Spoofing
o Attacker pretends to be the real signer.
[Link] Hash Function Attack
o If hash is weak (like SHA-1), attacker can
generate collisions.
[Link] Attack
o Attacker creates a fake signature that
appears valid.
[Link] Attack
o Old signed message is reused again.
[Link]-in-the-Middle Attack
o Signature is replaced while being
transmitted.
[Link]-Channel Attack
o Observing time, power, or CPU usage to
recover key.
Final Summary (Very Short)
 RSA is mainly attacked through factorization
and side-channel attacks.
 OAEP protects RSA, but bad implementation
is dangerous.
 SHA-1 is broken; SHA-256 and SHA-384 are
secure.
 Digital signatures are attacked by forgery,
spoofing, and hash collisions.