## Factorize large mod problem

Help
glob99
2012-02-03
2012-11-20

• glob99
2012-02-03

I am using an Ubuntu 64 bit CSL based Reduce install.

I was trying the polynomial factor problem shown at,

x^500+x+1 modulo nextprime(ceiling(pi * 2^500))

However, I am getting the error message that modulus is too big. After googling, it seems that modulo factorize is limited to largest!-small!-modulus value. In my install it's value is 16777215 or 24 bits. :-( So the algorithm is limited to small integers.

Is there another package that can handle large modulus problems?

• Arthur Norman
2012-02-03

As you observe, the current Reduce code for factorising polynomials over finite fields uses functions that do modular arithmetic using one-word integers. The limit is around 24 not 32 bits for historical compatibility between the PSL and CSL versions as well as because a Lisp implementation tends to need to use some of the bits of  a word as tags. On a 64-bit machine with CSL I could in principle increase that limit to around 2^60 but there would be rather a lot of re-coding to do that properly, and I am not about to go that way - and anyway 2^60 would not address your case. For challenge problems like the one you cite and that are expected to take many hours to solve  it is also common to need to review which algorithms are to be used and sometimes to tune the implementation. Reduce uses a simple Berlakamp. Its modular factorisation is there really mostly by exposing the factor-mod-p code needed for the general multivariate factorisation-over-the-integers package… and that does not need huge values of the modulus.

If would be possible to make a copy of chunks of the existiing modular factorisation code calling eg the funcions from packages/factor/bigmodp.red rather than the small-number-only versions that are built into the Lisp. Anybody doing that should in fact also bring themselves up to date with the literature on modular factorisation and consider whether a different method would be better. But if you felt like trying that and ended up with something you could contribute that coped with the large modulus case well and that was respectably reliable we could consider addint it to the Reduce sources.
If you have lots of huge modulus cases that are important to your work or interest (ie beyond the challenges thate are there to try to go beyond the capabilities of many systems, but that are otherwise artificial) that would also be interesting to know…  I do not think there is merit in me hacking anything just to attack one case but of there was significantly broader need then possibly somebody ought to try to develop something, or at least help you while you did!
Arthur