Can I find the remainder more efficiently?

Question

Here :

https://github.com/gnufinder/prime-factor

I submitted a contribution with the goal to find a prime factor of the number 2^{2^2²}+3^{3^3³}.

The number has 3,638,334,640,025 digits, so ECM will take too long, but pollard-rho might be feasible, if there is a computer which can handle such numbers.

With normal hardware, only trial division will work. A primility test for such a number will be virtually hopeless.

You can see programs for GAP and PARI/GP determining the remainder if the number is divided by p, but I think this can be improved.

Does anyone have an idea how I can improve my programs?

Is elliptic curve factorization feasible (assuming there are small factors)? — CodesInChaos, May 29 '16 at 12:00
Mysticial calculated Pi to 12 trillion digits, which is bigger than your number (3.6 trillion digits), so handling numbers of that magnitude is possible using sufficiently sophisticated programs and a good computer. — CodesInChaos, May 29 '16 at 12:27
Maybe, but who has access to such computers ? I do not think that you know anyone having such a machine. — Peter, May 29 '16 at 12:30
ECM would be too slow even if the number would fit into the computer. And I think, pollard rho would also take very very long. — Peter, May 29 '16 at 12:49

score 3 · Answer 1 · answered May 29 '16 at 14:22

3

You can calculate a^b modulo p in O(ln b). So if you refrain from turning your number into a binary or decimal number, you can check divisibility by a few hundred million small primes quite quickly.

Other calculations may be possible without evaluating the number.

answered May 29 '16 at 14:22

gnasher729

44,814
4
64
126

A useful answer! If you show me how I can do this with PARI or GAP (but with the given number!) , I will accept your answer. – Peter May 29 '16 at 18:30

Lie Ryan · Answer 2 · 2016-05-29T00:25:14.237

If you want to crowd source anything, it's best to make it as easy as possible to contribute. Having to install a rather unusual language environment, like GAP or PARI/GP, is a boundary that would prevent most people from contributing.

What you can do to make it as easy as possible to contribute is to write a server and an API which can generate a search range and collect results, and a JavaScript version so that potential contributors can just visit a page and leave that page running in background. The web page should automatically picks a range, compute the range, and submits the result to the server. Doing this in a Github issue page is too cumbersome, you would have difficulties collecting the result as well.

Having an API also makes it possible for more serious contributor to contribute an implementation in different languages. Once you have a few different popular languages (e.g. C, Java, Python, Mathematica), it increases the likelihood that most people will have one of the environments already installed.

Having multiple implementations also allow each implementations to cross check each other. Like most crowd sourced computation project, you need to care about security. It's possible to submit false data, so you want to assign the same ranges multiple times to different people to have a degree of confidence that any false data are going to be voted out by the majority.

@Peter: nothing's wrong with it, just that most people would not want to bother installing a new language interpreter just to get into something like this. Javascript, Java, Python, native code, are more likely something that people already have in their machine, so there's much less friction to contributing. If you could just visit an HTML page and leave it churning in the background, that makes it much easier to contribute CPU power. — Lie Ryan, May 29 '16 at 12:21

Can I find the remainder more efficiently?

2 Answers2