Re: How do I do very big integer computing by Mathematica?

• To: mathgroup at smc.vnet.net
• Subject: [mg115397] Re: How do I do very big integer computing by Mathematica?
• From: Filipe <filipedlarcanjo at gmail.com>
• Date: Mon, 10 Jan 2011 02:36:35 -0500 (EST)

```You might not be abble to represent such huge numbers in Mathematica. however, it's still possible to compute p^q (mod n) with some algebra tricks.

The basic idea is to compute the power incrementally and apply mod whenever posible. For instance:

2^10 (mod 5) =
2^3 * 2^7 (mod 5) =
3 * 2^3 * 2^4 (mod 5) =
3 * 3 * 2^3 * 2 (mod 5) =
3 * 3 * 3 * 2 (mod 5) =
9 * 6 (mod 5) =
4

You could implement something like PowerMod in mathematica following this strategy. For more information, just have a look at: http://en.wikipedia.org/wiki/Modular_exponentiation

```

• Prev by Date: Re: Clip[] doesn't work as expected
• Next by Date: Number of zeros finite or infinite?
• Previous by thread: Re: How do I do very big integer computing by Mathematica?
• Next by thread: Re: How do I do very big integer computing by Mathematica?