[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Bignums

Ron Rivest asked:
>> When a byte string is treated as a bignum (for crypto use), should the
>> first byte given be considered the most-significant byte of the number,
>> or the least-significant byte?

At 10:06 AM 4/4/97 +0100, Paul Leyland wrote:
>I'd go for least significant first, despite the increased difficulty for
>humans to read the raw data, for efficiency reasons.
>
>It's *much* easier to get storage alignment correct if you know where
>the word boundaries are.  On a byte-wide machine, it doesn't matter
>which way you read the number; on anything else it can make an enormous
>difference.  Big-endian numbers would require the string to be read in,
>parsed completely, and then copied or moved to aligned storage.

Efficiency doesn't matter as much as readability.

There are different kinds of byte streams you'd use:
- human-readable character strings, either hex, decimal, or uuencode.
- internally-generated byte streams
- full-8-bit byte streams used for something else?

Internally-generated byte streams can be any format you like,
including non-portable formats; they're presumably 8-bit-bytes,
some of which might be 0, so you're not going to handle them as
null-terminated C character strings anyway - my preference would be
to have a length word and an word-aligned bigendian string,
0-padded at the front, but if your machine is little-endian, do that.

Human-readable strings, and conversion to internal formats,
don't take up much of the processing time of most programs,
so efficiency isn't as important as readability.
A 4096-bit word takes 1024 hexes, which will take far more time
to input from disk or terminal, or somewhat more time to input
from subroutine call, than it will to realign.  (And obviously 
converting from decimal means you don't care about efficiency anyway.)
And after you've converted and maybe realigned, you'll spend a lot more
time doing modmults in n**2 or nlogn time than doing I/O.
You could 0-pad to make realigning usually faster, but the people with 
64-bit machines may not be helped much (though it won't hurt them.)
Another upper bound is to do one strlen() at the beginning,
and then you can either work the hex conversion little-endian, 
or set your alignment and convert bigendendianly.  (And you can also
make the strlen() go faster by only checking every other character,
since you know a valid number has an even number of hexes.)

Other uses for 8-bit bytestreams?  Passing arguments to perl routines
may call for something a bit more standard, so people can share code;
I think the perl bignum.pl routines use bigendian hex, but I don't
remember if they require alignment, and I don't know if other perl
bignum users do the same thing or not.



#			Thanks;  Bill
# Bill Stewart, +1-415-442-2215 stewarts@ix.netcom.com
# You can get PGP outside the US at ftp.ox.ac.uk/pub/crypto/pgp
#     (If this is a mailing list, please Cc: me on replies.  Thanks.)
References: