Prev: Non-entity Theorem. By Aiya-Oba
Next: dood, why did BP use the phrase "fossilized fuel TM" with a cartoon dinosaur-into-a-drop-of-oil?
From: recoder on 23 Jun 2010 18:00
Is there a fast algorithm for calculating A/B mod (2^n)?
Is there a faster variant if the divisor is prime? A/ p mod (2^n) ?
Examples of modular division are:: 23 / 3 mod 128 = 93 or 2/5 mod 32 =
26.

Thanx in advance...
From: master1729 on 23 Jun 2010 14:29
> Is there a fast algorithm for calculating A/B mod
> (2^n)?
> Is there a faster variant if the divisor is prime? A/
> p mod (2^n) ?
> Examples of modular division are:: 23 / 3 mod 128 =
> 93 or 2/5 mod 32 =
> 26.
>
> Thanx in advance...

nice question.
From: Gerry Myerson on 23 Jun 2010 18:59
In article
<8df941d4-71e4-4f67-a75d-2854f48cfc12(a)a30g2000yqn.googlegroups.com>,
recoder <kurtulmehtap(a)gmail.com> wrote:

> Is there a fast algorithm for calculating A/B mod (2^n)?

So, you're trying to solve the linear congruence B x = A (mod 2^n).
The standard methods for solving linear congruences, B x = A (mod m),
are very fast. I don't see where having the modulus a power of 2
makes much difference.

--
Gerry Myerson (gerry(a)maths.mq.edi.ai) (i -> u for email)
From: Pubkeybreaker on 23 Jun 2010 20:38
On Jun 23, 6:59 pm, Gerry Myerson <ge...(a)maths.mq.edi.ai.i2u4email>
wrote:
> In article
> <8df941d4-71e4-4f67-a75d-2854f48cf...(a)a30g2000yqn.googlegroups.com>,
>
>  recoder <kurtulmeh...(a)gmail.com> wrote:
> > Is there a fast algorithm for calculating A/B mod (2^n)?
>
> So, you're trying to solve the linear congruence B x = A (mod 2^n).
> The standard methods for solving linear congruences, B x = A (mod m),
> are very fast. I don't see where having the modulus a power of 2
> makes much difference.


After computing B^-1 mod m via Extended Euclid, doing the final
multiplication A* B^-1 mod m will be much faster when m = 2^n. But
this will
be only a fraction of the total time.

OTOH, if 2^n is very large, computing B^-1 mod 2^n *might* be faster
by modular exponentiation using DWTs mod 2^n rather than by Extended
Euclid.
i.e. compute B^(phi(m) - 1) mod m.
From: Gerry Myerson on 23 Jun 2010 22:04
In article
<ec38da93-c2df-4b9d-a9cf-c5d618a66287(a)d37g2000yqm.googlegroups.com>,
Pubkeybreaker <pubkeybreaker(a)aol.com> wrote:

> On Jun 23, 6:59�pm, Gerry Myerson <ge...(a)maths.mq.edi.ai.i2u4email>
> wrote:
> > In article
> > <8df941d4-71e4-4f67-a75d-2854f48cf...(a)a30g2000yqn.googlegroups.com>,
> >
> > �recoder <kurtulmeh...(a)gmail.com> wrote:
> > > Is there a fast algorithm for calculating A/B mod (2^n)?
> >
> > So, you're trying to solve the linear congruence B x = A (mod 2^n).
> > The standard methods for solving linear congruences, B x = A (mod m),
> > are very fast. I don't see where having the modulus a power of 2
> > makes much difference.
>
>
> After computing B^-1 mod m via Extended Euclid, doing the final
> multiplication A* B^-1 mod m will be much faster when m = 2^n. But
> this will
> be only a fraction of the total time.
>
> OTOH, if 2^n is very large, computing B^-1 mod 2^n *might* be faster
> by modular exponentiation using DWTs mod 2^n rather than by Extended
> Euclid.
> i.e. compute B^(phi(m) - 1) mod m.

Sorry, what's DWT? Discrete Walsh Transform?

--
Gerry Myerson (gerry(a)maths.mq.edi.ai) (i -> u for email)
 | 
Pages: 1
Prev: Non-entity Theorem. By Aiya-Oba
Next: dood, why did BP use the phrase "fossilized fuel TM" with a cartoon dinosaur-into-a-drop-of-oil?