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)*Reply-to*: comp.soft-sys.math.mathematica at googlegroups.com

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