Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
|
|
Re: square mod
Posted:
Jul 20, 2005 11:22 AM
|
|
tum_ wrote:
> Tom St Denis wrote:
> > (not a)\/b wrote:
> > > what is the more efficient algorithm for doing x^2 mod (n)?
> >
>
> "more efficient" than what?
>
> >
> > Suppose n is a random odd integer of say 512 bits and you are on a
> > Intel P4 [shudder...] then likely a comba based squaring algorithm with
> > a montgomery reduction will be the fastest.
>
> Hmm, don't see how would montgomery help here - it's just squaring, not
> exponentiation with a (relatively) big exp. If the task is stated
> correctly - it requires just a single modulo reduction, isn't it?
If you are doing more than one squaring...
If in your entire lifetime you'll only square one number for that
modulus... then chances are a straight up integer division will be
fine.
If you are doing 10000 squares per second... you'll want to rethink
that.
tom
|
|
|
|
