How do you get factor pairs of big numbers?

Answer 1

Well, for a given value of big . . .

• If you have a really big number which is the product of two primes (maybe 100 digits each) you are looking for the current Holy Grail of some workers in number theory.
• Generating numbers around 100 digits long is dead easy. Identifying the primes amongst them takes longer, but is quite do-able. Multiplying two of these primes to make a 200 digit composite number is, again, straightforward.
• Now try undoing it. Given a 200 digit number that was produced by multiplying two primes, find those primes. As far as we know, no-one has come up with a way of doing this within a lifetime of computation, even using the fastest number cruncher around.
• There are encryption systems in use that rely on the practical impossibility of factorising these huge numbers; if you can find a way to do it you could probably write your own check at GCHQ or the NSA.

The same as any other number. It will probably take a little longer since there's more factors. First step: Find the prime factorization.

23 x 32 x 52 x 11 = 19800 That gives you 2, 3, 5 and 11. Every other factor is in there in some combination. The rules of divisibility give you 4, 6, 8, 9 and 10. That gives you 10 factor pairs. (19800,1)(9900,2)(6600,3)(4950,4)(3960,5)(3300,6)(2475,8)(2200,9)(1980,10)(1800,11) Work your way up from there. 22 x 3, 3 x 5, 2 x 32, 22 x 5, 2 x 11, 23 x 3, 5 x 5, 2 x 3 x 5, 3 x 11, 22 x 32 (1650,12)(1320,15)(1100,18)(990,20)(900,22)(825,24)(792,25)(660,30)(600,33)(550,36) There are sixteen more.