Scribd
Upload
11 views4 pages

CSE 2101 Lab Manual: Algorithms & Cryptography

Uploaded by

rakib.hosen.tamim.2k2
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
11 views4 pages

CSE 2101 Lab Manual: Algorithms & Cryptography

Uploaded by

rakib.hosen.tamim.2k2
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

Heaven’s Light is Our Guide

Computer Science & Engineering


Rajshahi University of Engineering & Technology

Lab Manual

Module- 03
Course Title: Sessional based on CSE 2101
Course No. : CSE 2102
Experiment No. 3

Name of the Experiment: Algorithms, Number Theory and Cryptography

Duration: 2 Cycles

Experiments/Problems:
[1] Given a list of n integers, find the largest integer in the list and its complexity.
[2] Given a list of n integers, find the first and last occurrences of the largest
integer in the list.
[3] Given a list of n distinct integers, determine the position of an integer in the list
using a linear search.
[4] Given an ordered list of n distinct integers, determine the position of an integer
in the list using a binary search.
[5] Given a list of n integers, sort them using a bubble sort.
[6] Given a list of n integers, sort them using an insertion sort.
[7] Given an integer n, use the greedy algorithm to find the change for n cents
using quarters, dimes, nickels, and pennies.
[8] *Given the starting and ending times of n talks, use the appropriate greedy
algorithm to schedule the most talks possible in a single lecture hall.
[9] Given an ordered list of n distinct integers and an integer x, find the number of
comparisons used to determine the position of an integer in the list using a
binary search and using a linear search.
[10] Given a list of n integers, determine the number of comparisons used by the
bubble sort and by the insertion sort to sort this list.
[11] Given a set of identification numbers, use a hash function to assign them to
memory locations where there are k memory locations.
[12] Given a positive integer N, a modulus m, multiplier a, increment c, and seed
x0, where 0 ≤ a<m, 0 ≤ c<m, and 0 ≤ x0 <m, generate the sequence of N
pseudo-random numbers using the linear congruential generator x n+1 = (axn +
c) mod m.
[13] Given a message, encrypt this message using Caesar cipher; and decrypt this
message again.
[14] Given a positive integer, determine whether it is prime.
[15] Given a positive integer, determine whether it is Mersenne prime.
[16] The polynomial f(n) = n2-n+41 has the interesting property that f(n) is prime
for all positive integers n not exceeding 40. Given a positive integer n, find the
value of f(n) whether f(n) is prime or not.
[17] [Goldbach’s Conjecture] Given an even integer n, find two prime number
whether the sum of them is equal to n.
[18] Given an integer n, whether f(n) = n 2+1 is prime or not.
[19] [The Twin Prime Conjecture] Given a positive number n, whether it is prime or
not. If n is prime, check whether n and n+2 are Twin primes or not.
[20] Given two positive integers, find their greatest common divisor using the
Euclidean algorithm.
[21] Given two positive integers, find their least common multiple.
[22] Given a positive integer, find the prime factorization of this integer.
[23] Given integers n and b, each greater than 1, find the base b expansion of this
integer.
[24] [Modular Exponentiation] Given the positive integers a, b, and m with m> 1,
find ab mod m.
[25] *Given a positive integer, find the Cantor expansion of this integer.
2|P ag e
[26] Given two positive number a and b, find s and t such that gcd(a,b) = sa+tb.
[27] [The Chinese remainder theorem] Given n linear congruence’s modulo pair
wise relatively prime moduli, find the simultaneous solution of these
congruence’s modulo the product of these moduli.
[28] [pseudo primes] Given a positive integer b, find all pseudo primes to the base
b that do not exceed 10,000.
[29] Given a composite integer n, determine whether it is Carmichael number or
not.
[30] **Construct a valid RSA encryption key by finding two primes p and q with 200
digits each and an integer e> 1 relatively prime to (p − 1)(q − 1).
[31] Given a message and an integer n = pq where p and q are odd primes and an
integer e> 1 relatively prime to (p − 1)(q − 1), encrypt the message using the
RSA cryptosystem with key (n,e).
[32] Given a valid RSA key (n,e), and the primes p and q with n = pq, find the
associated decryption key d.
[33] Given a message encrypted using the RSA cryptosystem with key (n,e) and the
associated decryption key d, decrypt this message.
[34] Given an m × k matrix A and a k × n matrix B, find AB.
[35] Given a square matrix A and a positive integer n, find An.
[36] Given a square matrix, determine whether it is symmetric.
[37] Given two m × n Boolean matrices,find their meet and join.
[38] Given an m × k Boolean matrix A anda k × n Boolean matrix B,find the
Boolean product of A and B.
[39] Given a square Boolean matrix A and a positive integer n, find A[n].

Explain:
[25] A cantor expansion is a sum of the form
x = ann!+ an−1(n − 1)!+···+ a11!

procedure Cantor(x:positiveinteger)
n := 1; f := 1
while (n + 1) · f ≤ x
begin
n := n + 1
f := f · n
end
y := x
while n> 0
begin
an :=⌊y/f⌋
y := y − an · f
f := f/n
n := n − 1
end{x = ann!+ an−1(n − 1)!+···+ a11!}

[28] Let b be a positive integer. If n is a composite positive integer, and bn-1 ≡ 1(mod
n), then n is called a pseudo prime to the base b.

[29] A composite integer n that satisfies the congruence bn−1 ≡ 1(mod n) for all
positive integers b with gcd(b,n) = 1 is called a Carmichael number. (These numbers
are named after Robert Carmichael, who studied them in the early twentieth century.)

