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