Primality Testing and Factorisation

 Two practical problems that arise in Number Theory related to Primes are


1) How do we determine whether the given integer $n$ is prime ( primality testing)
2)How do we find the prime power factorisation of a given integer $n$.

Primality Testing

An integer $n>1$ is composite if and only if it is divisible by some prime $p \le \sqrt{n}$

Proof:If $n$ is divisible by such a prime $p$, then since $1 \lt p \le \sqrt{n} \lt n$, it follows that $n$ is composite. Conversely if $n$ is composite then $n=ab$ ,where $1 \lt a \lt n$ and $1 \lt b \lt n$; at least one of $a$ and $b$ is less than or equal to $\sqrt{n}$ ( if not $ab > n$), and this factor will be divisible by a prime $p \le \sqrt{n}$, which then divides $n$.

Example: we can check 97 is prime by checking that it is divisible by none of the primes $p \le \sqrt{97}$, namely 2,3,5 and 7.

This method requires us to test, whether an integer is divisible by various primes $p$.For certain small primes $p$ there are simple ways of doing this, based on the properties of the decimal number system.In decimal notation a positive integer $n$ i represented as

$$n=a_k10^k+a_{k-1}10^{k-1}+\cdots+a_110%1+a_010^0$$

where $a_0,a_1,\ldots,a_k$ are integers $0 \le a_i \le 9$ for all $i$ and $a_k \ne 0$.$n$ is divisible by 2 if the last digit is divisible by 2.$n$ is divisible by 5 if the last digit is 0 or 5.Similarly  $n$ is divisible by 3 if the sum of the digits is divisible by 3.$n$ is divisible by 11 , if the alternating sum of digits is divisible by 11.

Example:Consider the number 23

3 - last digit is not divisible by 2 .So it is not divisible by 2.

23=2+3=5 - sum of the digit is not divisible by 3.So it is not divisible by 3.

3- the last digit is not divisible by 5.So it is not divisible by 5.

2-3=-1=10 - which is not divisible by 11

Example:814 check divisibility by 3 and 11

8+1+4 - 13 not divisible by 3

8-1+4=11 divisible by 11 ie;814/11=74

Example: 8703585473 is divisible by 3?is it divisible by 11?

8+7+0+3+5+8+5+4+7+3=50 not divisible by 3

8-7+0-3+5-8+5-4+7-3=0 divisible by 11.

This method of primality testing is effective for fairly small integers $n$, since there are not too may primes $p$ to consider.But when $n$ become large , it is very time consuming.; by the Prime number Theorem, number of primes $p \le \sqrt{n}$ is given by

$$\pi(\sqrt{n})=\frac{\sqrt{n}}{ln( \sqrt{n})}$$

In cryptography we use large numbers with several hundred decimal digits.So this algorithm will take several months to compute.Better algorithm like Solovey-Strassen can beemployed in this case. We will discuss these techniques later.

The Sieve of Eratosthenes is a systematic way of compiling a list of all the primes up to a given integer $N$. First we list the integers $2, 3,... N$ in increasing order. Then we underline 2 (which is prime) and cross out all the proper multiples 4, 6, 8,... of 2 in the list (since these are composite). The first integer which is neither underlined nor crossed out is 3: this is prime, so we underline it and then cross out all its proper multiples 6, 9, 12, .... At the next stage we underline 5 and cross out 10, 15, 20, We continue like this. until every integer in the list is either underlined or crossed out. At each stage, the first integer which is neither underlined nor crossed out must be prime, for otherwise it would have been crossed out, as a proper multiple of an earlier prime; thus only primes are underlined, and conversely, each prime in the list is eventually underlined at some stage, so when the process terminates the underlined numbers are precisely the primes $p≤ N$. (We can actually stop earlier, when the proper multiples of all the primes $p≤ \sqrt{N}$ have been crossed out/ This implies that every remaining integer in the list must be prime because an integer $n>1$ is composite if and only if it is divisible by some prime $p \le \sqrt{n}$).

Python Code

from sympy import sieve
print([i for i in sieve.primerange(7, 19)])

[7, 11, 13, 17]

Factorization

In number theory, the factorization problem refers to the task of finding the prime factors of a given integer. For example, given the number 60, the factorization problem seeks to express it as the product of prime numbers: $60=2×2×3×5$.

In theory we would factorize any integer $n$ by testing it for the divisibility by the primes $2,3,5\ldots$, until a prime factor $p$ is found; we then replace $n$ with $n/p$ and continue this process until a prime factor $n/p$ is found'eventually, we obtain all the prime factors of $n$, with their multiplicities.

