LSFR and GCD Calculation

This document explains the concept of LSFR and GCD calculation with solved examples. It covers the definition of LSFR and GCD, their equations, and how to calculate them. The document also includes a bibliography of sources for further reading.

Surname 1
Student’s Name
Professor’s Name
Subject
Date
Question 1
a)
(1, 7) (0, 2)
x1 =1 y1 =0
x2 =7 y2 =2
Calculating the linear equation
(y- y1) = y2− x1
x2 −x1
(x- x1)
y-0 = 2−0
7−1 (x-1)
y= 2
6 (x-1)
y= 1
3(x-1)
b)
(1, 6) (0, 1)
x1 =1 y1 =0
x2 =6 y2 =1
Calculating the linear equation
(y- y1) = y2− x1
x2 −x1
(x- x1)

Surname 2
y-0 = 1−0
6−1 (x-1)
y= 1
5(x-1)
y= 1
5(x-1)
Question 1
a)
LSFR is defined as the element of pseudo random generator which generates a set of encryption
keys (Kim 3). The general formula LSFR are easily generalized in any finite model; GF (p).
LSFR is easily implemented in software and hardware thus they are widely applied in stream
cipher (Gómez 4; Denning 42).
The LFSR equation: xn+5 = xn + xn+3
When x=0, then X0+5 = x0 + x0+3 = 0+0 = 0
When x=1, then X1+5 = x1 + x1+3 = 1+0 = 1
When x=2, then X2+5 = x2 + x2+3 = 0+0 = 0
When x=3, then X3+5 = x3 + x2+3 = 0 = 1
When x=4, then X4+5 = x4 + x4+3 = 0+0 = 0
Thus the LSFR sequence becomes: 0, 1, 0, 1,0……
Therefore, the first 20 bits are: 0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1
b)
The first 20 bit follows a PN-sequence by investigation. The PN-sequences a period generalized
using the formula2n−1. Therefore, the period of LSFR is 2n−1.
Question 2
Definition

Surname 3
Let “a” and “b” be the integers and non-zero. The GCD of a and b, written as the gcd(a,b) , is the
integer “d” with the two main properties :
i) d is a common divisor of a and b i.e d|a and d|b
ii) Ѱ of c, if c is a common divisor of both a and b, then c ≤ d. In other words, for all
integers c, if c|a and c|b, then c ≤d.
Solution
Integers a and b are called relatively prime iff their GCD is 1 (Bhandari 33).
Given two numbers; 4883 and 4369
We have to use the extended Euclidean algorithm to find the GCD of 4883 and 4369 and express
them as a linear combination.
Step 1: Calculating the GCD
4883= 1(4369) +514
Thus 514 = 4883-4369
4883
4369 = 1 rem 514
But
4369
514 = 8 rem 257
And,
4883
514 =9 rem 257
Thus
514
257 = 2 rem 0
Since the remainder is 0, the greatest common divisor is the divisor, 257

Surname 4
Therefore, GCD = 257
Step 2: Expressing GCD as a linear combination
257 = -8(4883) +9(4369)
Therefore, the greatest common divisor of 4883 and 4369 is 257
Number 4
a)
Let n= 391
Factorizing 391 gives; 391= 17*23
n-1 = 390
Φ (n) = Φ (17) Φ = (23) = 16*22 = 352
2390 = 2352,238
29 =512 thus 29= 512(mod391)
238 ≡ 285 (mid391)
Fermat Theorem with a=2, n=391ged (a, n) =1
So,
aΦ(n ) = 1(mod, n)
2Φ(n) = 1(mod, n) ⇒ 2352 ≡≡1(mod391)
2391−1 =2390 = 2352,238
Thus
2391−1 ≡2352 =2352,238(mod391)
2390 ≡238(mod391)

Surname 5
2391≡ 238 (mod391) ⇒ 2285(mod391)
b)
2 j ≡ 1 (mod, n)
Applying the Fermat theorem
J = Φ (n) = Φ (391) = 352 thus J = 352
Work Cited
Bhandari, Sandeepak. "A New Era Of Cryptography : Quantum Cryptography". International
Journal On Cryptography And Information Security, vol 6, no. 3/4, 2016, pp. 31-
37. Academy And Industry Research Collaboration Center (AIRCC),
doi:10.5121/ijcis.2016.6403.
D. Denning. “Cryptography and Data Security Addison-Wesley Publishing Company”. 2013.
Gómez, Pardo J. L. Introduction to Cryptography with Maple. Heidelberg: Springer-Verlag,
2013. Internet resource.
Kim, Kwangjo. "Cryptography: A New Open Access Journal". Cryptography, vol 1, no. 1, 2016,
p. 1. MDPI AG, doi:10.3390/cryptography1010001.