0

I need to calculate prime factorization of large numbers, by large numbers I mean of range 10^100.

I get an input a[0] <= 10^5 (whose prime factors I have already calculated using the sieve and other optimizations). After that I get series of inputs of a[1], a[2], a[3] all in range 2 <= a[i] <= 10^5. I need to calculate the product and get the factors of the new product. I have the following maths

Let X be the data in memory and X can be represented as:

X = (p[0]^c1)(p[1]^c2)(p[2]^c[3]) .... where p[i] are its prime factors. So I save this as,

A[p[0]] = c1, A[p[1]] = c2.... as p[i] <= 100000 this seems to work pretty well.

and as new number arrives, I just add the power of primes of the new number in A.

So this works really well and also is fast enough. Now I am thinking of optimizing space and compensating with reduction of time efficiency.

So If I can represent Any number P as x^a + b where x is a prime. Can I factorize it? P obviously doesn't fit in the memory but 2 <= x, a, b <= 100000? Or Is there any other method that is possible which will save me the space of A? I am okay with a slower algorithm than the above one.

πάντα ῥεῖ
  • 1
  • 13
  • 116
  • 190
  • 1
    If you target number to be factored is result of multiplication of many known a[i], you need not to invent any other form. Just factor each a[i] and compute prime powers (exponents) by adding them, as you did (why you want to change current method?). You may use more compact A (prime powers) array - there is only even prime power of 2, so you may translate every prime < 10^5 into this prime index in A array (A[4], A[6], A[8] ... will be always 0 if factor a[i]). x^a+b is generic form isn't easier to factor, it is harder. – osgx Jun 02 '17 at 13:37

2 Answers2

2

I don't think representing a number as xa + b with prime x makes it any easier to factor.

Factoring hundred-digit numbers isn't all that hard these days. A good personal computer with lots of cores running a good quadratic sieve can factor most hundred-digit numbers in about a day, though you should know that hundred-digit numbers are about at the limit of what is reasonable to factor with a desktop computer. Look at Jason Papadopoulos' program msieve for a cutting edge factorization program.

user448810
  • 17,381
  • 4
  • 34
  • 59
0

First, you'll better do some math on paper (perhaps some simplifications are possible; I don't know...).

Then you need to use some arbitrary precision arithmetic (a.k.a. bignums or bigints) library. I recommend GMPlib but they are other ones.

See also this answer.

Basile Starynkevitch
  • 223,805
  • 18
  • 296
  • 547
  • As the numbers are arbitrary, I don't think there are many simplifications to this. And I would rather not use those bigint libraries but try to solve this at as low level as possible. As I am pretty sure storing the entire product is not necessary. –  Jun 02 '17 at 12:50
  • Why don't you want to use bigint libraries? You won't be able to do better than they do, and you'll do much worse. – Basile Starynkevitch Jun 02 '17 at 12:51