The difficulty of the factorization problem is closely related to the size of the numbers involved. For small numbers, factorization can be done relatively quickly using trial division or other elementary methods. However, as the numbers get larger, the problem becomes increasingly difficult.

The hardness of the factorization problem forms the basis for several cryptographic systems, most notably RSA encryption. RSA encryption relies on the assumption that it is computationally infeasible to factorize large composite numbers into their prime factors. There is no known polynomial-time algorithm for factoring large integers, and the problem is considered to be in the class of NP (nondeterministic polynomial time) problems.

Efficient algorithms for factorization, such as the General Number Field Sieve (GNFS), have been developed, but they are still impractical for factoring very large numbers. The security of RSA and other cryptographic systems depends on the difficulty of the factorization problem, making it crucial for secure communication and data encryption.


Comments

Post a Comment

Popular posts from this blog

Number Theory CST 292 KTU IV Semester Honors Course Notes Dr Binu V P 9847390760

About me Syllabus Scheme Teaching Plan Model Question Paper University Question Papers Assignment-1 Module-1  Introduction Well ordering principle Group Ring Fields Group Ring Fields in detail Divisibility Modular Arithmetic GCD- Euclidean Algorithm Bezout's Identity Extended Euclidean Algorithm LCM-Least Common Multiple Linear Diophantine Equations Modular Division Module-II Prime Numbers and Prime-Power Factorisation Fermat and Mersenne Prime Primality Testing and Factorization Miller Rabin Primality Testing Algorithm Fermat  Factorization Congruence Modular Exponentiation Linear Congruences Simultaneous Linear Congruences- Chinese Remainder Theorem Fermat's Little Theorem and Euler's Theorem Wilson's Theorem Module-III Congruence with Prime modulus Congruence with Prime power modulus Pseudoprime and Carmichael Numbers Euler's Totient Function Cryptography The Group of Units - Primitive Roots Module-IV Quadratic Residues-Legendre and Jacobi Symbols Arithmetic Func
Read more

Sum of Squares

Image
In this our aim is to determine which integers can be expressed as the sum of given number of squares ie; which have the form $x_1^2+x_2^2+\cdots+x_k^2$, where each $x_i \in \mathbb{Z}$, for a given $k$. Definition: For each integer $k \ge 1$, let $S_k=\{n|n=x_1^2+x_2^2+\cdots+x_k^2$ for some $x_1,x_2,\ldots,x_k \in \mathbb{Z} \}$ , the set of all sum of $k$ squares. Example: $S_1=\{0,1,4,9,\ldots\}$ is the set of all squares. By inspection $S_2$, the set of sum of two squares contains 0,1,2,4,5 and 8 but not 3,6, or 7. Lemma: The set $S_2$ contains, the sum of two squares is closed under multiplication ie; if $s,t \in S_2$ , then $st \in S_2$. Proof:Let $s=a_1^2+b_1^2$ and $t=a_2^2+b_2^2$ be the elements of $S_2$, where $a_1,b_1,a_2,b_2 \in \mathbb{Z}$. Then the identity $$(a_1^2+b_1^2)(a_2^2+b_2^2)=(a_1a_2-b_1b_2)^2+(a_1b_2+b_1a_2)^2$$ This shows that $st \in S_2$ Example: We have $8=2^2+2^2$ and $10=3^2+1^2$ so $8.10=80=(2.3-2.1)^2+(2.1+2.3)^2=4^2+8^2$ Note: an equivalent ident
Read more

Quadratic Residues-Legendre and Jacobi Symbols

Image
Quadratic Congruence   There is a general question whether an integer $a$ has a square root $\pmod{n}$ and if so, how many are there and how one can find them. We know that the solution of the quadratic equation can be found by  $$x=\frac{-b \pm \sqrt{b^2-4ac}}{2a}$$ If we want to apply this to the case where $a,b,c \in Z_n$, then $2a$ to be unit in $\pmod{n}$, so that we can divide by $2a$. We can write the equation in the form $$(2ax+b)^2=b^2-4ac$$ If we can find all the square roots $s$ of $b^2-4ac$ in $\mathbb{Z}_n$, we can then find all the solutions $x \in \mathbb{Z}_n$ of the quadratic equation of the form $2ax+b=s$, or equivalently $x=(s-b)/2a$. If we look at the square roots at $\mathbb{Z}_{15}$, then  1 and 4 have four square roots each($\pm 1 ,\pm 4$ and $\pm 2,\pm 7$ respectively, while the other units have none. Example: Find all the solutions of $x^2-3x+2 \equiv 0 \pmod{15}$ given $a=1, b=−3$ and $c=2,$ we have: $b^2−4ac=(−3)^2−4(1)(2)=9−8=1$ So, $b^2−4ac=1.$ Now, we ne
Read more