Factoring Very Large Numbers by GPS

Ordinary factoring by analytical means.
The number to be factored (factorised) is say, 11 466. The dividend i.e. 11 466, is an even number and will divide by 2 without leaving a remainder.

5 733 x 2 = 11 466

5 733 is an odd number and will not divide by 2 without leaving a remainder. Proceed to the next prime number, which is 3.

5 733 will divide by 3 without leaving a remainder and it also divides the quotient 1911 so that it is used twice as is always the case with every prime number that is being used as the divisor – keep on dividing the quotient by the same prime number while it does not leave a remainder.

The next prime number is 7, and so on to 13. That’s as far as I need to go and the prime factors of the integer 11 466 are.

2,3,3,7,7,13.

Any positive integer can be factorised in this way

The foregoing example is meant just as a refresher and also as a discussion model for what comes next.

Everyday Factoring of integers
Most ordinary computations only require the factoring of moderately sized positive integers and there is no problem. This is especially true if one is working longhand. However, since most important computations today are done in computers there is an automatic upper bound on the size of positive integer that can be handled by a computer when extremely large positive integers are considered. That upper bound is set by the limitations of the computer integer address box – the storage cells - to hold (contain) any large number while it is being factorised. In most computers in use today that cell size is 32 bits (32-bit arithmetic) although lot of the latest computers coming on the market are indeed 64 bit cells (64-bit arithmetic).

Click Here to download the full 4 page PDF file

Home Contact Us

Feel free to print these pages or Click Here to download the PDF file.