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