Could you please post a description of how to do long division of very
large numbers on a computer? I need one for the crypto program I'm making.

In article <1d54b7e4.0312241731.1b6bc46b@posting.google.com>, mike3 wrote:
For example, I needed a very simple RSA encryption with low exponent (3),
just once per session (basically to get a session key to a server), and
speed wasn't too much of a concern. Because this only involves three
mul/mod operations, there was no need for fancy algorithms, so this
ridiculously simple algorithm works (psuedocode):

// compute A*B mod N. Assumes A, B in [0,N)
bignum mod_mul( bignum A, bignum B, bignum N )
{
bignum R = 0;
while ( A != 0 )
{
if ( A & 1 )
{
R = R + B;
if ( R >= N )
R = R - N;
}
A = A / 2;
B = B * 2;
if ( B >= N )
B = B - N;
}
return R;
}

"Mok-Kong Shen" <mok-kong.shen@t-online.de> wrote in message
news:3FEAFD3D.96A8409@t-online.de...


Tom St Denis wrote:

"Mok-Kong Shen" <mok-kong.shen@t-online.de> wrote:

Spend some quarter of an hour and lots of your countrymen
(and even you yourself) might get benefits from that.

You don't think I spend time on my LT projects? I'm doing my bit in my
own
way.

It's a matter of 'global' optimization. If you are not
spending every minute available on that project (which
you seemingly aren't), then eventually having a better
public library system is likely worth much more personally
than what occassionally comes out from a usenet discussion
in my humble view.

I don't spend every waking minute working on LT projects because I'm still
in school. I have to also work to pay bills and of course i need time to
relax [re: play games].

The fact that I was working on my OMAC code on christmas day kinda shows I
got a bit of dedication to the project [cuz it's fun].

Tom

In article <1d54b7e4.0312241731.1b6bc46b@posting.google.com>, mike3 wrote:
Could you please post a description of how to do long division of very
large numbers on a computer? I need one for the crypto program I'm making.

First be sure you actually need long division. For many (most?) crypto
applications, you actually need mod, not div. One way to implement mod is
to divide and take the remainder, but there may be better ways.

In particular, often you only need mod, and only immediately after
multiplication, and then you can sometimes build the mod into the multiply.

For example, I needed a very simple RSA encryption with low exponent (3),
just once per session (basically to get a session key to a server), and
speed wasn't too much of a concern. Because this only involves three
mul/mod operations, there was no need for fancy algorithms, so this
ridiculously simple algorithm works (psuedocode):

// compute A*B mod N. Assumes A, B in [0,N)
bignum mod_mul( bignum A, bignum B, bignum N )
{
bignum R = 0;
while ( A != 0 )
{
if ( A & 1 )
{
R = R + B;
if ( R >= N )
R = R - N;
}
A = A / 2;
B = B * 2;
if ( B >= N )
B = B - N;
}
return R;
}

--
--Tim Smith

Good idea. Not only this is a good source to learn [*] but it might
be very useful to debug more complicated routines (since it allows
to compare results).

[*] If I remember well, in the cursus I followed, the study of
multi-precision divisions started with binary divisions.

Yes that works but it's ridiculously slow and not a good source to learn
how todo bignum math properly.

"Douglas A. Gwyn" <DAGwyn@null.net> wrote in message
news:bsf33d$8vs$1@ngspool-d02.news.aol.com...
"Tom St Denis" <tomstdenis@iahu.ca> wrote...
might as well be as insightful as Gwyn and suggest the poster go out
and
buy Knuth just to learn division.
That's not what I said.
No you said
"Look up "multiple precision arithmetic" in any decent text on algorithms,
for example Knuth's "The Art of Computer Programming"."
Where Knuth TAOCP is a COMMERCIAL product [each volume cost
about 65$ CDN].
Compared to say HAC which is freely available on the web [or even say the
LTM textbook].
Your post was not insightful at all. I mod you -1,overrated.

for example Kunth's "The Art of Computer Programming".

My possibly quite biased opinion is that the complete
Pascal package in Riesel is easier to read than other
sources.

That's a matter of opinion I guess.

I'd say my LTM code is very easy to follow.

I have yet to see a library in Ottawa [the capital of Canada I might add]
which is public access and has crypto journals, CS textbooks or anything of
higher academic value.

Of course if I said the sky was blue and water was wet you'd argue that too
I guess..

tomstdenis@iahu.ca says...

I have yet to see a library in Ottawa [the capital of Canada I might add]
which is public access and has crypto journals, CS textbooks or anything of
higher academic value.

Try a major University sometime. Anyone of them worth attending should
have very good library facilities.

In article <vkJGb.85823$2We1.23318@news04.bloor.is.net.cable.rogers.com>,
tomstdenis@iahu.ca says...
Of course if I said the sky was blue and water was wet you'd argue that
too
I guess..

Pot, kettle, black?

Every time someone responds to a question in this group, you disagree with
it. Just recently TAOCP was recommended as a source, to which you
disagreed. It's probably one of the very few books other than K&R1 or 2
that can be found in the personal library of almost every serious
professional programmer on the planet. Furthermore, as was said
elsewhere, any decent technical library will have it, in fact most will
have multiple copies.

Somehow, you simply had to disagree with it anyway. Why? Because your
book has a tiny intersection with the contents of TAOCP. Surely that's
not rational. You made your response, as did others. The beauty of
Usenet groups is that people can get the opinions of multiple people
and decide for themselves which to follow. You don't need to police
them all.

I have yet to see a library in Ottawa [the capital of Canada I might
add]
which is public access and has crypto journals, CS textbooks or anything
of
higher academic value.

Try a major University sometime. Anyone of them worth attending should
have very good library facilities.

In article <vkJGb.85823$2We1.23318@news04.bloor.is.net.cable.rogers.com>,
tomstdenis@iahu.ca says...

Of course if I said the sky was blue and water was wet you'd argue that too
I guess..


Pot, kettle, black?

Every time someone responds to a question in this group, you disagree with
it. Just recently TAOCP was recommended as a source, to which you
disagreed. It's probably one of the very few books other than K&R1 or 2
that can be found in the personal library of almost every serious
professional programmer on the planet. Furthermore, as was said
elsewhere, any decent technical library will have it, in fact most will
have multiple copies.

Somehow, you simply had to disagree with it anyway. Why? Because your
book has a tiny intersection with the contents of TAOCP. Surely that's
not rational. You made your response, as did others. The beauty of
Usenet groups is that people can get the opinions of multiple people
and decide for themselves which to follow. You don't need to police
them all.


Tom St. Denis is a disturbed youth who desperately needs help. I hope

Tom St. Denis is a disturbed youth who desperately needs help. I hope
someone at his community college can take him under his/her wing and
give him the counseling he needs. Sincerely.