THIS REPOSITORY CONTAINS SOME BASIC ALGORITHMS RELATED TO NUMBER THEORY LIKE THE DECOMPOSTION OF AN INTEGER IN PRIME FACTORS, CALCULATION OF PRIME NUMBERS AND THE EUCLIDEAN/DIVISION ALGORITHM TO FIND THE GREATEST COMMON DIVISOR OF TWO INTEGERS, CALCULATION OF CONTINUED FRACTIONS, CALCULATION OF THE P-ADIC EXPANSION OF INTEGERS AND RATIONAL NUMBERS. FURTHER ALGORITHMS WILL BE ADDED IN THE FUTURE.
ANY SUGGESTION OR CONTRIBUTION IS ENTIRELY WELLCOME.
OBSERVATION: THE MOST EFFICIENT ALGORITHMS TO COMPUTE THE FACTORS OF A VERY LARGE NUMBER ARE THE GENERAL NUMBER FIELD SIEVE AND THE QUADRATIC SIEVE BUT THEY INVOLVE HIGHLY COMPLEX CONCEPTS IN NUMBER THEORY, OUT OF THE SCOPE OF THIS REPOSITORY (I'M NOT A PROFESSIONAL MATHEMATICIAN). BUT THERE'S SOME IMPLEMENTATION OF THESE ALGORITHM IN LANGUAGES LIKE C/C++ EASILY AVAILABLE ON THE INTERNET. HERE WE HAVE IMPLEMENTED THE ALGORITHM KNOWN AS RATIONAL SIEVE, FROM WHICH THESE METHODS ARE DERIVED BY EXTENSION.
SEE: https://vtechworks.lib.vt.edu/bitstream/handle/10919/36618/etd.pdf http://www-personal.umich.edu/~msgsss/factor/qs_rep.pdf http://kmgnfs.cti.gr/kmGNFS/Home.html
I DON'T IMPLEMENT THE AKS_PRIMALITY_TEST WHICH IS A DETERMINISTIC TEST FOR THE PRIMALITY OF INTEGERS AND THE MOST EFFICIENT FOR VERY LARGE NUMBERS. IT'S A VERY COMPLEX ALGORITHM WHICH REQUIRES A DEEP KNOWLEDGE OF NUMBER THEORY. BUT I PROVIDE A SLIGHTLY CHANGED VERSION OF THE LAST STEP OF THIS ALGORITHM USING BINOMIAL EXPANSION.
BUT GOOD IMPLEMENTATION ARE ALSO AVAILABLE ONLINE: https://en.wikipedia.org/wiki/AKS_primality_test https://github.com/kikawet/AKSPrimalityTest-CPP/tree/main
FOR THE REASON OF COMPLEXITY WE DON'T IMPLEMENT THE ECPP (ELLIPTIC CURVE) PRIMALITY TEST AND THE APR-CL PRIMALITY TEST (WHICH USE ARITHMETIC ON CYCLOTOMIC FIELDS). THEY ARE THE MOST EFFICIENT PRIMALITY TESTS IN USE AVAILABLE TODAY (THEY HAVE BETTER RUNTIME THAN THE AKS TEST). GOOD IMPLEMENTATIONS ARE AVAILABLE ONLINE. SEE FOR INSTANCE: https://github.com/wacchoz/APR_CL/blob/master/APR_CL.py AND https://github.com/onechip/ecpp
THE PRESENT REPOSITORY COVERS ELEMENTARY ASPECTS OF NUMBER THEORY. THE READER INTERESTED MAY CONSULT THE FOLLOWING BIBLIOGRAPHY:
Introduction to Modern Number Theory, by Yuri I. Manin and Alexei A. Panchishkin
Elements of Number Theory by I. M. Vinogradov
Prime Numbers And Computer Methods For Factorization, by Hans Riesel