A Primality Test Based On Modular Hyperbolic Curves

The prime number is the basic factor that constitutes an integer.It has important applications in coding theory,especially in modern cryptography.Therefore,determining whether a large integer is a prime number is the most basic problem in the application of prime numbers.The existing methods usually simply use the decomposition of + 1 or the decomposition of -1 to determine Whether N is a prime,and do not make full use of these two decompositions,for example,do not jointly use the decomposition of + 1 and -1.Not only that,the existing methods are generally not efficient for algorithm implementation.So far,the largest known prime number has not reached 30 million digits,the larger the value,the more difficult it is to obtain prime numbers.This is not only the problem of the algorithm itself,there are also problems with the computer's operation or mode of operation.This thesis uses modular arithmetic of hyperbolic curve to study the problem of determining prime numbers from the perspective of theory and algorithm.Several methods of primality testing are proposed and implemented by programming on a computer.Among the main innovations:(1)Modular arithmetic of hyperbolic curve has only been discovered in recent years,this arithmetic is used for the primality test for the first time in this thesis;(2)Simultaneously use the decomposition properties of + 1 and -1 to determine the primality of ;(3)Our algorithm for determining Mersenne prime numbers is nearly 50% more efficient than existing methods.The primality test we gave not only has rigorous theoretical proof,but also verified its correctness and effectiveness through algorithm implementation.It also proves that modular hyperbolic curve is not only a beautiful mathematical theory,but also has important application value.