[go: up one dir, main page]
Scribd
Upload
33 views33 pages

Maths Unit 5

The document discusses various concepts related to primality testing and factorization algorithms, including definitions of primality tests, Pollard's Rho algorithm, and the role of witnesses in primality testing. It also covers the Birthday Paradox and its implications in cryptography, trapdoor functions, and methods for factorization using different techniques. Additionally, it includes practical examples and applications of these algorithms in cryptography and number theory.

Uploaded by

adi637963
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
33 views33 pages

Maths Unit 5

The document discusses various concepts related to primality testing and factorization algorithms, including definitions of primality tests, Pollard's Rho algorithm, and the role of witnesses in primality testing. It also covers the Birthday Paradox and its implications in cryptography, trapdoor functions, and methods for factorization using different techniques. Additionally, it includes practical examples and applications of these algorithms in cryptography and number theory.

Uploaded by

adi637963
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 33

UNIT -5

4 MARKS :
1. Define- primality test

In discrete mathematics, a primality test is a procedure used to


determine whether a given natural number is a prime number or
composite. A prime number is a number greater than 1 that has no
positive divisors other than 1 and itself.

There are two main types of primality tests:


1. Deterministic tests – Always give the correct result (e.g., trial division,
AKS test).
2. Probabilistic tests – Faster, with high accuracy but a small chance of
error (e.g., Miller–Rabin, Fermat test).

2. Define Factorization through difference of squares.

Example :
3. Define pollard rho algorithm for Factorization
Pollard’s Rho is a probabilistic algorithm used for integer factorization,
particularly effective for large numbers with small prime factors. It uses
a pseudo-random function and cycle detection (like Floyd’s algorithm) to
find a non-trivial factor of a composite number n.

4. What is the role of witness in primality testing?


In primality testing, a "witness" is a number that can be used to
definitively prove that a given number is composite (not prime).
Key Points:
 In tests like Fermat's and Miller-Rabin, a witness is a value a such that:
o If n is prime, certain modular conditions hold for all valid a.
o If n is composite, some values of a will violate these conditions —
these are called witnesses to compositeness.
Example (Miller-Rabin Test):
 If a is a Miller-Rabin witness, it shows that nis definitely composite.
 If no witness is found after multiple rounds, n is declared probably prime
.
Conclusion:
Witnesses are crucial in probabilistic tests for detecting composite
numbers efficiently, improving the accuracy of primality testing.

5. Factorize N=4087 using pollar's rho method.


6.what is the collision algorithm?
7.Factorize N=648749 by using difference of square.
8.Factorize 6557 by L=13 using Pollards (p-1) algorithm.
9.What are the difference between private key cryptography and public
key cryptography ?

10.Explain the term birtday paradox.


Birthday Paradox (4 Marks)
The Birthday Paradox refers to the counterintuitive probability theory
problem that shows that in a group of just 23 people, there is a 50%
chance that at least two people share the same birthday.
Explanation:
 The paradox arises because we tend to think that matching birthdays
would be rare, but in reality, the number of possible pairs increases
quickly as the group size grows.
 For example, with 23 people, there are 253 unique pairs of people,
making it much more likely that two people share the same birthday
than we might initially expect.
Application in Cryptography:
 The Birthday Attack exploits the paradox to find collisions in hash
functions more efficiently than brute force.

11.Check and conform whether 1697 has 2 has a witness


12.Define -trapdoor function.
A trapdoor function is a type of one-way function that is easy to
compute in one direction but difficult to reverse unless specific secret
information (the "trapdoor") is known.
Key Characteristics:
 Easy to compute: Given f(x) it’s easy to calculate y=f(x).
 Hard to reverse: Given y, it's computationally difficult to find x without
the trapdoor information.
 Trapdoor: With the secret key or information, reversing the function
becomes feasible.
Example in Cryptography:
 The RSA encryption algorithm uses a trapdoor function where, given the
public key, encryption is easy, but decryption is only possible with the
private key.

13. factorize 6557 using pollards (p-1) algorithm.


12 marks:
1. Factorize 91 and 1403 choose an integer 2 by using pollard's p-1
algorthm.
2. Explain the discrete algorithm computation through index calculus.
3. Check and conform Whether 3713 has 2 as a witness
4. Factorize 471953 using the difference of square approach.
5. Explain the pollard rho algorithm
6. State and Prove Miller-Rabin Test
7. Explain Pollard Method .
Pollard’s Rho method is a probabilistic algorithm used for integer
factorization, particularly useful for finding non-trivial factors of large
composite numbers, especially when the smallest factor is relatively small.

1. Introduction
 Developed by John Pollard in 1975.
 Named “Rho (ρ)” because the sequence it generates resembles the
Greek letter ρ.
 Commonly used in cryptography, especially in attacking weak RSA keys.

2. Purpose
Pollard's Rho is used to find a non-trivial factor of a composite number n. It
is most effective when the number has a small prime factor.

3. Idea Behind the Method


It uses the idea of the birthday paradox and cycle detection. It defines a
pseudo-random function and checks for repeated values modulo a prime
factor of n.
If two numbers x and y in a sequence satisfy:
Advantages
 Efficient for numbers with small factors.
 Requires very little memory (compared to other methods).
 Works well in practice for moderate-sized numbers (up to ~20 digits).

7. Limitations
 May fail if unlucky (but can be retried with a different function).
 Slower for numbers with large prime factors.
 Not suitable for general-purpose large integer factorization (like modern
RSA keys).

8. Applications
 Cryptanalysis: breaking weak cryptographic systems.
 Number theory: studying the structure of integers.
 Preprocessing step in more complex factorization algorithms.

8. Describe factorization through different square


Factorization is the process of breaking down an expression into simpler
expressions (called factors) that, when multiplied together, give back the
original expression. One common technique is factorization through the
difference of squares.

Example:
9. Explain the pollards rho algorithm for factorization
10.Check and conform whether 4481 has 2 and 3 has witness
11. Factorize 5475551 using the differnce square approach
12. Using pollard method, factorize the integer 3893.

You might also like