Prev: does this f(x,y) have to be a polynomial function of x and y?
Next: Tough queueing question
From: recoder on 4 Jun 2010 07:32
Dear All,
I have to write a program to compute:
2^q mod(p) and
2^(q-3) mod (p) where q and p are very large primes.
I plan to use the "power-mod" algorithm to compute the 2 expressions seperately.
Is there a way to compute
2^q mod(p) and derive 2^(q-3) mod (p) or vice versa ???
From: Pubkeybreaker on 4 Jun 2010 12:07
On Jun 4, 11:32 am, recoder <kurtulmeh...(a)gmail.com> wrote:
> Dear All,
> I have to write a program to compute:
> 2^q mod(p) and
> 2^(q-3) mod (p) where q and p are very large primes.
> I plan to use the "power-mod" algorithm to compute the 2 expressions seperately.
> Is there a way to compute
> 2^q mod(p) and derive 2^(q-3) mod (p) or vice versa ???

working mod p:

Trivially just multiply 2^q by 2^-3 to get 2^(q-3) or multiply the
latter by 2^3. You do know how to compute an inverse?
From: Chip Eastham on 4 Jun 2010 12:14
On Jun 4, 11:32 am, recoder <kurtulmeh...(a)gmail.com> wrote:
> Dear All,
> I have to write a program to compute:
> 2^q mod(p) and
> 2^(q-3) mod (p) where q and p are very large primes.
> I plan to use the "power-mod" algorithm to compute the 2 expressions seperately.
> Is there a way to compute
> 2^q mod(p) and derive 2^(q-3) mod (p) or vice versa ???

Instead of posting the same thing separately to
more than one newsgroup, it is considered better
etiquette to "crosspost", i.e. address it to all
the targeted newsgroups at once. That way replies
will be visible to all the groups and will not be
unnecessarily duplicated.

regards, chip
From: Arturo Magidin on 4 Jun 2010 12:14
On Jun 4, 10:32 am, recoder <kurtulmeh...(a)gmail.com> wrote:
> Dear All,
> I have to write a program to compute:
> 2^q mod(p) and
> 2^(q-3) mod (p) where q and p are very large primes.
> I plan to use the "power-mod" algorithm to compute the 2 expressions seperately.
> Is there a way to compute
> 2^q mod(p) and derive 2^(q-3) mod (p) or vice versa ???

I assume that q<p; otherwise, you can replace q with the remainder of
dividing q by p-1.

If you know 2^q and want 2^{q-3}, you just have to figure out the
inverse of 2^3 = 2*2^2 modulo p. This is a simple application of the
Euclidean algorithm, which in this case should be pretty quick. But it
would be far easier to compute 2^{q-3} first, and then just multiply
by 8 (modulo p of course).

I'm not sure which algorithm you mean by "power-mod". I hope you mean
the repeated squaring method.

--
Arturo Magidin
From: Pubkeybreaker on 4 Jun 2010 13:03
On Jun 4, 12:14 pm, Arturo Magidin <magi...(a)member.ams.org> wrote:
> On Jun 4, 10:32 am, recoder <kurtulmeh...(a)gmail.com> wrote:
>
> > Dear All,
> > I have to write a program to compute:
> > 2^q mod(p) and
> > 2^(q-3) mod (p) where q and p are very large primes.
> > I plan to use the "power-mod" algorithm to compute the 2 expressions seperately.
> > Is there a way to compute
> > 2^q mod(p) and derive 2^(q-3) mod (p) or vice versa ???
>
> I assume that q<p; otherwise, you can replace q with the remainder of
> dividing q by p-1.
>
> If you know 2^q and want 2^{q-3}, you just have to figure out the
> inverse of 2^3 = 2*2^2 modulo p. This is a simple application of the
> Euclidean algorithm, which in this case should be pretty quick. But it
> would be far easier to compute 2^{q-3} first, and then just multiply
> by 8 (modulo p of course).
>
> I'm not sure which algorithm you mean by "power-mod". I hope you mean
> the repeated squaring method.
>

Actually, (as you know), there are a variety of techniques that might
be
used in a "power_mod" (i.e. modular exponentiation) algorithm. It
might
be done by (as you suggest) just the binary method, but there are
also
hybrid methods (binary-trinary), decomposition methods (based on
factoring the
exponent), methods based on Fibonacci or Lucas chains, sliding
window methods
etc. etc. Finding the shortest possible chain is known to be NPC.
 |  Next  |  Last
Pages: 1 2
Prev: does this f(x,y) have to be a polynomial function of x and y?
Next: Tough queueing question