Abstract:
This primality testing is based on Infinite, Symmetric, Convergent, Continuous, Convolution Ring Group. The computational complexity of any primality testing depends in the factor less than √{square root over (N)} and becomes increasingly complex for large numbers as the lesser factor approaches └√N┘. But in the present algorithm the Infinite, Symmetry, Convergent, Continuous, Convolution Ring Group causes the numerator (i.e. the left side of the modulus) to converge smoothly towards └√N┘ as the testing factor approaches └√N┘. The normal operation for primality testing has computational complexity of O(n 2 ), while the present algorithm has computational complexity of O(n·(ln(n)). By using the non-abelian group e.g. Matrix (A). Matrix (B)≠Matrix (B). Matrix (A) the security is buttressed to the highest level.

Description:
BACKGROUND OF THE INVENTION 
       [0001]    This invention presents fast generation and testing of large primes in innovative way for the use in cryptographic systems such as RSA. With the mass applications of data security employed by the proliferation of mobile devices such as smart phones, e-commerce, cloud computing, banking and smart card transactions etc., the larger prime numbers are constantly required to keep up with the advances in computability. The fast generation of large Prime numbers is the basis of security of every current cryptographic system e.g. RSA, Elliptical Curve Cryptography, Diffie Hellman Key Exchange or any other cryptographic protocol. 
         [0002]    This prime number generation and testing is based on INFINITE, SYMMETRIC, CONVERGENT, CONTINUOUS, CONVOLUTION RING GROUP. The computational complexity of the prime number generation and testing depends on the factor less than √{square root over (N)} and becomes increasingly complex for large numbers as the testing factor approaches √{square root over (N)}. But in the present algorithm the INFINITE, SYMMETRIC, CONVERGENT, CONTINUOUS, CONVOLUTION RING GPOUP causes the numerator (i.e. the left side of the modulus) to converge rapidly towards R where R=N−└√N┘. ┌√N┐, as the testing factor approaches √{square root over (N)} and thus the computational complexity for prime number generation and testing is reduced from O(n 2 ) to O(n·Log(n)). 
         [0003]    The concept of primality testing and factorization has been thoroughly investigated since the Euler&#39;s time. The prime numbers are ubiquitous in digital security and are the most interesting figure in number theory. Prime numbers are only divisible by themselves and 1 and have no other factor. The method to determine whether a number N is prime or not is to divide N by every number n≦√{square root over (N)} and if any n divides N, it is composite and otherwise prime. This method was well known as Sieve of Eratosthenes (276 BC) and it generates all primes less than N. However this method is very slow for testing primality as it takes Ω(N) steps. For large numbers Sieve of Eratosthenes may take many thousand years for large prime number generation, testing and factoring. 
         [0004]    There have been many thorough investigations for testing primality. These methods were either probabilistic or on the condition such as Extended Riemann Hypothesis (ERH). Yet other were based on confluence of various existing methods of pseudo prime generation or Elliptic Curve method of factorization and the primality testing which are impracticable for large prime number generation and testing. 
         [0005]    Some modern methods of testing primality utilizes Fermat&#39;s congruence which can be written as b p-1 =1 mod p where b is any number and p is prime. But the Fermat Little Theorem may also satisfy the congruence b p-1 =1 mod n, where n is composite, called Carmichael number and hence the test is probabilistic or conditional. 
         [0006]    In 1975 Miller used the property based on Fermat&#39;s little theorem to obtain a deterministic polynomial time algorithm. But if the algorithm asserts that a number is Prime then its primality is proven from Paeno&#39;s axioms, whereas Miler&#39;s algorithm guarantees a proof under additional assumption of the Extended Riemann Hypothesis. It was modified by Rabin to give unconditional but randomized polynomial time algorithm. Solovay and Strassen independently in 1974 obtained a randomized polynomial time algorithm using the congruence 
         [0000]    
       
         
           
             
               ( 
               
                 b 
                 n 
               
               ) 
             
             = 
             
               
                 b 
                 
                   n 
                   - 
                   1 
                 
               
                
               
                 ( 
                 
                   mod 
                    
                   
                       
                   
                    
                   n 
                 
                 ) 
               
             
           
         
       
     
         [0000]    for every b where 
         [0000]    
       
         
           
             ( 
             
               b 
               n 
             
             ) 
           
         
       
     
         [0000]    is the Jacobi symbol. Their algorithm can also be made deterministic under ERH. Since then there have been number of randomized polynomial time algorithm proposed based on different properties. 
         [0007]    In 1983, Adleman, Pomerance and Rumely gave the deterministic algorithm for primality testing that runs in (log n) O(log log log n)  time. This algorithm was the generalization of Millers Algorithm and used higher reciprocity laws. In 1986 Goldwasser and Kilian proposed a randomized algorithm based on Elliptic Curves running in expected polynomial time. Atkin, Adleman and Huang modified Goldwasser-Kilian algorithm to obtain a randomized algorithm that runs in expected polynomial time. Only recently in the last decade Agrawal, Kayal and Saxena (AKS) proposed unconditional deterministic algorithm for primality testing. The primality testing of AKS algorithm is based on the identity 
         [0000]      ( X+a ) n   =X   n   +a (mod  n )  (1)
 
         [0000]    Where aεZ, nεN, n≧2 and (a,n)=1 
         [0008]    However, this takes time Ω(n) because in the worst scenario we need to evaluate n coefficients on left side of the equation (1). AKS algorithm reduces the number of coefficients by appropriately choosing a small r to satisfy the equation: 
         [0000]      ( X+a ) n   =X   n   +a (mod  X   r −1, n ).
 
         [0000]    The AKS algorithm does not return factors. 
         [0009]    The open question remained was to test the complexity of factorization of integers and the complexity class P vs. NP. Is there a polynomial time algorithm for factoring the integers? In the past there has been no polynomial time algorithm for factoring integers. We shall present such algorithm which factors any whole number in polynomial time. Later we shall also prove the related theorems for the deterministic and unconditional properties of the algorithm. 
         [0010]    Factoring like the primality testing has long history. Euler developed a method of factorization by expressing the whole number as sum of two squares in two different ways. But because of this characteristic it shall only factor very limited number of the whole numbers. The other method is called Fermat&#39;s method of factoring, which uses the identity: 
         [0000]    
       
         
           
             ab 
             = 
             
               
                 
                   
                     [ 
                     
                       a 
                       + 
                       b 
                     
                     ] 
                   
                   2 
                 
                 4 
               
               - 
               
                 
                   
                     [ 
                     
                       a 
                       - 
                       b 
                     
                     ] 
                   
                   2 
                 
                 4 
               
             
           
         
       
     
         [0011]    Pollard Rho factoring method can only factor the small factors of the composite number. Peter Shor developed a suitable polynomial time algorithm for factoring on quantum computer. Yet another method i.e. Number Field Sieve recently used by researchers to factor RSA 768 using the computer systems of many Research Institutions with the equivalent time of 2000 years for the fastest current processor using parallel programming and if the size of the composite number is increased, the additional efforts required to factor are increased drastically. That research concluded that there exists no polynomial time algorithm for factoring in a non-quantum computer. Till now it was an open problem in computer science that there exists no polynomial time algorithm for factoring large integers. 
     
    
     DESCRIPTION 
       [0012]    This invention goes beyond Godel&#39;s Incompleteness Theorems for the solution to Hilbert&#39;s second problem. and the resolution of NP completeness for algebra and number theory and in general P=NP. Godels incompleteness are the theorems of mathematical logic that establishes inherent limitation of all but the most trivial axiomatic systems capable of doing arithmetic. The two results are widely but not universally interpreted as showing that Hilbert&#39;s interest in finding a complete and consistent set of axioms for all mathematics is impossible giving negative answers to the Hilbert&#39;s second problem. The first incompleteness theorem states that no consistent system of axioms whose theorems can be listed by an effective procedure (e.g. computer program or any sort of algorithm) is capable of proving all truths about the relations of the natural numbers i.e. arithmetic. For any such system, there will always be statements about the natural numbers that are true but improvable within the system. The second incompleteness theorem shows that such a system cannot demonstrate its own consistency. 
         [0013]    This invention goes beyond the Godel&#39;s first and second incompleteness theorems by discovering INFINITE, SYMMETRIC, CONVERGENT, CONTINUOUS, CONVOLUTION RING GROUP that establishes NP completeness for algebra and number theory and in general P=NP. This INFINITE, SYMMETRIC, CONVERGENT, CONTINUOUS, CONVOLUTION RING GROUP has the power to solve any instances of NP complete, NP=NP hard and decision problems. At the end we prove the consistency of axioms used in the algorithms by the theorems. Accordingly, anything which can be computed mechanically can be computed in the feasible amount of time. 
       The Idea 
       [0014]    A practical and deterministic method for generating and testing large prime numbers is presented which solves the NP completeness for algebra and number theory and in general P=NP. The idea behind the primality testing with INFINITE, SYMMETRIC, CONVERGENT, CONTINUOUS, CONVOLUTION RING GROUP is that if any whole number N is divisible by [└√N┘−x], then [x 2 +x+R], where R=N−└√N┘. ┌√N┐, is divisible by [└√N┘−x] in the ring group i.e. (3≦x&lt;└√{square root over (N)}┘) and vice versa. By substituting y=[└√N┘−x] or x=[└√N┘−y] it can be further simplified that if a number N is divisible by y, then [y 2 −&lt;└√N┘+┌√N┐&gt;y+N] is divisible by y in the ring group i.e. (3≦y&lt;└√{square root over (N)}┘) and vice versa. The power of this algorithm is its ability for symmetric, continuous, convolution and rapid convergence of the numerator towards R as the testing factor approaches √{square root over (N)} and thus the computational complexity for prime number generation and testing is reduced from O(n 2 ) to O(n·Log(n)). The R by the definition can take the value in the range −└√N┘+1≦R≦└√N┘. 
         [0000]    
       
         
               
             
               
               
             
               
             
               
               
             
               
             
           
               
                   
               
               
                 ALGORITHM I 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                 Step 1: Input N 
                 // N is a (odd) whole number 
               
             
          
           
               
                 Step 2: If N is the perfect square, go to step 1 
               
               
                 Step 3: Calculate R = N − └{square root over (N)}┘·┌{square root over (N)}┐ 
               
               
                 //└√N┘ returns √N rounded down to next whole number and ┌√N┐ returns 
               
               
                 √N rounded 
               
               
                 up to the next whole number. By its definition R can take values −└√N┘ + 
               
               
                 1 ≦ R ≦ 
               
               
                 └√N┘ 
               
               
                 If R=0, Return 
               
               
                 The factors of N are └√N┘ and ┌√N┐. 
               
               
                 Else, 
               
               
                 For (x=Int, x= [└{square root over (N)}┘ − 3], x=             √            ┌√N┐ 2  − N                       , x−= 2) 
               
               
                 // Set x as an integer with initial value of x= [└{square root over (N)}┘ − 3] , make a 
               
               
                 descending loop in the 
               
               
                 step of 2 (to test only odd numbers) and set the final value of 
               
               
                 x=             √            ┌√N┐ 2  − N                       . 
               
             
          
           
               
                 Evaluate Z = [x 2  + x + R]MOD[└√N┘ − x] 
                 // Modular Operation 
               
             
          
           
               
                 If Z= 0, Return [└√N┘ − x] is the factor of N. 
               
               
                 Else, 
               
               
                 Return N is Prime. 
               
               
                   
               
             
          
         
       
     
         [0000]                                                            ALGORITHM II                                Step 1: Input N   //N is (odd) whole number            Step 2: If N is the perfect square, go to step 1.       Else,                For (y=Int, y =3, y = [└√N┘ −             √            ┌√N┐ 2  − N                       ], y+=2)            // Set y as an integer with initial value of 3, make an increment in the       steps of 2 and set       the final value to y = [└√N┘ −             √            ┌√N┐ 2  − N                       ].       Evaluate Z= [y 2  − [└√N┘ + ┌√N┐]y + n] MOD y       If Z= 0, Return y is the factor of N.       Else,       Return N is Prime.                    
Algorithm I and Algorithm II can be simplified as Algorithm III and Algorithm IV respectively.
 
         [0000]    
       
         
               
             
               
               
               
             
               
               
             
           
               
                   
               
               
                 ALGORITHM III 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 Step 1: Input N 
                 // N is (odd) whole number 
               
             
          
           
               
                   
                 Step 2: If N is the perfect square, go to step 1. 
               
               
                   
                 Step 3: Calculate R = N − └{square root over (N)}┘·┌{square root over (N)}┐ 
               
               
                   
                 If R=0, Return 
               
               
                   
                 The factors of N are └√N┘ and ┌√N┐. 
               
               
                   
                 Else, 
               
               
                   
                 K = └√N┘ 2  − 5└√N┘ + R + 6 
               
               
                   
                 // Set the initial value of K = F(x) = x 2  + x + R for x= [└{square root over (N)}┘ − 3]. 
               
               
                   
                 For (x=Int, x= [└{square root over (N)}┘ − 3], x=             √            ┌√N┐ 2  − N                       , x−= 2) 
               
               
                   
                 // Set x as an integer with initial value of x= [└{square root over (N)}┘ − 3] , make a 
               
               
                   
                 descending loop in the 
               
               
                   
                 steps of 2 and set the final value of x=             √            ┌√N┐ 2  − N                       . 
               
               
                   
                 Z = K MOD[└√N┘ − x] 
               
               
                   
                 K = K − 4x +2 
               
               
                   
                 // Assign the new values of K in the loop. 
               
               
                   
                 If Z= 0, Return [└√N┘ − x] is the factor of N. 
               
               
                   
                 Else, 
               
               
                   
                 Return N is Prime. 
               
               
                   
                   
               
             
          
         
       
     
         [0000]                                            ALGORITHM IV                                Step 1: Input N   // N is (odd) whole number            Step 2: If N is the perfect square, go to step 1.       K = N + 9 − 3[└√N┘ + ┌√N┐]       // Set the initial value of K = F(y) = y 2  − [└√N┘ + ┌√N┐]y + N for y=3.       For (y = Int, y=3, y = [└√N┘ −             √            ┌√N┐ 2  − N                       ], y+=2)       // Set y as an integer with initial value of 3, make an increment in the steps       of 2 and set       the final value to y = [└√N┘ −             √            ┌√N┐ 2  − N                       ].       Evaluate Z = K MOD y       K = K − 4[└√N┘ − y] +2       // Assign the new values of K in the loop.       If Z= 0, Return y is the factor of N.       Else,       Return N is Prime.                    
If the composite number has the factors of about the same size, it shall be more efficient to use the reverse direction as by Algorithms V through VIII in place of Algorithms I through IV respectively:
 
         [0000]    
       
         
               
             
               
               
             
               
             
           
               
                   
               
               
                 ALGORITHM V 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                 Step 1: Input N 
                 // N is a (odd) whole number 
               
             
          
           
               
                 Step 2: If N is the perfect square, go to step 1. 
               
               
                 Step 3: Calculate R = N − └{square root over (N)}┘·┌{square root over (N)}┐ 
               
               
                 If R=0, Return 
               
               
                 The factors of N are └√N┘ and ┌√N┐. 
               
               
                 Else, 
               
               
                 For (x=Int, x=             √            ┌√N┐ 2  − N                       , x= [└{square root over (N)}┘ − 3], x+= 2) 
               
               
                 // Set x as an integer with initial value of x=             √            ┌√N┐ 2  − N                       , make 
               
               
                 an incremental loop 
               
               
                 in the step of 2 (to test only odd numbers) and set the final value of 
               
               
                 x = [└{square root over (N)}┘ − 3] 
               
               
                 Evaluate Z = [x 2  + x + R]MOD[└√N┘ − x] 
               
               
                 If Z= 0, Return [└√N┘ − x] is the factor of N. 
               
               
                 Else, 
               
               
                 Return N is Prime. 
               
               
                   
               
             
          
         
       
     
         [0000]                                                            ALGORITHM VI                                Step 1: Input N   //N is (odd) whole number            Step 2: If N is the perfect square, go to step 1.       Else,                For (y=Int, y = [└√N┘ −             √            ┌√N┐ 2  − N                       ], y= 3, y−=2)            // Set y as an integer with initial value of y = [└√N┘ −             √            ┌√N┐ 2  −       N                       ]. make a       decrement in the steps of 2 and set the final value of y = 3       Evaluate Z= [y 2  − [└√N┘ + ┌√N┐]y + N] MOD y       If Z= 0, Return y is the factor of N.       Else,       Return N is Prime.                    
Algorithm V and Algorithm VI can be simplified as Algorithm VII and Algorithm VIII respectively.
 
         [0000]    
       
         
               
             
               
               
             
               
             
           
               
                   
               
               
                 ALGORITHM VII 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                 Step 1: Input N 
                 // N is (odd) whole number 
               
             
          
           
               
                 Step 2: If N is the perfect square, go to step 1. 
               
               
                 Step 3: Calculate R = N − └{square root over (N)}┘·┌{square root over (N)}┐ 
               
               
                 If R=0, Return 
               
               
                 The factors of N are └√N┘ and ┌√N┐. 
               
               
                 Else, 
               
               
                 K =             √            ┌√N┐ 2  − N                        2  +             √            ┌√N┐ 2  − N                        2  + R 
               
               
                 // Set the initial value of K = F(x) = x 2  + x + R for x =             √            ┌√N┐ 2  − 
               
               
                 N                        
               
               
                 For (x=Int, x=             √            ┌√N┐ 2  − N                       , x = [└{square root over (N)}┘ − 3], x+= 2) 
               
               
                 // Set x as an integer with initial value of x=             √            ┌√N┐ 2  − N                       , make 
               
               
                 incremental loop in 
               
               
                 the steps of 2 and set the final value of x= [└{square root over (N)}┘ − 3] 
               
               
                 Z = K MOD[└√N┘ − x] 
               
               
                 K = K + 4x − 2 
               
               
                 // Assign the new values of K in the loop. 
               
               
                 If Z= 0, Return [└√N┘ − x] is the factor of N. 
               
               
                 Else, 
               
               
                 Return N is Prime. 
               
               
                   
               
             
          
         
       
     
         [0000]                                      ALGORITHM VIII                                    Step 1: Input N           Step 2: If N is the perfect square, go to step 1.           K = [└√N┘ −             √            ┌√N┐ 2  − N                       ] 2  − [└√N┘ −             √            ┌√N┐ 2  −           N                       ] [└√N┘ + ┌√N┐] + N           // Set the initial value of K = F(y) = y 2  − [└√N┘ + ┌√N┐]y + N for           y = [└√N┘ −                       √            ┌√N┐ 2  − N                       ]           For (y = Int, y = [└√N┘ −             √            ┌√N┐ 2  − N                       ], y= 3, y−=2)           // Set y as an integer with initial value of [└√N┘ −             √            ┌√N┐ 2  −           N                       ],, make an decrement           in the steps of 2 and set the final value to y = 3           Evaluate Z = K MOD y           K = K + 4[└√N┘ − y] − 2           // Assign the new values of K in the loop.           If Z= 0, Return y is the factor of N.           Else,           Return N is Prime.                        
The Algorithm can be further simplified by using the Prime Numbers in the container class and thus testing the Primality for the Prime divisors only and not for every odd number divisor and thus increasing the efficiency of the algorithm.
 
Now we shall prove the theorems used in the algorithm for primality testing based on INFINITE, SYMMETRIC, CONVERGENT, CONTINUOUS, CONVOLUTION RING GROUP.
 
       Theorem I 
       [0015]    The expression (1) 
         [0000]    
       
         
           
             
               
                 x 
                 2 
               
               + 
               x 
               + 
               R 
             
             
               
                 [ 
                 
                   n 
                 
                 ] 
               
               - 
               x 
             
           
         
       
     
         [0000]    (algorithm I, III, V and VII) and the expression (2) 
         [0000]    
       
         
           
             
               
                 y 
                 2 
               
               - 
               
                 
                   ( 
                   
                     
                       ⌊ 
                       
                         N 
                       
                       ⌋ 
                     
                     + 
                     
                       ⌈ 
                       
                         N 
                       
                       ⌉ 
                     
                   
                   ) 
                 
                  
                 y 
               
               + 
               N 
             
             2 
           
         
       
     
         [0000]    (algorithm II, IV, VI and VIII) are identical. Proof: Put └√N┘−x=y or x=└└√N┘−y┘ in the first expression to obtain the second expression and vice versa.
 
The expression (1) on substitution becomes expression (2):
 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           ( 
                           
                             ⌊ 
                             
                               N 
                             
                             ⌋ 
                           
                           ) 
                         
                         2 
                       
                       + 
                       
                         y 
                         2 
                       
                       - 
                     
                   
                 
                 
                   
                     
                       
                         2 
                          
                         
                           ( 
                           
                             ⌊ 
                             
                               N 
                             
                             ⌋ 
                           
                           ) 
                         
                          
                         y 
                       
                       + 
                       
                         ⌊ 
                         
                           N 
                         
                         ⌋ 
                       
                       - 
                     
                   
                 
                 
                   
                     
                       y 
                       + 
                       N 
                       - 
                       
                         
                           ( 
                           
                             ⌊ 
                             
                               N 
                             
                             ⌋ 
                           
                           ) 
                         
                          
                         
                           ( 
                           
                             ⌈ 
                             
                               N 
                             
                             ⌉ 
                           
                           ) 
                         
                       
                     
                   
                 
               
               y 
             
             = 
             
               
                 
                   y 
                   2 
                 
                 - 
                 
                   
                     ( 
                     
                       
                         ⌊ 
                         
                           N 
                         
                         ⌋ 
                       
                       + 
                       
                         ⌈ 
                         
                           N 
                         
                         ⌉ 
                       
                     
                     ) 
                   
                    
                   y 
                 
                 + 
                 N 
               
               y 
             
           
         
       
     
         [0000]    By simply noting that ┌√N┐=└√N┘+1
 
Similarly the expression (2) on substitution becomes expression (1)
 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           ( 
                           
                             ⌊ 
                             
                               N 
                             
                             ⌋ 
                           
                           ) 
                         
                         2 
                       
                       + 
                       
                         x 
                         2 
                       
                       - 
                     
                   
                 
                 
                   
                     
                       
                         2 
                          
                         
                           ( 
                           
                             ⌊ 
                             
                               N 
                             
                             ⌋ 
                           
                           ) 
                         
                          
                         x 
                       
                       - 
                     
                   
                 
                 
                   
                     
                       
                         
                           ( 
                           
                             
                               ⌊ 
                               
                                 N 
                               
                               ⌋ 
                             
                             - 
                             x 
                           
                           ) 
                         
                          
                         2 
                          
                         
                           ( 
                           
                             
                               ⌊ 
                               
                                 N 
                               
                               ⌋ 
                             
                             + 
                             1 
                           
                           ) 
                         
                       
                       + 
                       N 
                     
                   
                 
               
               
                 
                   ⌊ 
                   
                     N 
                   
                   ⌋ 
                 
                 - 
                 x 
               
             
             = 
             
               
                 
                   x 
                   2 
                 
                 + 
                 x 
                 + 
                 R 
               
               
                 
                   ⌊ 
                   
                     N 
                   
                   ⌋ 
                 
                 - 
                 x 
               
             
           
         
       
     
         [0000]    By simply noting R=N−└√{square root over (N)}┘·┌√{square root over (N)}┐ 
       QED 
       [0016]    In the subsequent theorems we shall use only the expression (2), i.e. 
         [0000]    
       
         
           
             
               
                 
                   y 
                   2 
                 
                 - 
                 
                   
                     ( 
                     
                       
                         ⌊ 
                         
                           N 
                         
                         ⌋ 
                       
                       + 
                       
                         ⌈ 
                         
                           N 
                         
                         ⌉ 
                       
                     
                     ) 
                   
                    
                   y 
                 
                 + 
                 N 
               
               y 
             
             . 
           
         
       
     
       Theorem II 
       [0017]    The expression 
         [0000]      [ y   2 −(└√ {square root over (N)}┘+┌√{square root over (N)} ┐) y+N] 
       (i) Is always less than N for 0&lt;y≦|√N|   (ii) Within the range 0&lt;y≦|√N| has maximum value when y is at the lowest value and minimum value when y is at the highest value.   (iii) The limits [y 2 −(└√{square root over (N)}┘+┌√{square root over (N)}┐)y+N]→R as y→└√N┘ or y→┌√{square root over (N)}┐ where R=N−└√N┘┌√N┐ and R by its definition take values −└√{square root over (N)}┘+1≦R≦└√N┘       
 
       Proof: 
       [0021]    Since for 0&lt;y≦|√{square root over (N)}| the expression y 2 −(└√{square root over (N)}┘+┌√{square root over (N)}┐)y is negative and hence 
         [0000]        y   2 −(└√ {square root over (N)}┘+┌√{square root over (N)} ┐) y+N&lt;N  
 
         [0000]    It may be noted that as limit y→└√N┘, the expression 
         [0000]      [ y   2 −(└√ {square root over (N)}┘+┌√{square root over (N)} ┐) y+N]→R  
 
         [0000]    In fact by putting y=└√{square root over (N)}┘ or y=┌√{square root over (N)}┐, one obtains 
         [0000]      [ y   2 −(└√ {square root over (N)}┘+┌√{square root over (N)} ┐) y+N]=N−└√{square root over (N)}┘·┌√{square root over (N)}┐=R  
 
         [0000]    In other words as y→√N the numerator [y 2 −(└√{square root over (N)}┘+┌√{square root over (N)}┐)y+N]→R, where R=N−└√N┘┌√N┐ and R by definition has a value in the range −└√{square root over (N)}┘+1≦R≦└√N┘. 
       QED 
     Theorem III 
       [0022]    For y being the factor of y 2 −(└√{square root over (N)}┘+┌√{square root over (N)}┐)y+N, the following identity holds: 
         [0000]        y   2 −(└√ {square root over (N)}┘+┌√{square root over (N)} ┐) y+N≧y  
 
         [0000]    (Note the upper limit for testing for y in the Algorithm II, IV, VI and VIII) 
       Proof: 
       [0023]    Let “a” be the lesser factor of N (odd whole number) and therefore the factor of the expression y 2 −(└√{square root over (N)}┘+┌√{square root over (N)}┐)y+N and N/a=b where “b” is other factor of N (Note that “b” may be composite or prime). Therefore by dividing the expression a 2 −(└√{square root over (N)}┘+┌√{square root over (N)}┐)a+N by “a” we obtain (a+b)−(└√{square root over (N)}┘+┌√{square root over (N)}┐)≧1, where (a+b) is the sum of two factors of N.
 
Note that (a+b)&gt;(└√{square root over (N)}┘+┌√{square root over (N)}┐); (a+b) is even and (└√{square root over (N)}┘+┌√{square root over (N)}┐) is odd. Therefore (a+b)−(└√{square root over (N)}┘+┌√{square root over (N)}┐)≧1.
 
The algorithm tests from integers 3≦y≦└√N┘, but the algorithm can be terminated before y is ever reached to └√N┘ based on the identity: y 2 −(└√{square root over (N)}┘+┌√{square root over (N)}┐)y+N≧y, see Algorithm II, IV, VI and VIII.
 
       QED 
       [0024]    Corollary: The Quotient of the expression y 2 −(└√{square root over (N)}┘+┌√{square root over (N)}┐)y+N when divided by lesser factor of N (also the factor of expression) say “a” is equal to (a+b)−(└√{square root over (N)}┘+┌√{square root over (N)}┐), where “b” is the other factor of N. 
       Theorem IV 
       [0025]    “a” is the factor of N if and only if “a” is the factor of the expression y 2 −(└√{square root over (N)}┘+┌√{square root over (N)}┐)y+N in the ring group (3≦a≦└√{square root over (N)}┘) or for larger factor “b” for any N (odd whole number) and vice versa. 
         [0000]    Proof: The expression y 2 −(└√{square root over (N)}┘+┌√{square root over (N)}┐)y+N with “a” as one of the factors in the ring group (3≦a≦└√N┘) can be expressed as a(a−(└√N┘+┌√N┐))+N. Similar expression for the larger factor “b” of N can be written as b(b−(└√N┘+┌N┐))+N.
 
Therefore “a” (or “b”) is the factor of N if and only if “a” (or “b”) is the factor of the expression y 2 −(└√{square root over (N)}┘+┌√{square root over (N)}┐)y+N in the ring group (3≦a≦└√N┘) or for larger factor “b” for any odd N and vice versa.
 
       QED 
     SUMMARY OF INVENTION 
     Importance 
       [0026]    Almost every form of current computer security depends on generating large prime numbers to be used in conjunction with major security protocols such as RSA, Elliptic Curve Cryptography or Diffie Hellman Key Exchange. The RSA, Elliptical Curve Cryptography or Diffie Hellman Key Exchange derives their security from the hardness to factor large numbers. The present algorithm is the fastest deterministic algorithm to test the primality and to return the factors. The security candidates shall have to use this algorithm to find large prime numbers for the composite numbers and the primes to be used in conjunction with the RSA, Elliptical Curve Cryptography, Diffie Hellman Key Exchange or any other security protocol in accordance with the advancement of the computational power. 
         [0000]    The important properties of this algorithm are:
 
(1) It is fastest deterministic algorithm to test primality and the factorization.
 
(2) This algorithm is universally applicable for every N (whole number). In comparison to the existing primality testing algorithms e.g. the Miller Rabin test, the AKS primality test, and otherwise too this is most efficient and practical algorithm.
 
(3) It solves the Hilbert&#39;s second problem, the Non Deterministic Polynomial Time Completeness for Algebra and Number theory and in general P (Polynomial Timt)=NP (Non Deterministic Polynomial Time) for all instances.
 
       The Trillion Dollar Phenomena 
       [0027]    INFINITE, SYMMETRIC, CONVERGENT, CONTINUOUS, CONVOLUTION RING GROUP is a trillion dollar phenomena in form of NEXT BIG IDEA and the CAPITAL MAGNET for the Venture Capital and Private Equity markets. 
       NON-PATENT CITATIONS 
     References 
       [0000]    
       
         The Riemann Hypothesis and Prime Number Theorem, Daljit S. Jandu; Infinite Bandwidth Publishing, 2006. 
         Handbook of Cryptography, Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone; CRC Press, 1996. 
         Prime is in P Manindra Agrawal, Kayal and Saxena: Indian Institute of Technology Kanpur, 2002. 
         Prime Numbers and the Computer Method of Factorization, Hans Riesel, Springer 1994. 
       
     
       PATENT CITATION 
       [0032]      
         [0000]    
       
         
               
               
               
               
             
           
               
                   
               
               
                 CITED 
                 FILING 
                 PUBLICATION 
                   
               
               
                 PATENT 
                 DATE 
                 DATE 
                 APPLICANT 
               
               
                   
               
             
             
               
                 U.S. Pat. No. 
                 Jul. 31, 2003 
                 Mar. 18, 2008 
                 Agrawal, Kayal 
               
               
                 7,346,637 B2 
                   
                   
                 Saxena