Mathematica 9 is now available
Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2011

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • 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?