Home > Archive > Scheme > November 2005 > primes question generated from SICP footnote
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
primes question generated from SICP footnote
|
|
| Bradley Buszard 2005-11-03, 9:57 pm |
| I'm having trouble sorting out the expmod procedure on p. 51, probably
because I don't know modular algebra. The key to my problem, I think, is
in note 46 at the bottom of the page, which claims:
xy mod m = [(x mod m)(y mod m)] mod m
Fine. That explains the transformation of the "even?" branch of the cond thus:
b^e = b(e^2) * b(e^2); hence
(b^e) mod m = {[b(e^2) mod m] ^ 2} mod m
But in the (else) branch, i.e. the odd branch, the algorithm given is this:
{b * [b^(e - 1) mod m] } mod m
when the expansion of note 46 implies that we should have:
{ (b mod m) * [b^(e - 1) mod m] } mod m
Now these two versions of the odd branch can be reconciled if one can
prove that
[a * (b mod m)] mod m = (ab) mod m
either for all a, b, and m or for some special case that always
pertains here. I've tried a few test cases, and this last equation has
so far always proven true, but I have no idea why this should be so.
Would anyone with a better understanding of the math care to enlighten me?
| |
| Pascal Bourguignon 2005-11-04, 3:57 am |
| Bradley Buszard <bradley.buszard@cnu.edu> writes:
> I'm having trouble sorting out the expmod procedure on p. 51, probably
> because I don't know modular algebra. The key to my problem, I think, is
> in note 46 at the bottom of the page, which claims:
>
> xy mod m = [(x mod m)(y mod m)] mod m (1)
> [...]
> [a * (b mod m)] mod m = (ab) mod m (2)
>
> either for all a, b, and m or for some special case that always
> pertains here. I've tried a few test cases, and this last equation has
> so far always proven true, but I have no idea why this should be so.
>
> Would anyone with a better understanding of the math care to enlighten me?
Revert to the definition:
a mod m = d <=> Ek in Z, a=(k*m+d) (def)
So you can deduce easily this theorem:
a mod m = b mod m <=> (a-b) mod m = 0 (th1)
[a(b mod m)] mod m = (ab) mod m (2)
<=> [a(b mod m) - (ab) mod m] = 0 per (th1)
<=> [ a(b mod m) - (a mod m)(b mod m) ] mod m = 0 per (1)
<=> Ek a(b mod m) - (a mod m)(b mod m) = km+0 per (def)
<=> Ek [a-(a mod m)](b mod m) = km (3) per distributivity
Per definition (def), Eq, a = qm + (a mod m), therefore:
(3)
<=> Ek Eq ( qm+(a mod m) - (a mod m)) (b mod m) = km per (def)
<=> Ek Eq qm*(b mod m) = km
<=> Ek Eq q*(b mod m) = k
<=> TRUE
For example, with: q=1 and k=(b mod m)
--
__Pascal Bourguignon__ http://www.informatimago.com/
Small brave carnivores
Kill pine cones and mosquitoes
Fear vacuum cleaner
| |
| Joe Marshall 2005-11-04, 3:57 am |
| Bradley Buszard <bradley.buszard@cnu.edu> writes:
> I'm having trouble sorting out the expmod procedure on p. 51, probably
> because I don't know modular algebra. The key to my problem, I think, is
> in note 46 at the bottom of the page, which claims:
>
> xy mod m = [(x mod m)(y mod m)] mod m
>
> Fine. That explains the transformation of the "even?" branch of the cond thus:
>
> b^e = b(e^2) * b(e^2); hence
> (b^e) mod m = {[b(e^2) mod m] ^ 2} mod m
>
> But in the (else) branch, i.e. the odd branch, the algorithm given is this:
>
> {b * [b^(e - 1) mod m] } mod m
>
> when the expansion of note 46 implies that we should have:
>
> { (b mod m) * [b^(e - 1) mod m] } mod m
Yes, but since
b < m
then
b mod m = b
| |
| Bradley Buszard 2005-11-07, 10:03 pm |
| On Fri, 04 Nov 2005 05:32:59 +0100, Pascal Bourguignon wrote:
>
> [a(b mod m)] mod m = (ab) mod m (2)
>
> <=> [a(b mod m) - (ab) mod m] = 0 per (th1)
My thanks for the reply; shouldn't this step instead be:
[a(b mod m) - (ab)] mod m = 0
??
| |
| Bradley Buszard 2005-11-07, 10:03 pm |
| On Thu, 03 Nov 2005 23:36:59 -0500, Joe Marshall wrote:
> Yes, but since
> b < m
> then
> b mod m = b
Sure enough. For whatever reason I was taking it as m, not b. Thanks.
|
|
|
|
|