Algorithms of primality testing – implementation in PythonCONTENTS1.
Introduction1.1 Method of Implementation 1.2 Literature Survey 1.3 Objective2.
Primality Testing 2.1 Problem Statement 2.2 Previous Works 2.3 Probabilistic Primality Tests 2.
4 Deterministic Primality Tests3. Types of Primality Testing 3.1 Fermat’s Primality Testing 3.2 Miller Rabin Primality Testing 3.3 Solovay Strassen Primality TestingIntroductionTo satisfy the speed of communication and to meet the demand for the continuously larger prime numbers, the primality testing and prime numbers generating algorithms require continuous advancement. To find the most efficient algorithm, a need for a survey of methods arises. Concurrently, an urge for the analysis of algorithms performances emanates.
The critical criteria in the analysis of the prime numbers generation are the number of probes, number of generated primes, and an average time required in producing one prime. Hence, the purpose of this thesis is to indicate the best performing algorithm. The survey the methods, establishment of the comparison criteria, and comparison of approaches are the required steps to find the best performing algorithm.Method of ImplementationThe programs were installed on the Windows operating system, running on the Python 3.
4 to perform the computer experiments. The computer experiments results pertaining to the selected algorithms, provided required parameters to compare the algorithms performances. The results from the computer experiments were tabulated to compare the parameters and to indicate the best performing algorithm.Literature SurveySurvey of methods indicated that the deterministic and randomized are the main approaches in prime numbers generation. Random number generation found application in the cryptographic keys generation. Contemporaneously, a need for deterministically generated provable primes emerged in the code encryption, decryption, and in the other cryptographic areas.
The analysis of algorithms performances indicated that the prime numbers generated through the randomized techniques required smaller number of probes. This is due to the method that eliminates the non-primes in the initial step that pre-tests randomly generated primes for possible divisibility factors. Analysis indicated that the smaller number of probes increases algorithm’s efficiency.
Further analysis indicated that a ratio of randomly generated primes to the expected number of primes, generated in the specific interval is smaller than the deterministically generated primes. In this comparison the Miller-Rabin’s and the Gordon’s algorithms that randomly generate primes were compared versus the SFA and the Sequences Containing Primes. The name Sequences Containing Primes algorithm is abbreviated in this thesis as 6kseq. In the interval 99000, 100000 the Miller Rabin method generated 57 out of 87 expected primes, the SFA algorithm generated 83 out of 87 approximated primes.
The expected number of primes was computed using the approximation n/ ln (n) presented by Menezes. The average consumed time of originating one prime in the 99000, 100000 interval recorded 0.056 s for Miller-Rabin test, 0.0001 s for SFA, and 0.0003 s for 6kseq. The Gordon’s algorithm in the interval 1, 100000 required 100578 probes and generated 32 out of 8686 expected number of primes.Algorithm Parametric Representation of Composite Twins and Generation of Prime and Quasi Prime Numbers invented by Doctor Verkhovsky verifies and generates primes and quasi primes using special mathematical constructs.
This algorithm indicated best performance in the interval 1, 1000 generating and verifying 3585 variances of provable primes or quasi primes. The Parametric Representation of Composite Twins algorithm consumed an average time per prime, or quasi prime of 0.0022315 s. TheParametric Representation of Composite Twins and Generation of Prime and QuasiPrime Numbers algorithm implements very unique method of testing both primes and quasi-primes. Because of the uniqueness of the method that verifies both primes and quasi-primes, this algorithm cannot be compared with the other primality testing or prime numbers generating algorithms.
ObjectiveThe objective of this thesis is to survey the methods for primality testing, for generating prime numbers, to compare the efficiency of selected algorithms, and indicate the best performing algorithm. Initially this paper will review, survey, and compare different approaches. In the next step the performance of algorithms will be tested through the series of computer experiments. Uniformly designed computer programs will test algorithms in the specified interval smallest, largest and report the number of probes, number of generated primes, CPU time, and the average time required to generate one prime in the specified interval. Results obtained from the computer experiments will serve to compare the efficiency of algorithms in the specified interval using the time complexity, number of probes, and -number of generated primes as comparison criteria. The most efficient algorithm will be indicated from the tabulated results furnished in the form of comparison tables.PRIMALITY TESTING ALGORITHMSProblem StatementA.
J. Menezes, 66 classified algorithms for primality testing and provided fundamental details pertaining to the presented algorithms. New algorithmic ideas have been emerged and have been implemented since the Menezes book was published. Thus, using Menezes classification in this chapter the algorithms will be sorted, placed into appropriate categories, and compared, to indicate the best performing algorithm. The time complexity, the number of generated primes, and the number of probes will be used in the comparison criteria to indicate the most efficient algorithm.
Previous WorkMenezes delineated generalized framework for Probabilistic Primality Testing, which is included in the Appendix A. Probabilistic approaches for primality testing are exemplified in the Fermat, Solovay-Strassen, and Miller-Rabin methods.Menezes summarized the properties of Probabilistic Primality Tests in the general form, that for each odd positive integer n a set W(n) is a proper subset of Z. such that the listed properties hold. The number a, that is an element of Z.
can be defined in the deterministic polynomial time if the number a is an element of W(n). If number n is a prime, then the set is empty and W(n) is equal to 0. If the number n is a composite, then an element in W(n) is greater or equal to number n divided by 2. If the number n is a composite, then the elements of W(n) are called witnesses to the compositeness of n, and the elements of the complementary set L(n) that are equal to Z..
in W(n) are called liars.An element a of Zn is chosen at random, and it is tested if a belongs to the W(n) subset.The test will output composite if a is an element of W(n), and will output prime if a does not belong to subset W(n). Menezes defines an integer n as a probable prime, if based upon a probabilistic primality test the number n is believed to be a prime.Probabilistic Primality TestsThe Fermat’s theorem referenced in Menezes upholds, if the number n is a prime and the number a is an integer, such that a is greater than or equal to 1, but smaller than or equal to n-1, then a^ (n-1) will be equal to 1 (mod n). The Fermat’s theorem endorses, that the odd, composite integer n is called Fermat’s witness to compositeness for n, if an odd composite integer a is a pseudo-prime to the base a, and if the number a raised to the power of n-1 is equal to 1 (mod n), then the integer a is called Fermat’s liar to primality for n.The Solovay-Strassen Test outlined in Menezes implements Euler’s criterion.
In this algorithm the number n is an odd prime and the number a raised to the power of(n-1) divided by 2 is equal to (a/n) mod n for all integers a, that satisfy the gcd (a,n) equal to 1. The quotient (n / a) denotes a Jacobi symbol and (n / a) is equal to Legendre symbol if n is a prime. The number a is called Euler witness for compositeness if a satisfies one of the following categories. If n is an odd composite integer and a is an integer in the interval 1, n-1, then the number a is Euler’s witness for compositeness. If gcd (a, n) is greater than 1, or if the number a raised to the exponent (n-1)/2, is not equal to (a/n) mod n, then the number n is called Euler’s pseudo-prime to the base a. The number n is called Euler’s pseudo-prime to the base a only, if gcd (a, n) is equal to 1, and if a raised to the power (n – 1)/2 is equal to (a/n) mod n. If n is an odd composite integer, then (1)(n)/2 for all the numbers a, are called Euler’s liars where a is defined by 1, n-1.
The Miller-Rabin probabilistic primality test presented in Menezes is considered to be a strong pseudo-prime test. In this delineation n is an odd prime and n-1 is equal to 2 to the power of s and multiplied by r, where r is an odd integer. If gcd (a, n) is equal 1, then base a raised to the power of r is equal to 1 (mod n) or for j in the range of 0, s-1 base a raised to the power of 2^j and multiplied by r is equal to -1 (mod n). The number n is called a strong pseudo-prime to the base a, if a raised to the exponent r is not equal to 1 (mod n), or a raised to the power of (2^j)*r is not equal to -1 (mod n), for all j numbers in the range of 0,s-1. The integer a is also called a strong liar to primality for n.
Base a raised to the power of r is equal to 1 (mod n). Base a raised to the power of (2^j)*r is equal to -1 (mod n). If n is not equal to 0, then the number of strong liars for n is equal to 4(n)/4. If n is an odd composite integer, then 1/4 of all the numbers a that refer to 1,n-1 are strong liars for n.Deterministic Primality TestsFrom many different deterministic primality testing algorithms the best one (so far unique with proved polynomial complexity) is AKS algorithm.In August 2002, Agrawal, Kawal and Saxena made public their deterministic, polynomial-time algorithm for primality testing withO((log n)12 )computational complexity. It is worthto underline the AKS algorithm is unconditionally correct. It means that it is not based on unproved hypothesis like for example GRH (Generalized Riemann Hypothesis).
AKS test 15 is considered to be the first deterministic, unconditional (correct) algorithm to establish the primality for a given number with a polynomial run time. Though many algorithms existed, they were probabilistic or they had a running time slower than polynomial.The test provides a witness of primality for any prime input number. The AKS testtakes O((log n)6 )time to check if an n-bit number is a prime. In the original version it wasO((log n)12 ) , which means that the exponent depends on the version that is being used. Unfortunately, because of the high level complexity when implementing this algorithm in hardware and software, probabilistic tests are still being used.
The AKS algorithm is based on the following simple theorem.Theorem 2.4.1If a, n ? N , n ? 2 and GCD(a, n) ? 1 then n is a prime if and only if(x ? a)n ? (xn ? a)(mod n)where congruence of polynomials modulo n means in the above theorem that left side andright side polynomials after reduction of coefficients (by powers x j ) ) modulo n are even.
The above theorem can be treated as generalization of the small Fermat theorem.3. TYPES OF PRIMALITY TESTING 3.1 Fermat’s TestThe Fermat’s algorithm for primality testing (in short Fermat’s test) is based on the following theorem called the first (or little) Fermat’s theorem.Theorem 3.
1.1 (Fermat’s little theorem)If p is a prime number and a is an integer which is relatively prime to p then,(3.1)Proof. The Fermat little theorem is a direct conclusion from the following Euler’s theorem.?Theorem 3.
1.2 (Euler’s theorem)If and a is an integer which is relatively prime to n (i.e. ) then(3.2)where is a the Euler’s function defined in the following way: , and for every : .Proof. The Euler’s theorem is a direct conclusion from the following simple theorem from group theory.
?Theorem 3.1.3If G is a finite group then for every element we have .Proof. If denotes order of the element a then set of powers is a subgroup of G and .
Then from the Lagrange theorem from group theory we have that divides . Then divides i.e. there is a integer that but then also .
?Corollary 3.1.4 If , , , and a congruence is not fulfilled then n is not a prime (then it is a composite number). In the above corollary the assumption can be omitted, because if then the corollary thesis is of course fulfilled. Hence we can formulate our corollary 3.
1.4 in the following way.Corollary 3,1.5 If , , and a congruence is not fulfilled then n is not a prime (then it is a composite number). Hence we have obtained a criterion on which can be based a primality test. Such an algorithm is called the Fermat primality test and is shown on the Fig.3.1.
1. Of course even numbers n greater than 2 are not primes then the we can assume that we test only odd numbers. It is worth to notice, that if for an integer we have then of course we have , where denotes the remaider after division by n. More strictly for every : if and only if . Hence we can verify in the Fermat test only bases . In the Fermat primality test, the congruence have to be verified only for bases . Indeed, because and tested natural number n is odd then we have always .
For the given odd n, we don’t need to test such a basis that because in this situation n is not a prime. It is easy to verify that in this situation the congruence is not true. Then our criterion correctly detects the situation when .
Pseudo Code of Fermat’s Primality Testing:Repeat for K times:Pick a number ‘a’ randomly in the range 2, (n-2) If a^(n-1) !? 1 ( mod n), then return compositeReturn probably primeProof:Fermat’s Little theorem states- if n is prime and a is not divisible by n then,a^(n-1) ? 1 ( mod n)Proof of Fermat’s little theorem: If n is not prime then it has a divisor d ; 1. The number d^(n?1) is divisible by d so it is not equal to 1 mod n. If n is prime, let A be the set of integers x which satisfy x^n ? x (mod n). This set contains x = 1, and it is closed under addition and subtraction. Hence every integer x belongs to A. Now let x by any integer not divisible by n. The fact that x ? A means that n | x^n ? x = x(x^(n?1) ? 1). Since n is prime and x is indivisible by n, this implies n | x^(n?1) ? 1, i.
e. x^n?1 ? 1 (mod n).So if we want to test n is prime, then we can pick random number a which is not divisible by n and see whether the property above stated holds. If for a value of ‘a’ the equality does not hold then the number n is composite.After a certain amount of trial (K times) if all the times the equality holds then we state the number n is probably prime. Time Complexity:The computational complexity of this algorithm is O(k × log2n).
The factor K is for how many trials are we running.To compute an-1 one can use repeated squaring and multiplication, which requires one or two modular multiplications per bit of n. As the number of bits is log n , we get a factor of log n.
A modular multiplication can be done by adding up to logn bit shifted copies of a factor. Each addition uses at most twice as many bits as n has, so takes O(logn) steps; the reduction modulo n might for example be done by using logn pre computed values, one for each of the “higher” bits. At least this does not hurt the O(log n) for the addition.
If the Fermat test returns the answer “n is a composite number” then for sure n is a composite number. If the Fermat test returns the answer „n is a prime number” then it can be a mistake. The tested number n can efficiently “pretend” a prime i.e.
more strictly a odd composite number n can for fixed fulfill a congruence . Coding:__author__ = ‘Anand’from random import randintfrom datetime import datetimefrom timeit import default_timer as timer#function for calculating (x^y)%mod#for efficiency we will use BigMod Algorithm heredef powerWithMod(x,y,mod): res = 1; x%=mod; while y>0: if (y%2)==1: res=(res*x)%mod; y=y>>1; #y=y/2 x=(x*x)%mod; return res;def fermatAlgorithm(n,k): #this three are base cases. if(n==1): return 0; if(n==2): return 1; if(n==3): return 1; for i in range(k): a=randint(0,n-4)+2; # to generate a random value in 2,n-2 # print(a) res=powerWithMod(a,n-1,n)%n; if res !=1: return 0; return 1;if __name__== “__main__”: print(“Menu:
1.
Print All Probable Prime in a Range
2.Check if a number is Probable Prime
3.Check an exponent ( X^n format)
4.End”) while True: print(“Enter choice: “); choice=int(input()); if choice==1: print(“Enter a Range: “); r=int(input()); print(“Enter value of K:”); k=int(input()); start=timer() for i in range(r): if fermatAlgorithm(i+1,k): print(str(i+1)+” “); elif choice==2: print(“Enter a number: “); n=int(input()); print(“Enter value of K:”); k=int(input()); start=timer() if fermatAlgorithm(n,k): print(str(n)+” is Probably Prime
“); else: print(str(n)+” is Composite
“); elif choice==3: print(“Enter X: “); x=int(input()); print(“Enter n: “); n=int(input()); print(“Enter k: “); k=int(input()); n=x**(n); start=timer() if fermatAlgorithm(n,k): print(str(n)+” is Probably Prime
“); else: print(str(n)+” is Composite
“); else: break; elapsedTime=timer()-start; print(“Time taken for this operation : “, str(elapsedTime),”Seconds”)Output:Menu:1.Print All Probable Prime in a Range2.
Check if a number is Probable Prime3.Check an exponent ( X^n format)4.EndEnter choice: 2Enter a number: 9871563Enter value of K:45239871563 is CompositeTime taken for this operation : 0.
0001331358024691358 Seconds3.2 Miller Rabin Primality TestThe Fermat primality test has an evident drawback. Every Carmichael number is assessed as a prime.
But the Fermat primality test can be easily improved. Such a improved version of the Fermat primality test is called the Miller-Rabin primality test. In practice the most useful probabilistic primality test is the Miller-Rabin test which is also known as strong pseudoprime test. Assume, and p is a prime and . Then we have to have or . It is a crucial fact for the Miller-Rabin algorithm.
In the sequel it will be referenced as property #1. The second important element of the algorithm are so called strong pseudoprime numbers to a basis a.The thesis of the following theorem give a simple criterion of primality.Theorem 3.2.
1If a number is an odd prime and , where , and d is odd then for every , there is that we have or .Proof. 1. If there is for which then and. Hence if p is a prime then we have or (property #1). 2.
If p is a prime fulfilling assumptions of the above theorem then from the small Fermat theorem we have: i.e. . Using the point #1 (i.e.
property #1) to a congruence: , we obtain, that or . If then the thesis of our theorem is fulfilled. If and then the thesis of our theorem is fulfilled. If and then we can use again the point #1. Hence after at most k steps we obtain a congruence fulfilling the thesis of the theorem.
?Remark. In particular the above theorem is fulfilled for every basis .The above theorem motivates the following definition.Definition 3.
2.1 (a strong pseudoprime number to basis a) Assume is an odd composite number and , where and d is odd and. Assume additionally that the basis fulfills the condition and .
A number n is called a strong pseudoprime to basis a , if or there is that: . The integer a is called a strong liar to primality for n.Remark.
Of course if n is a strong pseudoprime to basis a, then . Assumption that n and a are coprime (i.e. ) in the above standard definition is in fact not necessary because if then the congruence is not fulfilled in this case and n cannot be a strong pseudoprime to basis a. From definition, a prime is not a strong pseudoprime (from definition a strong pseudoprime is an odd composite number) but the theorem 3.2.1 says that every odd prime number fulfills the condition from definition of a strong pseudoprime number.Definition 3.
2.2 (a strong witness to compositness for n) Assume is an odd composite number and , where and d is odd and. Assume additionally that the basis fulfills the condition . If and for every we have then a is called a strong witness to compositeness for n.Example 3.2.1 Consider a number . It is a composite integer.
Because then s=1 and r=45. Since then 91 is a strong pseudoprime to base 9. For 91 the set of all strong liars to primality is the following:{1,9,10,12,16,17,22,20,38,53,62,69,74,75,79,81,82,90}Note that there are exactly 18 strong liars (to primality) for 91 and we have where is the Euler function . ?Example 3.
2.2 The only strong liars to primality for a composite integer are 1 and 104. More generally, if and n is a product of the first k odd primes then there are only two strong liars to primality for n, namely 1 and n-1. ?Theorem 3.3.2If a number is an odd composite number then the number n is strong pseudoprime to basis a for at most ¼ all basis . If a number is odd composite number and then the number n is strong pseudoprime to basis a, where for at most numbers from the set , where is the Euler function.Proof.
see N. Koblitz xx i V. Shoup xx. ?From the above theorem it follows that for strong pseudoprimes there is no equivalent of Carmichael numbers. If we have a tested number in common binary notation then we can easily assess if n is even or odd. It is sufficient to verify the LSB of n if n is odd the LSB is equal to 1 if n is even the LSB is equal to 0, The Miller–Rabin algorithm is given in the fig.
3.2.1.
For simplicity reason we assume that the input data are odd numbers _________________________________________________________________________________Algorithm: Miller–Rabin primality test ; the first version of the Miller-Rabin algorithmMiller–Rabin (n, t) _________________________________________________________________________________Input data: tested odd natural number and security parameter defining probability of error consisting in decision „tested number n is a prime”, when in fact it is a composite numberOutput data: answer „ n is a composite number” or „n is a prime” (a probable prime)___________________________________________________________________________1.write down a number in the form: , where and r is an odd number. 2.for to t do beginchoose at random a number ;; (using an algorithm of fast raising to a power modulo n) if and then beginwhileand do begin ;if then return(„ n is a composite number”); ; endif then return( „ n is a composite number”) end end3.
return(„ n is a prime”) ___________________________________________________________________________Fig.. 3.2.1 Miller-Rabin primality test (the first version, “bottom to up”) __________________________________________________________________________________Algorithm: Miller–Rabin primality test ; the second version of the Miller-Rabin algorithm,Miller–Rabin (n, t) ___________________________________________________________________________Input data: tested odd natural number and security parameter defining probability of error consisting in decision „tested number n is a prime”, when in fact it is a composite numberOutput data: answer „ n is a composite number” or „n is a prime” (a probable prime)___________________________________________________________________________1.write down a number in the form: , where and r is an odd number. 2.
for to t do begin2,1 choose at random a number ;2.4 while begin2.5 (using an algorithm of fast raising to a power modulo n) if and then return („n is a composite number”)if then else begin ; endend end3.return(„ n is a prime”) _______________________________________________________________________________Fig.. 3.
2.2 Miller-Rabin primality test (the second version “up to bottom”) Correctness of the Miller-Rabin algorithm If the input number n of the algorithm is a prime and then according to the property #1 it behaves always like a a strong pseudoprime number and it is independent of the chosen basis .If the input number n of the algorithm is a composite odd number then according to the theorem 3.2.2 for at most ¼ of all basis the number n is a strong pseudoprime.
If we assume that we choose a basis a with a uniform probability distributions then probability of the correct compositeness detection (in one experiment) is and the probability of failure is . But the experiment of choosing a basis with a uniform probability distribution on is repeated t times in independent way. Then the probability of compositeness detection failure after t experiments is .For large t for example we are sure from practical point of view that the tested numbern is a prime.
Definition 3.2.3 Let denotes the first t primes. Then is defined to be the smallest positive composite integer which is strong pseudoprime to all bases . The numbers can interrupted as follows: to determine the primality of any odd positive integer it is sufficient to apply the Miller-Rabin algorithm to n with bases a being the first t prime numbers. With this choice of bases, answers returned by the Miller-Rabin algorithm are always correct. Table from the fig. 3.
2.3 gives value of for . The essence of the algorithm consists on verification if for basis the tested odd number n behaves like a strong pseudoprime. A prime behaves always (for consecutive t independent experiments consisting on randomly choosing a basis ) as a strong pseudoprime. A composite number n behaves as a strong pseudoprime number (for all independent t experiments of choosing basis at random with uniform probability) with probabilisty less even than . Hence probability of „fault” (i.e.
acceptance of a composite number as a prime) is for large t negligible small.t 1 20472 13736533 253260014 32150317515 21523028987476 34747496603837 3415500717283218 341550071728321Fig. 3.2.3 Smallest strong pseudoprimes Computational complexity of the Miller-Rabin algorithmIf we assume that the multiplication modulo n is a basic operation in the algorithm then a computational complexity of the Miller-Rabin algorithm is equal to . The Miller-Rabin algorithm is a classical example of the so called probabilistic algorithm. As a rule probabilistic algorithms are much faster than deterministic ones solving the same problem but in the case of probabilistic algorithms the answer can be with usually very small probability false. In the case of the Miller-Rabin algorithm the answer “n is a composite number” is quite correct but the answer “n is a prime” can be false with probability less even than where is a so called security parameter which is equal to number of experiments (repetitions of the algorithm).
Deterministic version of the Miller-Rabin algorithm There is a deterministic version of the Miller-Rabin algorithm based on the Generalized Riemann Hypothesis. It is based on the following theorem.Theorem 3.2.
3If GRH hypothesis is true and is odd composite number then the least basis a detecting compositeness in the Miller-Rabin algorithm is (i.e the least so called strong witness of compositeness) is less than .Corrollary 3.
2.4It is possibile to verify primality of an odd number n executing the Miller-Rabin algorithm for every basis . It gives a deterministic version of the Miller-Rabin algorithm which is correct under assumption that the GRH is true. It can be proved that the computational complexity of the deterministic version of the Miller-Rabin algorithm is equal to (of bit operations). Hence the algorithm has polynomial complexity.Pseudo-Code of Miller-Rabin Test:Express n-1 as d*(2^r) with d where d is oddfor k times do:pick a random integer a in the range 2 , (n-2)x = a^d mod nif x = 1 or x = n-1 thencontinue to the next iteration of this loopfor (r-1) times do:x = (x*x) mod nif x = 1 thenreturn compositeif x = n-1 thencontinue to the next iteration of the outer loopreturn compositereturn probably primeProof:The Miller Rabin test is based on the following property to prove that a number is composite-If we can exhibit a number x satisfying x^2 ? 1 (mod n) but x !? ±1 (mod n) then the number is compositeThis lemma implies that n is a divisor of x^2-1= (x+1) * (x-1), but n divides neither (x+1) nor (x-1). This is impossible when n is prime.
Now let n be prime greater than 2. So we are sure to say (n-1) is even and can be written as d*(2^s), where s and d is integer and d is odd. So there can be two cases-a^d ? 1 (mod n) , or a^(d*2^r) ? -1 (mod n)for some 0<= r <=(s-1)To show either of these are true we can recall Fermat’s Little theorem- For a prime number n: a^(n-1) ? 1 ( mod n)Proof of Fermat’s little theorem: If n is not prime then it has a divisor d > 1. The number d^(n?1) is divisible by d so it is not equal to 1 mod n. If n is prime, let A be the set of integers x which satisfy x^n ? x (mod n).
This set contains x = 1, and it is closed under addition and subtraction. Hence every integer x belongs to A. Now let x by any integer not divisible by n. The fact that x ? A means that n | x^n ? x = x(x^(n?1) ? 1). Since n is prime and x is indivisible by n, this implies n | x^(n?1) ? 1, i.e.
x^n?1 ? 1 (mod n).So as we proved earlier, if we keep taking square roots of a^(n-1) , we will get 1 or -1. If we get -1 the second of the above equality stands and we are done. If we never get -1, then we are left with the first equality.The Miller Rabin test primality test is based on the contrapositive of the above claim. That is for all 0<=r<=(s-1) , the above two equality is not stands, then n is not prime.
For the test, we choose a. Every odd composite n has many witnesses a, however, no simple way of generating such an a is known. The solution is to make the test probabilistic: we choose a non-zero a in Z/nZ randomly, and check whether or not it is a witness for the compositeness of n. If n is composite, most of the choices for a will be witnesses, and the test will detect n as composite with high probability. There is, nevertheless, a small chance that we are unlucky and hit an a which is a strong liar for n. We may reduce the probability of such error by repeating the test for several independently chosen a. That is the role of K. the more the value of K, the more accurate the result would be.
Time Complexity:In step (2-b) and (2-d-i) , if we use modular exponentiation by repeated squaring, then running time will be to compute each step O(log2(n)). Also in step (2-d), the loop runs (r-1) times. The value of r can be in worst case log(n). So the running time of the algorithm for one trial will be O( log3n). As we are taking K trials so ultimately the running time for this algorithm will be O(k log3n) .Coding__author__ = ‘Anand’from random import randintimport timefrom datetime import datetimefrom timeit import default_timer as timer#function for calculating (x^y)%mod#for efficiency we will use BigMod Algorithm heredef powerWithMod(x,y,mod): res = 1; x%=mod; while y>0: if (y%2)==1: res=(res*x)%mod; y=y>>1; #y=y/2 x=(x*x)%mod; return res;def isPrime(n,k): #handle some corner cases first if n<=1 or n==4: return False; if n<=3: return True; #find d for some r>0 such that n-1 = d*2^r d=n-1; while d%2==0: d//=2; #run miler test on number n, total k times for i in range(k): if millerTest(n,d)==False: return False; return True;def millerTest(n,d): #pick a randome number in range2,n-2 a=randint(0,n-4)+2; #compute (a^d)%n temp=powerWithMod(a,d,n); if temp==1 or temp==n-1: return True; #iterate by squaring x while conditions met while d<=(n-1): temp=powerWithMod(temp,2,n); d=d*2; if temp==1: return False; if temp==n-1: return True; return False;if __name__== “__main__”: print(“Menu:
1.Print All Probable Prime in a Range
2.
Check if a number is Probable Prime
3.Check an exponent ( X^n format)
4.End”) while True: print(“Enter choice: “); choice=int(input()); if choice==1: print(“Enter a Range: “); r=int(input()); print(“Enter value of K:”); k=int(input()); start=timer() for i in range(r): if isPrime(i+1,k): print(str(i+1)+” “); elif choice==2: print(“Enter a number: “); n=int(input()); print(“Enter value of K:”); k=int(input()); start=timer() if isPrime(n,k): print(str(n)+” is Probably Prime
“); else: print(str(n)+” is Composite
“); elif choice==3: print(“Enter X: “); x=int(input()); print(“Enter n: “); n=int(input()); print(“Enter k: “); k=int(input()); n=x**(n); start=timer() if isPrime(n,k): print(str(n)+” is Probably Prime
“); else: print(str(n)+” is Composite
“); else: break; elapsedTime=timer()-start; print(“Time taken for this operation : “, str(elapsedTime),”Seconds”) Output:Menu:1. Print All Probable Prime in a Range2. Check if a number is Probable Prime3. Check an exponent ( X^n format)4.
EndEnter choice: 2Enter a number: 547562345Enter value of K:2345547562345 is CompositeTime taken for this operation: 0.0001477530864197531 Seconds3.3 Solovay-Strassen algorithm A Solovay-Strassen algorithm is a probabilistic algorithm for primality testing. Description of the algorithm is given in the Fig. 3.3.
1. Correctness of the algorithm is a direct conclusion from the following six theorems 3.3.
1-3.3.6.
Theorem 3.3.11.A set with multiplication taken from the set of integers is a group.
2. If then a set with multiplication modulo n is a group and is a subgroup of a multiplicative group .3. A map defined by the formula: , is an isomorphism of groups and . Proof. Ad 1. To prove, that is a group it is sufficient to verify if the set is closed for defined multiplication and the group axioms are fulfilled. Ad 2.
In similar way we verify if the set is closed for multiplication modulo n. For we can easily verify, that . Group axioms can be verified like in the point 1. We have and and . Indeed, if it would be: then there are such , , , that and . Then we have, that but it is not possible. Therefore we come to the conclusion that then we have . Then indeed .
is a subgroup of the multiplicative group , it follows from the fact, that the set is finite and closed under multiplication modulo n.Ad 3.The fact that the map defined by the formula: , is an isomorphism of the group and follows from simple verification: ?Theorem 3.3.2If is an odd natural number then a map is a homomorphism of the multiplicative group into the multiplicative group . Raising to a power in is done in the multiplicative group (in equivalent way can be written as , if raising to a power is done in the ring of integers Z).
2. a map , (where denotes a Jacobi symbol), is a homomorphism of the multiplicative group into a multiplicative group .Proof.
Ad 1. We have to show, that for every we have . Indeed the multiplicative group is an Abelian one then:Then is an endomorphism of the group .Ad 2. In general the Jacobi symbol can take values from the set . Because the map has arguments a from the set then we have and values of the function belong to the set . It follows from the theorem 1 that the set is a group with the multiplication from the ring of integers. The Jacobi symbol has the following property: for every we have , thenHence is a homomorphism of the group into the group .
Theorem 3.3.3Assume G is a finite group, H an arbitrary group and and are two homomorphisms. If there is an element a of the group G, that then homomorphisms and are different in at least points.Remark.
Intuition behind the above theorem is the following. Two homomorphisms defined on the finite group can be the same homomorphism or be “very different” .Proof. Let’s define a set . The set is closed under multiplication. Indeed if we have elements , and then , and therefore we obtain .
If a subset of the finite group is closed under multiplication then it is a subgroup of this group. Therefore is a subgroup of the finite group G. The group is a proper subgroup of the group G because there is such a element a of the group G , that , then . It follows from the Lagrange theorem (from group theory) that is a divisor of . But then . It means, that two homomorphisms and are different in at least points. Theorem 3.
3.4If a number is an odd natural number then:a number n is prime if and only if, for every we have (3.3.1)where is a Jacobi symbol. If denotes raising to a power in the multiplicative group then the congruence (*) can be written as an equality: .
Proof. 1.Implication right it is so called the Euler criterion. To prove the above implication left it is sufficient to show, that if n is not a prime then mappings:(3.
3.2)and (3.3.3)are different.
It follows from the theorem 3.3.2 that these two mappings are group homomorphisms. To show, that (3.3.2) and (3.
3.3) are different it is sufficient to find only one such , that 2.At first, consider a case number 1 when n is not a square-free. It means assume that n has such a prime factor p , that divides n. If , where are such primes, that and then the value of the Euler’s function is the following:.
Therefore, if then . The multiplicative group has elements and because then there is a cyclic subgroup of the order p of the multiplicative group . Denote a generator of this subgroup by g.
Hence we have . The value cannot be equal to 1 or (i.e.
), because in this case and we obtain that which gives contradiction (because we cannot have and ). Therefore we can write: . On the other hand it follows from the theorem 3.2.2, that for we have , i.e.
or .Hence we have found such an element , that i.e. the congruence is not fulfilled.3.
Consider now the second case, when n is a composite square-free number i.e. assume, that , where are such primes that: and . Assume, that there is (we can admit for example ) that we have such , thati.
e. the congruence is not fulfilled. In this situation we can easily find such , that: . Indeed from Chinese remainder theorem it follows that there is a standard isomorphism of the ring and a direct sum of rings given by the formula: (which is written in short as ) and additionally the map h constrained to is a standard isomorphism of the multiplicative group and a direct product of groups . Then we have . The value for is a number x written in Residue Number System (RNS notation) with moduli . Choose such an argument , for which the isomorphism h has the value: i.
e. . We obtain now from definition of the Jacobi symbol:Therefore there is such an element , that (g indeed belongs to , because and for every we have ). Because and h is an isomorphism then using definition of multiplication in a direct sum of rings we obtain: (3.3.4)Observe, that oraz (3.
3.5)We have assumed, that the congruence is not fulfilled or equivalently .The value of the Jacobi symbol is even to (see theorem 3.3.2) 1 or -1.
We consider both cases. If then it follows from the inequality , that . From the equations (3.3.5) and (3.3.4) we have, that . Because then .
Hence we have found such , that the congruence is not fulfilled. If then it follows from inequality: , that . Now from equality (3.
3.5) and (3.3.
4) we obtain, that . Because , then . Therefore we have found such , that the congruence: is not fulfilled.4. Consider now the last situation, when n is a square-free composite number i.e. n is such a number, that , where are such primes that and . Assume that for every and every , we havei.
e. the congruence is not fulfilled. Then we have no „start point” as previously. We can find now a quadratic residue modulo i.e. find such , that and a quadratic nonresidue modulo i.e. find such , that . It follows from Chinese remainder theorem, that there is a unique element such that: Raising both sides of the above equality to the power we obtain:But because h is an isomorphism we have in the sequel:Now, it follows from (3.3.5), that is not equal to 1 or (i.e. ). We have found such , that: or equivalently, we have found such , that the congruence is not fulfilled.5. Finally we can say that: if an odd number n is not a prime then in every considered case we find such an element , that or equivalently the congruence is not fulfilled. ?Theorem 3.3.5If is an odd natural composite number then for at least a half of elements from the set is not fulfilled the following congruence (or equivalently ).Proof. 1. From the theorem 2 it follows, that the mapping is a homomorphism of the multiplicative group into the group and the mapping is a homomorphism of the multiplicative group into the group . 2.It follows from the theorem3.3.4, that because n is a odd composite number then for at least one we have .3. From the theorem 3.3.3 and the point 1 it follows that for at least a half of elements from the set we have i.e. for at least a half of elements a from the set the congruence is not fulfilled. Theorem 3.3.6 If n is an odd natural number and a random variable defined on a probabilistic space and with values in the multiplicative (more strictly in a measurable space ) has the uniform probabilisty distribution on thenProof. The above theorem is a direct conclusion from the theorem 3.3.5. ?Hence probability of detection that an odd natural number n is composite by choosing at random a number with the uniform probabilisty distribution and verification if the conguence is not fulfilled is greater even ½.Probabilistic algorithm of primality testing of a natural odd number based on the above remark is called the Solovay-Strasssen algorithm. The Solovay-Strassen algorithm is the following: ___________________________________________________________________________Algorithm: Solovay-Strassen algorithm of primality testing___________________________________________________________________________Input data: An odd natural number and an arbitrary chosen parameter. The parameter t defines probability of the error when we accept a composite number as a prime, . The algorithm answer „the number n is composite” is always true. Output data: Answer if a number n is a composite one or a prime. ___________________________________________________________________________for to t do begin 1.we choose at random a number with the uniform probability distribution on 2. ; // we compute the value of the Jacobi symbol 3. ; // we compute the value 4. if then begin write („the number n is composite”); goto finishing_label end ; // we verify if the congruence: is fulfilledend;write („the number n is a prime”); finishing_label:___________________________________________________________________________Fig. 3.3.1 Solovay-Strassen algorithm of primality testing Coding:__author__ = ‘Anand’from random import randintfrom datetime import datetimefrom timeit import default_timer as timer#function for calculating (x^y)%mod#for efficiency we will use BigMod Algorithm heredef powerWithMod(x,y,mod): res = 1; x%=mod; while y>0: if (y%2)==1: res=(res*x)%mod; y=y>>1; #y=y/2 x=(x*x)%mod; return res;def legendre(a,n): if n<2: raise ValueError(‘Value error’) if (a==0) or (a==1): return a; if a%2==0: r=legendre(a//2,n); if ((n * n)-1) & 8 !=0: r*=-1; else: r=legendre(n%a,a); if (a-1)*(n-1)&4 !=0: r*=-1; return r;def isPrime(n,k): #handle some corner cases first if n<=1 or n==4: return False; if n<=3: return True; for i in range(k): a=randint(2,n-1); x=powerWithMod(a,int((n-1)/2),n) y=legendre(a,n); if(y==0) or (x!=y%n): return False; return True;if __name__== “__main__”: print(“Menu:
1.Print All Probable Prime in a Range
2.Check if a number is Probable Prime
3.Check an exponent ( X^n format)
4.End”) while True: print(“Enter choice: “); choice=int(input()); if choice==1: print(“Enter a Range: “); r=int(input()); print(“Enter value of K:”); k=int(input()); start=timer() for i in range(r): if isPrime(i+1,k): print(str(i+1)+” “); elif choice==2: print(“Enter a number: “); n=int(input()); print(“Enter value of K:”); k=int(input()); start=timer() if isPrime(n,k): print(str(n)+” is Probably Prime
“); else: print(str(n)+” is Composite
“); elif choice==3: print(“Enter X: “); x=int(input()); print(“Enter n: “); n=int(input()); print(“Enter k: “); k=int(input()); n=x**(n); start=timer() if isPrime(n,k): print(str(n)+” is Probably Prime
“); else: print(str(n)+” is Composite
“); else: break; elapsedTime=timer()-start; print(“Time taken for this operation : “, str(elapsedTime),”Seconds”)Output:Menu:1.Print All Probable Prime in a Range2.Check if a number is Probable Prime3.Check an exponent ( X^n format)4.EndEnter choice: 3Enter X: 55Enter n: 55Enter k: 5524744532468751923546122657597368049278513737089035272057324643668607677682302892208099365234375 is CompositeTime taken for this operation : 0.0006076049382706117 SecondsAKS Primality TestingThe AKS Primality Test is an elegant solution to this age old problem that dates back to times of Gauss and Fermat. It is based on the following neat characterization of primes.The Agrawal-Kayal-Saxena (AKS) primality test, discovered in 2002, is the first unconditional, deterministic algorithm to determine the primality of a given number n with a polynomial run time. The algorithm will correctly determine whether that number is prime or not in time . Many previous primality testing algorithms existed, but they were either probabilistic in nature, had a running time slower than polynomial, or the correctness could not be guaranteed without additional hypotheses such as GRH.The AKS algorithm is based on the following simple theorem.Theorem 3.4.1If a, n ? N , n ? 2then n is a prime if and only if(x ? a)n ? (xn ? a)(mod n)(3.4.1)where congruence of polynomials modulo n means in the above theorem that the left side andright side polynomials after reduction of coefficients (by powers x j ) ) modulo n are even.In equivalent way we can formulate the above theorem in the following way.If a, n ? N , n ? 2then n is a prime if and only if in the ring of polynomialsZn x we have(x ? a)n ? xn ? aThe above theorem can be treated as generalization of the small Fermat theorem.Proof. 1.Using the Newton formula for the ringZn we havennn?1 ? n?i n?in(x ? a)? x ? ??? i ?? a x? a(3.4,2)i?1 ? ?If n is a prime then from the first Fermat theorem we obtain that for everyan ? a , where raising to a power is done modulo n .a ? Zn , we haveIf n is a prime p (i.e. n ? p ) then for i ? 1,2,.., p ?1 the number? p ?p !385826011811000?? ?i( p ? i) !?i !??is divisible by p then all coefficients? p ??? aiidlai ? 1,2,.., p ?1are equal to 0 then the??equality (2.3.1) is true.If n is a composite number then there is a prime p which divides n and there are k ? Nandm ? N that we have n ? pk? m and? n ?GCD( p, m) ? 1 . It is easy to show that ??pis notdisable by??pk . Indeed:? n ??? ?pn(n ?1)(n ? 2)…(n ? p ? 1)p !??The numerator of this fraction is divisible bypk but is not divisible by2pk ?1 . On the other? n ?hand the de numerator is divisible by p but is not divisible byp . Hence the number?? isp??k ? n ?not divisible byp . Then we obtain that the number?? is not divisible by n. Indeed, ifp? n ???p?would be divisible by n then it would be divisible by?pk then??? n ??? app (mod n) ? 0??Finally we have that the coefficient by the power xn? pin the polynomialnn?1 ? n?i n?inx ? ?? i ? a x? ai?1 ? ?is different from 0 and the equality(x ? a)n ? xn ? ais not true.In the AKS algorithm description shown in the fig, 3.4.1 we use special notation. Thesymbolor (n)denotesthesmallestnumberksuchthatak ? 1(mod r) .Notationf (x) ? g(x) (mod(xr ?1, n))means that at first we take the remainder of division of thepolynomialf (x) byxr ?1 next we take the remainder of division of the polynomialg(x) byxr ?1andifcoefficientsoftheseremaindersareequalmodulonwewritef (x) ? g(x) (mod(xr ?1, n)) .Theorem 3.4.2The algorithm from the fig. 3.4.1 returns n is prime if and only if n is a prime.Proof. See Agraval, Kayal, Saxena 29.Algorithm. AKS – Agrawal, Kayal, Saxena algorithm of primality testing108077011493500Input data: An natural number n ? N , n ? 1Output data: Answer if a number n is a composite one or a prime.108077011493500if ( n ? ab for a, b ? N, b ? 1) then return (composite) ;3206115180340r00rFind the smallest r such that o (n) ? log 2 n ;if (1 ? GCD(a, n) ? n for some a ? r ) then return (composite)if ( n ? r ) then return (prime)for(a ? 1)to??(r) ? log n?dobeginif((x ? a)n ? xn ? a (mod(xr ?1, n)) ,2764155-23114000return(composite) end; where ? is the Euler functionreturn (prime)107886511938000Fig. 3.4.1 AKS algorithm of primality testingPseudo Code of AKS Primality Testing:Check if n is a perfect power: if n = ab for integers a > 1 and b > 1, output composite.Find the smallest r such that ordr(n) > (log2 n)2. (if r and n are not co-prime, then skip this r)For all 2 ? a ? min(r, n?1), check that a does not divide n: If a|n for some 2 ? a ? min(r, n?1), output composite.If n ? r, output prime.For a = 1 to {displaystyle leftlfloor scriptstyle {{sqrt {varphi (r)}}log _{2}(n)}
ight
floor }floor sqrt( phi(r)) * log2(n) doif (X+a)n? Xn+a (mod Xr ? 1,n), output composite;Output prime.Here, ord(n) is the multiplicative order of n modulo rPhi(r) is the Euler totient function of r Proof of correctness:The AKS primality test is based upon the following theorem: An integer n (? 2) is prime if and only if the polynomial congruence relation(x+a)n equiv. to (xn + a) ( mod n) …………………………… (1)holds for some a coprime to n. Note that x should be understood as a formal symbol.This theorem is a generalization to polynomials of Fermat’s little theorem, and can easily be proven using the binomial theorem together with the following property of the binomial coefficient: equiv. to 0 ( mod n) for all 0<k<n, if and only if n is prime. While the relation (1) constitutes a primality test in itself, verifying it takes exponential time: the brute force approach would require the expansion of the (x – a)n polynomial and a reduction (mod n) of the resulting n + 1 coefficients.The congruence is an equality in the polynomial ring ?nx. Evaluating in a quotient ring of ?nx creates an upper bound for the degree of the polynomials involved. The AKS evaluates the equality in ?nx/(xr – 1), making the computational complexity dependent on the size of r. For clarity, this is expressed as the congruence-( x+ a )n equiv. to ( xn + a ) ( mod xr-1,n) …………………………………. (2)Which is same as:( x+a)n – ( xn +a) = ( xr -1 )g + nf;For some polynomials f and g.All primes satisfy this relation (choosing g = 0 in (3) gives (1), which holds for n prime). This congruence can be checked in polynomial time when r is polynomial to the digits of n. The AKS algorithm evaluates this congruence for a large set of a values, whose size is polynomial to the digits of n. The proof of validity of the AKS algorithm shows that one can find an r and a set of a values with the above properties such that if the congruences hold then n is a power of a prime.For the algorithm to be correct, all steps that identify n must be correct. Steps 1, 3 and 4 are trivially correct, since they are based on direct tests of the divisibility of n. Step 5 is also correct: since (2) is true for any choice of a coprime to n and r if n is prime, an inequality means that n must be composite.The difficult case of the algorithm is step 6. Its proof of correctness is based on the upper and lower bounds of a multiplicative group in ?nx constructed from the (X + a) binomials that are tested in step 5. Step 4 guarantees that these binomials are floor sqrt( phi(r)) * log2(n) distinct elements of ?nx. For the particular choice of r, the bounds produce a contradiction unless n is prime or a power of a prime. Together with the test of step 1, this implies that n is always prime at step 6.Time complexity:In the first version of the above-cited paper, the authors proved the asymptotic time complexity of the algorithm to be O( log(n)12). In other words, the algorithm takes less time than the twelfth power of the number of digits in n times a polylogarithmic (in the number of digits) factor.Coding:import mathimport itertools as ITimport numpy as NPimport fractionsfrom datetime import datetimefrom timeit import default_timer as timerdef ordr(r, n): for k in IT.count(3): if pow(n, k, r) == 1: return k def isqrt(x): if x < 0: raise ValueError(‘square root not defined for negative numbers’) n = int(x) if n == 0: return 0 a, b = divmod(n.bit_length(), 2) x = 2 ** (a + b) while True: y = (x + n // x) // 2 if y >= x: return x x = y def mmultn(a, b, r, n): “”” Dividing by X^r – 1 is equivalent to shifting the amplitude from position k to k – r a and b are vectors of length r maximum convolve them (equivalent to polynomial mult) and add all amplitudes with exp k of r and higher to exp k – r After the multiplication all amplitudes are taken %n “”” res = NP.zeros(2 * r, dtype=NP.int64) res:len(a)+len(b)-1 = NP.convolve(a, b) res = res:-r + res-r: return res % n def powmodn(pn, n, r, m): res = 1 while n: if n & 1: res = mmultn(res, pn, r, m) n //= 2 if n: pn = mmultn(pn, pn, r, m) return res def testan(a, n, r): pp = powmodn(a, 1, n, r, n) ppn%r = (ppn%r – 1 ) % n # subtract X^n pp0 = (pp0 – a) % n # subtract a return not any(pp) def phi(n): return sum(fractions.gcd(i, n) == 1 for i in range(1, n)) def aks(n): for a in range(2, isqrt(n) + 1): for b in range(2, n): t = a ** b if t == n: return False if t > n: break logn = math.log(n, 2) logn2 = logn ** 2 for r in IT.count(3): if fractions.gcd(r, n) == 1 and ordr(r, n) >= logn2: break for a in range(2, r + 1): if 1 < fractions.gcd(a, n) < n: return False if n <= r: return True for a in range(1, int(math.sqrt(phi(r)) * logn)): if not testan(a, n, r): return False return Trueif __name__== “__main__”: print(“Menu:
1.Print All Prime in a Range
2.Check if a number is Prime
3.Check an exponent ( X^n format)
4.End”) while True: print(“Enter choice: “); choice=int(input()); if choice==1: print(“Enter a Range: “); r=int(input()); start=timer() for i in range(r): if aks(i+1): print(str(i+1)+” “); elif choice==2: print(“Enter a number: “); n=int(input()); start=timer() if aks(n): print(str(n)+” is Prime
“); else: print(str(n)+” is Composite
“); elif choice==3: print(“Enter X: “); x=int(input()); print(“Enter n: “); n=int(input()); n=x**(n); start=timer() if aks(n): print(str(n)+” is Prime
“); else: print(str(n)+” is Composite
“); else: break; elapsedTime=timer()-start; print(“Time taken for this operation : “, str(elapsedTime),”Seconds”)Output:Enter choice: 3Enter X: 25Enter n: 5577037197775489434122239117703397092741524065928615527809597551822662353515625 is CompositeTime taken for this operation : 0.000568098316563237 SecondsThe Sieve of Eratosthenes is a very simple and popular technique for finding all the prime numbers in the range from 2 to a given number n. The algorithm takes its name from the process of sieving—in a simple way we remove multiples of consecutive numbers.400304037465{}00{}Initially, we have the set of all the numbers 2,3 ,. .., n . At each step we choose the smallest number in the set and remove all its multiples. Notice that every composite number 27254203429000has a divisor of at most n. In particular, it has a divisor which is a prime number. It 53917858445500is sufficient to remove only multiples of prime numbers not exceeding n. In this way, all composite numbers will be removed. The above illustration shows steps of sieving for n = 17. The elements of the processed set are in white, and removed composite numbers are in gray. First, we remove multiples of the smallest element in the set, which is 2. The next element remaining in the set is 3, and wealso remove its multiples, and so on.center49453800The above algorithm can be slightly improved. Notice that we needn’t cross out multiples of i which are less than i2. Such multiples are of the form k i, where k < i. These have already been removed by one of the prime divisors of k. After this improvement, we obtain the following implementation:1 def sieve(n):2sieve = True * (n + 1)3sieve0 = sieve1 = False4i = 25while (i * i <= n):6if (sievei):7k = i * i8while (k <= n):9sievek = False10k += i11i += 112return sievePseudo Code of Sieve:Let A be an array of Boolean values, indexed by integers 2 to nSet all the index having odd value of A to true.Set A2=true;For all odd integer i = 3,5,7, … not exceeding square root of n do:If Ai is true then:For j = i^2, i^2+i, i^2+2i, ….not exceeding n:Aj=false;Output all I such that Ai is true; Proof:The main idea here is that every value given to n will be prime, because if it were composite it would have been marked as a multiple of some other smaller primes.The algorithm relies upon one theorem solely. If n>1 is composite, then n has a prime divisor p such that p^2<=n.Or another way to say,If n>1 is composite, then n has a prime divisor p such that p<= square root(n).Proof of this theorem:Let n be a composite integer. So n must have a prime divisor a with 1<a<n, thus n=a*bIt’s likely that a <= sqrt(n) or b<=sqrt(n).Otherwise, if on the contrary, a> sqrt(n) and b>sqrt(n), thenab> sqrt(n) * sqrt(n) = nSo either a or b is less than sqrt(n).Time complexity:Step 2 of the algorithm has running time O(n) as it runs n/2 times.Step 4 runs sqrt(n) times.The loop of step 4-a-I has running time as followsT(n) = n/2 + n/3 + n/5 … = n * (sum of reciprocals of primes upto n).The reciprocal sum of primes diverges as log(logn).So the ultimate running time of this algorithm is O(nlog(logn)).Coding:__author__ = ‘Anand’from datetime import datetimefrom timeit import default_timer as timermarked=bool*236870910# 236870910 is the biggest size of array in python 3# in sieve algorithm we take an array.. then mark all the prime position# so max input you can give is 236870910def sieve(n): # markedi=True is if i is not prime # markedi=False is if i is prime # first initialize all the index for i in range(n): markedi=False; i=3; limit=int(n**(.5)); # first loop’s limit.. i<=sqrt(n) while i<=limit: if markedi==False: # if is is prime, then mark all of i’s divisors as not prime j=i*i; while j<=n: markedj=True; j+=(i+i); i+=2; # this is because we are not considering even numbers as they are not primedef isPrime(n): # these are base cases if n==1: return False; if n==2: return True; # to eliminate even numbers if n%2==0: return False; # for rest of the cases we can just check marked array to check return markedn==False;if __name__== “__main__”: print(“Menu:
1.Print All Prime in a Range
2.Check if a number is Prime
3.Check an exponent ( X^n format)
4.End”) while True: print(“Enter choice: “); choice=int(input()); if choice==1: print(“Enter a Range: “); r=int(input()); start=timer() sieve(r+1); for i in range(r): if isPrime(i+1): print(str(i+1)+” “); elif choice==2: print(“Enter a number: “); n=int(input()); start=timer() sieve(n+1); if isPrime(n): print(str(n)+” is Prime
“); else: print(str(n)+” is Composite
“); elif choice==3: print(“Enter X: “); x=int(input()); print(“Enter n: “); n=int(input()); n=x**(n); start=timer() sieve(n+1); if isPrime(n): print(str(n)+” is Prime
“); else: print(str(n)+” is Composite
“); else: break; elapsedTime=timer()-start; print(“Time taken for this operation : “, str(elapsedTime),”Seconds”)Output:Menu:1.Print All Prime in a Range2.Check if a number is Prime3.Check an exponent ( X^n format)4.EndEnter choice: 2Enter a number: 85695458569545 is CompositeTime taken for this operation : 1.626723455428376 Seconds
