Factorisation and Cryptography: Methods, Advantages, and Disadvantages

This report delves into the critical role of factorisation within the realm of cryptography. It begins by defining and differentiating between integer and prime factorisation, laying the groundwork for understanding their applications. The report then explores the method of square root approximation and its relevance. Furthermore, it examines the advantages of using factorisation to enhance the integrity, authenticity, and confidentiality of data transmitted through various channels, particularly in the context of securing confidential information. The discussion extends to the practical aspects, outlining the advantages and disadvantages of factorisation in cryptography, including the RSA algorithm. The report also touches on the method of trial division factoring and its limitations. By examining these concepts, the report provides a comprehensive overview of factorisation's importance in modern cryptography, highlighting its strengths and weaknesses in maintaining secure data transmission.

Running head: FACTORISATION AND CRYPTOGRAPHY
FACTORISATION AND CRYPTOGRAPHY
Name of student:
Name of university:
Author’s note:

1FACTORISATION AND CRYPTOGRAPHY
Abstract
This report aims to discuss the topic factorisation in cryptography. This report includes the
discussion of the topics integer factorisation and prime factorisation. The method of square
root approximation is stated in this report. The use of cryptography is used for securing
confidential data and with the help of factorisation in cryptography, the integrity, authenticity
and the confidentiality of the data to maintain a secure transmission over any transmission
channel can be increased. In the theory of numbering, integer factorisation is disintegration of
any number that is composite in the product of reduced integers. When the restriction of
integers is done into prime numbers, the method of factorisation is known as prime
factorisation. Most of the factoring programs attempts the method of trial division by the
primes that are smallest. The method of square root approximation is a common method of
factorisation that is used in cryptography. Prime factorisation is the breaking down of any
composite number in smaller divisors that are trivial, which can be multiplied together and
obtain a value that is equal to the original integer.

2FACTORISATION AND CRYPTOGRAPHY
Introduction
This report aims to discuss about the topic Factorisation and its application in
cryptography. A brief discussion of the Factorisation is stated in this report. The two types of
factorisation described in this report are the Integer factorisation and Prime factorisation. The
advantages and disadvantages of factorisation in cryptography is indicated in this report.
Lastly, an appropriate conclusion of this report is provided.
Factorisation is utilised in mathematics for writing a mathematical object or number
writing as product of several factors, commonly simpler or smaller objects of the similar
kind. Factorisation is not commonly utilised in possessing divisions of number systems like
the complex or real numbers as X can be also written as (xy) x (1/y) when Y is not zero. Still,
a meaningful factorisation for any rational number or any rational function can be obtained
by writing in the terms that is lowest and separately factoring the denominator and numerator.
Cryptography is the essential building block for the systems of e-Commerce (Bouwmeester et
al., 2013). Commonly, cryptography with public key is utilised for confirming the integrity,
privacy, and legitimacy of organisational information.
Discussion
Factorisation
According to the fundamental theorem of arithmetic, which states that each integer
that is positive can be factored in a product of prime numbers, that cannot be factored further
into the integers greater than 1. However, this factorisation is considered to be unique up to
the factor orders (Lindell & Katz, 2014). Even though, the integer factorisation is kind of
inverse to the multiplication, the algorithm is much more difficult, which is a fact that is

3FACTORISATION AND CRYPTOGRAPHY
exploited in the cryptosystem of RSA for implementing the cryptography with public key.
The study of polynomial factorisation has done for centuries. In the elementary algebra, roots
finding is reduced by factoring a polynomial. The polynomials with the coefficients in
integers or in any field possess the property of unique factorisation, which is a version of
fundamental arithmetic theorem with the prime numbers that are reduced by the irreducible
polynomials (Kahate, 2013). Specifically, an univariate polynomial consisting of coefficients
that are complex admits to a distinct factorisation in the linear polynomials, which is the basic
theorem of algebra. In such cases, the conducting of factorisation can be done with the
algorithms of root-finding. In computer algebra, the situation of polynomials with the integer
coefficients is fundamental. Several computer algorithms are there for the factorisation
computing in the polynomials ring with the coefficients that are rational number. A ring that
is commutative possessing distinct factorisation property is referred as the domain of unique
factorisation (Buchmann, 2013). There are several number systems like the algebraic integers
ring that are not distinct domains of unique factorisation.
Factorisation can also refer to the more common decompositions of any mathematical object
in the product of simpler or smaller objects. As an example, every function can be factored in
the composition of any function that is surjective along with the injective function. Matrices
includes several kinds of matrix factorisations. As an example, each matrix has some unique
LUP factorisation as the product of a lower triangular matrix L along with the diagonal
entries that are equal to one, U or the upper triangular matrix, and P which is permutation
matrix, which is matrix formulation of Gaussian elimination (Salomaa, 2013).
Integer factorisation
In the theory of numbering, integer factorisation is disintegration of any number that
is composite in the product of some smaller integers. When the restriction of these integers is
up to the prime numbers, this procedure is known as prime factorisation.

