How are extreme numbers TF'd?

[JuanTutors]

How are extreme numbers (so large that they can't be stored in any computer) trial-factored? It seems like factors of exreme numbers are being found frequently by different groups.

[xilman]

Originally Posted by dominicanpapi82

How are extreme numbers (so large that they can't be stored in any computer) trial-factored? It seems like factors of exreme numbers are being found frequently by different groups.

In general, they are not trial-factored. Almost all such numbers are unmanageable.

A few very special numbers, such as factorials and powers of small integers (plus or minus a small constant) are trial factored not by calculating the number and then taking the remainder but by taking remainders as the number is calculated. If the final remainder is (minus or plus the small constant), the number is divisible by the trial factor.

Here's a small worked example. We want to show that 7!+1 is divisible by 71.

1! mod 71 = 1
2! mod 71 = 2*(1! mod 71) mod 71 = 2
3! mod 71 = 3*(2! mod 71) mod 71 = 6
4! mod 71 = 4*(3! mod 71) mod 71 = 24
5! mod 71 = 5*(4! mod 71) mod 71 = 5 * 24 mod 71 = 120 mod 71 = 49
6! mod 71 = 6*(5! mod 71) mod 71 = 6 * 49 mod 71 = 294 mod 71 = 10
7! mod 71 = 7*(6! mod 71) mod 71 = 7 * 10 mod 71 = 70

Therefore, 7!+1 mod 71 = 70+1 mod 71 = 0

Therefore 7!+1 is divisible by 71, as claimed.

Note three things:

(1) this is an unrealistically small example, chosen so the computations would fit into a small browser window.

(2) I chose factorials rather than powers of integers to show that just about any function that can be computed iteratively can have its values tested without having to perform the entire computation first but, rather, the remainder calculated at each iteration. Some functions, such as powers of small integers, can be calculated much faster than others, such as factorials but the principle of the trial factoring remains the same.

(3) The intermediate values in the computation remain quite small. Careful programming should enable them to be not greater than (or not much greater than if the coding isn't quite as careful!) than the square of the trial factor.


Paul

[R.D. Silverman]

Originally Posted by dominicanpapi82

How are extreme numbers (so large that they can't be stored in any computer) trial-factored? It seems like factors of exreme numbers are being found frequently by different groups.

The short answer is that they are not. However, your question is
poorly posed.

If indeed, a number can not be stored, then it can not be trial factored.
However, the meaning of the word 'stored' is subject to interpretation,
because numbers can be represented in different ways. Consider a
Mersenne number, N = 2^p-1, for (say) p = 6090817323763. I can store
this number on a computer. What I can not do is store its DECIMAL
REPRESENTATION. Do not confuse a number with its representation.
There are many ways of representing integers. Decimal is only one of them.

What numbers can be 'stored' depends on how they are represented.
Many numbers can be manipulated and 'stored' even though we do not
have its full decimal representation. Consider N from above. I can compute
N mod 7 without ever computing the decimal expansion of N via e.g. the
binary exponentiation algorithm. I can even compute 2^2^2^2^N - 1 mod 7,
even though this last number is VERY big.

[alpertron]

As an example of very high numbers trial factored you can see in my Web site:

Factorization of numbers near googolplex

and

Factorization of numbers near googolplexplex

Where googol = 10^100, googolplex = 10^googol, googolplexplex = 10^googolplex.