3|P ag e
[30-32] The RSA Cryptosystem

KEY GENERATION:
[1] Choose two distinct prime numbers p and q, say, with 200 digits each.
Simple Example: p = 61 and q = 53
[2] Compute n = pq.
Simple Example: n = 3233
[3] Compute φ(n) = φ(p)φ(q) = (p − 1)(q − 1) = n − (p + q − 1).
Simple Example: φ(n) = 3120
[4] Choose an integer e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1; i.e., e and
φ(n) are coprime.
Simple Example: e= 17
[5] Determine d as d ≡ e−1 (mod φ(n)); i.e., d is the modular multiplicative inverse
of e (modulo φ(n)) [This is more clearly stated as: solve for d given d⋅e ≡ 1
(mod φ(n))]
Simple Example:
d = 2753
Worked example for the modular multiplicative inverse
d x e mod φ(n) =1
2753 x 17 mod 3120 =1
[6] The public key consists of the modulus n and the public (or encryption)
exponent e. The private key consists of the modulus n and the private (or
decryption) exponent d, which must be kept secret.
Simple Example: The public key is (e = 17) and the private key is (n = 3233,
d = 2753).

RSA ENCRYPTION:
For a padded plaintext message M, the encryption function is
C(M) = Me mod n

Simple Example: For instance, in order to encrypt m = 65, we calculate


C(M)= 6517 mod 3233 = 2790

RSA DECRYPTION:
For an encrypted ciphertext c, the decryption function is
M(C) = Cd mod n

Simple Example: To decrypt c = 2790, we calculate


M(c) = 27902753 mod 3233 = 65

Report:
Your completed work must be submitted through a LAB REPORT.

Read:
[1] Kenneth H. Rosen, “Discrete Mathematics and its Application”, 7th Edition:
Chapter 3 (Algorithms) Chapter 4(Number Theory and Cryptography).

4|P ag e

Common questions

Powered by AI

Pseudo primes are composite numbers that satisfy the condition b^(n-1) ≡ 1 (mod n) for a base b, making them appear prime under specific tests. Carmichael numbers are a stronger type of pseudo prime, satisfying this property for all bases b that are coprime to n. This makes them deceptive since they pass Fermat's primality test for non-prime numbers.

The Euclidean algorithm finds the GCD of two integers through a series of division steps, using the remainder of each division as the new divisor in the next step, continuing until the remainder is zero. The last non-zero remainder is the GCD. It is highly efficient compared to other methods like prime factorization, as it operates in O(log(min(a, b))) time, leveraging the properties of division and modulus.

The RSA decryption key d is derived using the extended Euclidean algorithm to find the modular inverse of the encryption key e relative to φ(n), which is (p-1)(q-1). The relationship de ≡ 1 (mod φ(n)) ensures that the decryption and encryption operations are inverses. This derivation is critical to RSA's functionality and security, relying on the difficulty of reverse-engineering φ(n) without knowing p and q.

Binary search divides a sorted list into halves, reducing the possible location of the target element by half each iteration, performing O(log n) comparisons in the process. This efficiency is in stark contrast with linear search, which can require up to n comparisons in the worst case. Binary search is most efficient when dealing with very large sorted datasets where quick lookup times are crucial.

Cantor expansion expresses a number x as a sum x = an*n! + an-1*(n-1)! + ... + a1*1!, where each a is a digit within a specific range determined by the factorial factor. This is closely related to the factorial number system, where numbers are expressed similar to base-n systems but using factorials instead of powers. This method is useful in combinatorial contexts because it allows unique representation using constrained digits.

A linear congruential generator produces a sequence of pseudo-random numbers using the recurrence relation x_{n+1} = (ax_n + c) mod m, where x is the sequence, and a, c, and m are parameters setting up the sequence's linear characteristics. It is widely used due to its simplicity, but its randomness quality heavily depends on the parameter choices and initial seed, making mathematical analysis crucial for high-quality randomness.

The bubble sort algorithm compares each pair of adjacent elements and swaps them if they are in the wrong order, effectively "bubbling" the highest element to the end of the list in each pass. Its time complexity is O(n^2) in the worst and average cases. Insertion sort, on the other hand, builds the sorted array one element at a time and has a time complexity of O(n^2) as well, but it performs better than bubble sort on average for partially sorted arrays since it only scans as much as needed to place an element.

In RSA, modular arithmetic is crucial as it allows for operations over a finite field. Encryption transforms a message M into a ciphertext C using C = M^e mod n, and decryption recovers M using M = C^d mod n. The use of modulus n ensures that operations remain within a manageable size, even for large e and d, and roots the technique in number theory, which contributes both to the cryptosystem's functionality and its security.

The RSA encryption process involves choosing two large prime numbers, p and q, and computing their product n = pq. The totient φ(n) is then used to find an encryption exponent e that is coprime to φ(n). The public key consists of (n, e), while the private key is the decryption exponent d, which is the modular inverse of e (mod φ(n)). The security of RSA relies on the difficulty of factoring large numbers, ensuring that while the public key can encrypt a message, only the private key can decrypt it.

Goldbach’s Conjecture states that every even integer greater than 2 can be expressed as the sum of two primes. To find such a pair for a given even integer n, the approach is typically to iterate through potential primes less than n, and check if the difference between n and this prime is also a prime. While straightforward in description, there is no known algorithm that avoids testing all pairs effectively, due to the conjecture's unproven nature in the general case.

You might also like