4FACTORISATION AND CRYPTOGRAPHY
When numbers are found to be significantly large, none of the new algorithm of
integer factorisation that is non-quantum is currently known. Modern methods of factoring N
falls in two categories, which includes the method of Pollard Rho, Elliptic Curve Method,
and the trial division. The algorithms involved in the second category factors a number
irrespective of sizes of the factors that are prime but it costs additional when it is applied to
the integers that are larger (Van Tilborg & Jajodia, 2014). These algorithms includes the
fraction that is continued, QS or Quadratic Sieve and the NFS (Number Field Sieve).
Commonly, the algorithms involved in these groups are essential. Commonly, the utilisation
of algorithms in these groups are equally significant.
Concepts of base
Factoring linque: Symbols Q, R, Z denotes the rational number sets, integers and real
numbers. If y and x are the integers, then x/y (x divides y) denotes that y is the multiple of x.
That means, x/y if and only if there exists k belongs to z such that y=kx. GCD (x,y) is used to
denote that GCD or the Greatest Common Divisor of both the integers Y and X (Mirhosseini
et al., 2015). GCD is always positive and it becomes negative when x=y=0. If gcd(x,y) = 1,
then the variables y and x are found as coprime, there exists none same factor for except ± 1.
Smoothness of power: Any N number is considered to be B-smooth when it consists
of none of the divisors that are prime higher that the bound B, where B is considered to be a
positive integer. An integer that is positive is considered to be B-smooth if all the powers that
are prime are dividing N are lesser than or it is equal to B (Kosba et al., 2016). The
smoothness of power of is the B that is largest such that N is B-power-smooth.
Fermat’s little theorem: Consider n be any integer that is composite with p as prime
factor. By the application of Fermat’s little theorem, that states:

5FACTORISATION AND CRYPTOGRAPHY
Advantages and disadvantages of Integer factorisation
Like other innovations, the factorization in cryptography has also its own advantages
and disadvantages. These are demonstrated hereafter.
The advantages:
The cryptography has been all about number theory. Here every integer numbers has
been developed of primes. Hence one has to deal with lots of prime numbers in the number
theory. Specifically, various important cryptographic algorithms like RSA has been
depending critically over integer factorization of large numbers. This has been taking lots of
time, Here, one has a public key comprised of product of a couple of large numbers. This is
used for encrypting messages. This also includes a secret key comprising of primes used for
decrypting those messages. Further one can turn the public key into “public”. Here every
body gas using that to encrypt messages. Anybody needed to access the desired crypted
message has needed to make the number factorized. This takes long time in practical
situation.
Thus the benefits can be summarized as follows:
The factorization in cryptography has been used to encrypting data. This has been
permitting only the individual having the key to access the data, assuring the privacy.
Moreover, it can be used in “signing” messages and showing the recipient that exactly
what the sender’s identity has been, as claimed by sender.

6FACTORISATION AND CRYPTOGRAPHY
The disadvantages:
For instance the RSA algorithm has been bringing their fake public-ley algorithms.
Here the users has never been worrying to consider anybody taking other’s place. This is
done by counterfeiting various published false public keys. Thus has been possible to publish
widely the proper key into public and preventing the counterfeiting. Further, there has been
complexities of key creation. As RSA algorithm has been restricted but prime and effectively
of creating primes has been lesser. Hence this has been hard to get access to secret data.
Moreover, the security has required to be proofed. This RSA security has been depending on
the complexity to factor huge numbers. However, this has been equivalent to factoring and
this has not been proven as per theory. The reason is that there is no evidence of cracked RSA
that has needed factorizations. As there are algorithms that can be decomposing large number
quickly, RSA algorithm security has not been threatened. Besides, the ability of computations
of computer has been constantly improving. Here the expense of computer to reduce, parallel
technology of computers in developing and attacking RSA algorithm has been getting huge
ability of growth. Lastly, it has been slow in speed. This RSA encryption and decryption
algorithm has been needing lots of calculations and speeding that slowly. This is as compared
to symmetric cryptographic algorithm that has been thousand times slower. Through
developing huge number of decomposition tools the primary lengths has been rising to assure
security and the computation has been higher.
Theoretically, newer technologies has been rendering the present cryptographic
schemes like RSA to useless Here, the following big threat for present schemes of
cryptography is quantum computers. This has been presently researched by different

