HEJ, HU ISSN 1418-7108 Manuscript no.: ANM-000926-A

Primality testing and factorization

Given a number $n$, it is a very important question, how to construct its complete factorization according to Theorem 2. Up to the $1950$s, this process was usually very circumstantial - and in most of the cases unsuccessful - for large numbers. In spite of this a number of very important theoretical results were published already long before (e.g. by FERMAT). However, the significant development in this field practically started with the appearance of computers. Similarly as before, we present only the most important results and only some of the proofs. We omit the exact behaviour-analysis by the methods. Detailed theoretical discussion can be found e.g. in [1].

The basic algorithm A traditional method for the factorization is the trial divison with the primes $2, 3, 5, 7, 11, 13, 17, \dots$, or with the numbers $2, 3, 5, 7, 9, 11, 13, 15, \dots$, which is easier to programize, but we get the result slower. Analysing this algorithm (e.g. its simplified Maple-form below) we conclude, that it works usable in our PC's if the order of $n$ is maximum $10^{16} - 10^{18}$, or if the order of the divisor is maximum $10^8-10^9$. For larger numbers the algorithm usually slows down hopelessly, because of the lot of divisions. In a faster computer we can make this situation better, but the improvement will not be spectacular. In the following example we search for the prime divisors of an odd number with trial divison. We can get the same result using the ifactor function with the option 'easy'.

  > basic:=proc(n,limit)
  > local i,s,a;
  >   s:=NULL; a:=n;
  >   for i from 3 by 2 to limit do
  >     if a mod i = 0 then a:=a/i; s:=s,i;
  >       while a mod i = 0 do a:=a/i; s:=s,i od
  >     fi
  >   od; print(s,a) 
  > end:

  > b:=1234567890123456789:
  > basic(b, 4001);

$$3, \,3, \,101, \,3541, \,3607, \,3803, \,27961$$

  > ifactor(b,'easy');

$$(\,{\rm }3)^{2}\,(\,{\rm }101)\,(\,{\rm }3803)\,(\,{\rm }3607)\,( \,{\rm }27961)\,(\,{\rm }3541)$$

Let us assume, that the number $n$ is very large, it contains e.g. $100$ decimal digits. In this case we apply the basic algorithm to separate the "small" factors up to the order of approximately $10^9$. After this we examine the remaining part further with additional methods, discussed in the following subsections.

HEJ, HU ISSN 1418-7108 Manuscript no.: ANM-000926-A