7FACTORISATION AND CRYPTOGRAPHY
universities around the globe. As the quantum computers are built eventually, the algorithms
of integer factorizations are used to encrypt that can be rendered useless. Thus it has been
seen that the future of factorization in cryptography and the applications has been coming to
an end. This is because of the fact that various processing abilities of quantum computing. As
any normal computer has been taking billions of years in deciphering texts, quantum
computers, on the other hand has been deciphering the txt in just a minutes. This is done
completely in theoretical manner.
Method of Trial division factoring
Most of the factoring programs attempts the method of trial division using the primes that are
smallest. Even though the length of the integer N is found to 100 decimal digits, few seconds
are taken for division of N by the primes up to 107. When it is a composite number, then a
prime consisting in N is almost at √N. For factoring N, utilisation of the algorithm of trial
division sequentially divides the number N with the primes 2,3,5,7,….. √N and checks which
of the primes divides the number that are to be factored (Kranakis, 2013). When N has the
largest prime factor as P, then this method of trial division involves O(p) steps (or O(p/ln p))
steps when the trial division is done using the primes.
Commonly, special forms are involved in the prime divisors of N. As an instance, if p / aN – 1
but p ≠ ak – 1 where k < N and k/ N, then p ≡ 1(mod N). This information offers trial
division, as it restricts the possible divisors range. For these kind of numbers, the method of
trial division can be utilised by all the primes that are qualifying below 232 or higher.
Moreover, unless N possess any distinct form, the trial division method is not useful for
discovery of the prime divisor that are above 109. Moreover, this method is not so
economical, nonetheless several better methods are available in recent times. The most recent
methods are the QS and NFS that are based on the format of Pierre de Fermat (1601-1665)[24]

8FACTORISATION AND CRYPTOGRAPHY
who have perceived that each number N that is composite can also be written as difference of
two squares: N = x2–y2 = (x+ y)(x – y). therefore, after finding the numbers x and y, the
factors of number N have also been found. Sieving process is utilised for the discovery of the
numbers, where the probable values of x and y have been excluded (Lyubashevsky, Peikert &
Regev, 2013). This process includes the collection of efficient relations: the number pair a
and b involving only prime factors that are small, such that the difference: a – b is divided by
the number N.
The difficulty in the factoring grows with the increase in size, which means the digit numbers
of any number that is to be factorised. For testing this, number N consisting of L decimal
digits (N ≈ 10L) and attempt factoring it with dividing it by .
After this process is done, the remainder is checked. In the scenario that is worst,
there might rise a situation of using division with approximate values for problem solving an
exponential increase as the function of L (Peikert, 2014).
Difficulty and complexity
The publishing of no algorithm has been done for factoring all the integers in the polynomial
time, that is factoring the numbers that are b-bit in the time O(bk ) for a constant K. there are
some available algorithm that are quicker than the O((1+ε)b) for the entire positive integers,
which are sub-exponential. Running time that is best available, which is asymptotic for
common field of common number is the algorithm of GNFS, for any number N with b-bit is
For the present computers, for any kind of large number N the best suitable algorithm is
GNFS. For any quantum computer, Shor’s algorithm has significant importance in

9FACTORISATION AND CRYPTOGRAPHY
cryptography if the scalability is defined in the quantum computation. This algorithm
involves number inputs of O(b) space and O(b3) time on b-bit numbers.
Technique of square root approximation
The method of square root approximation is a common method of factorisation that is used in
cryptography. This method involves the following steps:

10FACTORISATION AND CRYPTOGRAPHY

11FACTORISATION AND CRYPTOGRAPHY
The algorithm of factorisation based on the square root approximation
Data: n: an integer number that is to be factorised, Pr: a list of the subset of prime numbers,
U pr: a threshold that is indicating the highest r=pq allowed, Highstep : a threshold
that is indicating the steps that are allowed for finding a solution (Pirandola et al., 2015)
Result: A and B: 2 integers factors n
Begin
Initialisation
a := 0.02, r := 2, steps :=0:
f (x) :=√n –[√n];
iterate until finding factors or until reaching the threshold specified for steps;
repeat
while (r < U pr AND f(x) x r ≠ [f (x) x r] ± a) do
find a possible multiplier r of f (x) which generates its nearest integer:
steps = steps + 1;
factor r into p and q;
A :=[ √n] x q/p;
If A is not a divisor of n then
find in Pr the nearest value Pri to A;
A := GCD (Pri-2 × Pri -1 × Pri × Pri+1 × Pri +2 , n );
Until A is an integer divisor of n OR steps > Highstep:
if steps < Highstep then
B :=n/A;
Else
Print (“ n is prime or no solution is found for the chosen thresholds”);
end