Cryptography-Digest Digest #888, Volume #12 Tue, 10 Oct 00 11:13:01 EDT
Contents:
Re: A new paper claiming P=NP (David C. Ullrich)
Re: A new paper claiming P=NP (David C. Ullrich)
Re: A new paper claiming P=NP (David C. Ullrich)
Re: The science of secrecy: Simple Substition cipher ("Miki Watts")
Re: are doubly encrypted files more secure than singly encrypted ones? (Edwin Woudt)
Re: Looking for paper ("John A. Malley")
Re: AES Runner ups (Tom St Denis)
Re: What is meant by non-Linear... (Tom St Denis)
Re: Why trust root CAs ? (Daniel James)
TC8 -- Yet More Work On It (Tom St Denis)
Re: The science of secrecy: Simple Substition cipher ([EMAIL PROTECTED])
Re: Rijndael test vectors (Paul Schlyter)
Re: AES Runner ups ("Sam Simpson")
My view of election. (SCOTT19U.ZIP_GUY)
Re: Error-correcting code ? ([EMAIL PROTECTED])
Re: working with huge numbers (Eric Young)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (David C. Ullrich)
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: Tue, 10 Oct 2000 13:22:29 GMT
Reply-To: [EMAIL PROTECTED]
On 9 Oct 2000 19:58:57 GMT, [EMAIL PROTECTED] (Jeremy Spinrad)
wrote:
>Some people are claiming that big O analyses do not do a good job of
>reflecting behavior of programs. Although I know of examples of this (e.g.
>simplex outperforms its worst case analysis in practice), I am
>curious as to whether saying this is common is at all justified. It certainly
>goes against my intuition that there are lots of programs out there such
>that the O(n^2) algorithm is beating up on the O(n) algorithm on inputs
>of large enough size so that time is a factor, as one poster implied.
I didn't _imply_ that, I _stated_ it. When someone talks
about O(this) and O(that) there's an unspecified constant. Does
it go against your intuition to imagine two algorithms to solve
the same problem, one of which takes on average time
100000000*n for input of size n while the other takes on
average time 2*n^2 for the same input? The first is O(n) and
the second is O(n^2) but the first is much faster until n gets
very large.
I've seen plenty of actual real-life examples of this
phenomenon. Probably not with numbers as extreme as
100000000 versus 2, but I've seen plenty of programmers
ask online questions about why doesn't the following work
for large strings - it works for small strings just fine. Maybe
it's a string-processing problem, maybe you want to
replace one character with another wherever it apears.
Suppose it's a language where actual loops in code are
fairly slow, while calls to builtin functions are reasonably
fast. In a pidgin of various languages to protect the
innocent:
def ReplaceAll1(data: string):
begin
result = CopyOf(data)
index = Pos(result, '&') //returns 0 if not found, say
while index > 0:
data[index] = '+'
index = Pos(result, '&')
return result
end
def ReplaceAll2(data: string):
begin
result:= ''
for j:=1 to Length(data):
if data[j] = '&' then result:= result + '+'
else result = result + data[j]
return result
end
Now (assuming a uniform distribution of characters
in the input) ReplaceAll1 is O(n^2) while ReplaceAll2 is O(n).
Depending on quirks of the implementation it could well be
that ReplaceAll1 is nonetheless much faster for small n - there
are just n/256 function calls and n/256 loop iterations, while
ReplaceAll2 has n loop iterations.
Not just theoretical, I've seen it happen several
times that professional programmers ask why ReplaceAll1
doesn't work for large strings. (Usually in these cases
they had no idea what the problem was - they hadn't
rejected ReplaceAll2, the idea of doing it that way
never occured to them, because if you're writing in
language xxx you're not supposed to be doing any
actual programming. But the cluelessness of xxx
programmers is irrelevant. The fact that ReplaceAll2
is actually faster even for small n in language xxx is also
irrelevant - in fact ReplaceAll2 _will_ be slower for small
n in language xxxx (where as it happens programmers
are typically not so clueless).)
And yes, of course ReplaceAll1 becomes O(n)
if the Pos function takes three arguments: data, ToFind, and
IndexToStartLooking. And in most actual implementations
ReplaceAll2 could be much improved by allocating one
large string at the start instead of using all those
concatentation. None of which has anything to do
with the point I was trying to make, which is that you
cannot tell whether an algorithm executes in polynomial
time just by looking at the performance for n less than
1000000000000000000.
(You _can_ tell about the performance for
n < 1000000000 by looking at the performance
for n < 1000000000. And that's often all that a
person would care about. But that has nothing to
do with this P/NP stuff. (And it does turn out
that the asymptotic performance matters after
all: someone applies the algorithm to much
longer strings than it was tested on. I've seen
it actually happen in the real world.)
>As to the P = NP paper; there is an entirely different reason for having
>an implementation. Previous claims of this types have proved to be moving
>targets; a hole is found by a reviewer, and the author adds a patch to the
>hole and still claims an algorithm. It would be nice to have a program at
>least so we could check whether the author could make the program answer
>the problem correctly before we do the difficult job of reviewing the paper.
Of course an actual program is a good idea. But you
cannot "check" that the program runs in polynomial time
by _running_ it - to check that requires an analysis of the
algorithm.
Again: You _can_ check that the program gives
acceptable results for the data you're going to be applying
it to by running it. But that says nothing whatever
about whether it runs in polynomial time.
>Jerry Spinrad
>
------------------------------
From: [EMAIL PROTECTED] (David C. Ullrich)
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: Tue, 10 Oct 2000 13:24:46 GMT
Reply-To: [EMAIL PROTECTED]
On Tue, 10 Oct 2000 08:36:29 GMT, David Bernier <[EMAIL PROTECTED]>
wrote:
[...]
>
>Suppose P is a proof in ZFC of FLT similar to Wiles', but with
>proofs of all lemmas and all background material included
>(i.e. a self-contained proof). I wonder what the order of magnitude
>of the length of P might be...
It's O(1).
>David Bernier
>
>
>Sent via Deja.com http://www.deja.com/
>Before you buy.
------------------------------
From: [EMAIL PROTECTED] (David C. Ullrich)
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: Tue, 10 Oct 2000 13:30:15 GMT
Reply-To: [EMAIL PROTECTED]
On Tue, 10 Oct 2000 00:34:56 +0300, Stas Busygin
<[EMAIL PROTECTED]> wrote:
>"David C. Ullrich" wrote:
>>
>> On Mon, 09 Oct 2000 04:47:22 GMT, Rajarshi Ray <[EMAIL PROTECTED]>
>> wrote:
>>
>> [...]
>> >Is it not possible to implement the presented algorithm and try it out
>> >on examples to see the growth rate, just as a preliminary check?
>>
>> No. Suppose that a(n) is a sequence of integers and
>> a(n) = 2^(2^(^n)) for all n less than 10^(10^10). Does a(n)
>> have polynomial growth?
>The complexity of the algorithm is bounded as O(n^6) by the author.
??? I was talking in general, not referring to the specific
algorithm that started all this.
Simply trying to point out that one cannot check whether
an algorithm runs in polynomial time by running it. (If one argued
that bad polynomials and good exponentials just didn't happen
in practice I wouldn't argue with that - although it might not
be that clearcut, that doesn't say anything about whether you
can check whether an algorithm runs in polynomial time by
running it, it says something about whether that's the important
question.)
>It's because the so-called vertex-saturating takes not more than n
>steps and repeats not more than n times according to author's
>claims (n is the number of graph vertices). As the nested loop of
>the saturating has O(n^4) complexity in any case (this assertion is
>obvious), we need to keep an eye only on those two bounds claimed
>to be n. So, no trouble to verify the complexity on particular
>given instances when there will be a program.
>
>
>Best wishes,
>
>Stas Busygin
>email: [EMAIL PROTECTED]
>WWW: http://www.busygin.dp.ua
------------------------------
From: "Miki Watts" <[EMAIL PROTECTED]>
Subject: Re: The science of secrecy: Simple Substition cipher
Date: Tue, 10 Oct 2000 08:06:56 +0200
> Dear group,
> Channel 4 (UK) are running a series of 'The science of secrecy'
> and after the show mentioned a cipher competition on thier website
> www.channel4.co.uk/nextstep. The message uses a substition cipher
> where the letters are pared ie if cT 'A' = pT 'T' then cT 'T' = pT 'A'.
>
> The problem is i cant make sense of the last line.
> Can anyone help?
>
> -TIA-
>
> Cipher:
> Iroho awg genoirtms tm iro iemo
> ez irtg meio irwi swko no showi
> jmowgtmogg. (Poiioh 'P')
> 'Iro Sepx Qjs' qc O.W. Leo
>
>
> Plaintext:
> There was something in the tone
> of this note that gave me great
> uneasiness. (Letter 'L')
> ????????????????????????????
Deciphering what i can:
'The gol? ?ug' ?? E.A. ?oe
I'd say: "The gold bug" E.A. Poe
------------------------------
From: Edwin Woudt <[EMAIL PROTECTED]>
Subject: Re: are doubly encrypted files more secure than singly encrypted ones?
Date: Tue, 10 Oct 2000 15:31:28 +0200
John Myre wrote:
>
> Now suppose on the other hand that you don't armor
> until after the last encryption. The bad guys have a
> much harder task, because they can't easily tell if
> they have broken the last round of decryption. If the
> encryption is fairly good, so that there are no useful
> statistics in the output, then the bad guys have to
> break all the rounds at once.
The output format used by GnuPG (OpenPGP/RFC2440) can be quite easy
distinguished from random data due to the inclusion of header and length
bytes. So multiple encryption without armouring is also not that useful.
Edwin
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Looking for paper
Date: Tue, 10 Oct 2000 06:33:34 -0700
Benjamin Goldberg wrote:
>
> I recall seeing a paper where data was compressed using a static huffman
> tree (with 0 and 1 labels on the branches randomly swapped), and the
> tree hidden... and analysis was done to attempt to recover the tree. I
> don't, however, recall *where* I saw the paper... I think it was a .ps,
> or .ps.gz, not a .pdf or .html document.
>
Perhaps it's the Master's Thesis from Mojdeh Mohtashemi, "On the
Cryptanalysis of Huffman Codes" June, 1992, at:
http://theory.lcs.mit.edu/~cis/theses/mohtashemi-masters.ps
john A. Malley
[EMAIL PROTECTED]
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: AES Runner ups
Date: Tue, 10 Oct 2000 13:29:05 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (John Savard) wrote:
> On Tue, 10 Oct 2000 11:12:06 +0200, Runu Knips
> <[EMAIL PROTECTED]> wrote, in part:
>
> >Twofish is a redesign of Blowfish
>
> I'm not sure they really share much except the name.
>
> >Btw, another really good cipher is AFAIK CAST-128 which
> >didn't made it to the second round but is used, for
> >example, in GnuPG.
>
> I remember someone correcting me, telling me that the name of the AES
> candidate was CAST-256. However, like RC6, I believe that it requires
> licensing as well.
>
> Among the non-finalist designs, one that is freely available, and
> which should be secure (but its key schedule may be iffy), is SAFER+,
> I believe. (Now _there's_ a cipher whose rounds could be alternated
> with those of Rijndael...)
SAFER+ is most likely perfectly secure, but it is very slow and not
perticularly usefull in hardware. It rocks in software if speed is not
crucial. It's a nice design too.
It's nothing like Rijndael. SAFER+ is not a "square" cipher.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: What is meant by non-Linear...
Date: Tue, 10 Oct 2000 13:27:09 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (John Savard) wrote:
> On Mon, 9 Oct 2000 17:59:05 +0100, "Rob Marston" <[EMAIL PROTECTED]>
> wrote, in part:
>
> >I assume it means that where
> >
> > y = f(x)
> >
> >is so complex that
> >
> > x = F(y)
> >
> >is difficult/impossible to compute? Right or Wrong?
>
> No. Its meaning is much weaker than that. It just means that y = f(x)
> can't be expressed as y = a*x + b, or, usually, that y also can't be
> expressed as a function of x that involves an XOR and a transpose or
> masking of bits as well. Thus, while it is easy to invert each of the
> rows in the DES S-boxes, they are designed so that "no S-box is a
> linear or affine function of its input".
Aw but in f(x) = ax + b the upper bits can be nonlinear.
Typically in crypto we are talking about "some of the input bits"
and "some of the output bits". For example on a 4x4 sbox we could have
the folling linear *approximation* y0 = x0 xor x1 xor x3 xor 1. As
compared to y0 = x1(not x0) or x3(not x1)x2 ...
So a linear combination of the inputs and output bits must hold with a
probability bounded by 1/2 for a function to be nonlinear. With a 4x4
sbox there are 15x15 ways to combine the linear functions so you have
to make sure that all 225 linear combinations are balanced (i.e occur
with a prob of 1/2)
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Daniel James <[EMAIL PROTECTED]>
Subject: Re: Why trust root CAs ?
Date: Tue, 10 Oct 2000 14:48:40 +0100
Reply-To: [EMAIL PROTECTED]
In article <SJrE5.24117$[EMAIL PROTECTED]>, Lyalc wrote:
> Why does every sniffer and every server along the line need to see your name
> and address that is embodied in the certificate?
>
> Only you and the delivery agent need that information, yet certificates give
> it all away, every time the certificate is used. No ifs, no buts,
> privacy=zero.
Most of the certificates in use today associate a public key with an identity
that is expressed in terms of a person's name and address. X.509 rather
presupposes that that's the sort of thing people will want to do when it sets
out the fields that can exist in a DName. It doesn't really have to be that
way - a certificate needs /something/ to identify the owner, but that
something doesn't have to contain a name and address as long as it's unique to
the certificate's owner (among certificates issued by that CA).
If the whole message - including the sender's certificate - is encrypted
(using the recipient's public key, which the sender believes he can trust
because he obtained it from a certificate signed by ... etc.) the snooper can
gain nothing.
Cheers,
Daniel.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: TC8 -- Yet More Work On It
Date: Tue, 10 Oct 2000 14:11:08 GMT
I worked on TC8 quite a bit last night. I fixed the key schedule
problem, but I also switched the algorithm around. I use a fixed 4x4
sbox to make a keydependant 8x8. I take the key (assuming it's a
multiple of 8 bits) and use the key as round keys in a 8-bit Feistel.
So each byte provides two round keys. With a 64-bit key the sbox
generation has 16 rounds, with a 192-bit key (the max) it is a 48 round
feistel.
While the sbox Feistel is a slow process it can be precomputed. Since
it's very small hardware can just roll up the feistel to have a mid-
latency key schedule, the 280 bytes the key takes up is certainly not a
huge problem but does raise costs.
I did this because I can prove certain things about it. For example
the best differential characteristic with a 64-bit key is 2^-20 which
means that any given differential on the 8x8 sbox created will hold
with a prob of about 1/255 over all keys. Similar idea holds for
linear attacks.
I also changed the key schedule to expand the user key to 24 bytes as
required, but I am still doing the sbox[key + rnd] as the round key
schedule.
I will post the source and the paper I am working on later this week.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: The science of secrecy: Simple Substition cipher
Date: Tue, 10 Oct 2000 14:11:29 GMT
I couldn't agree more. The code took me at most 3 minutes to crack and
the answer was way too obvious. After all, how many five letter
composers are there with an 'L' in their name?
Eager with the buzz of thinking I was perhaps a genius and nobody else
would have the CD at home I emailed my answer off straight away only to
find that the email address they've given is duff. I got the 'failed
delivery' message back the next day. I guess they haven't bothered to
register it yet thinking that it would be ages before anybody cracks it.
Ha!
Jeremy Taylor
In article <8rtc4k$d6h$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Scott Craver) wrote:
> KK <[EMAIL PROTECTED]> wrote:
>
> >Dear group,
> >Channel 4 (UK) are running a series of 'The science of secrecy'
> >and after the show mentioned a cipher competition on thier website
> >www.channel4.co.uk/nextstep.
>
> This is going to get very bad very fast.
>
> My brother already sent me the URL (neither of us are UK
residents,
> so we aren't eligible for the prize,) and I already know the
> trip-to-Egypt-winning phrase. I must not be alone.
>
> There will be 5 ciphertexts distributed over the course of the
> month, each hinting at a piece of the big final answer that
wins
> the prize. But within 10 minutes of peering at the 1st
ciphertext,
> I knew the big final answer.
>
> It didn't hurt that I had it on CD at home (the final answer
> is the name of a piece of music.) But then, anyone with any
> CD by this one composer surely has this one piece of music.
>
> <SNOBBERY SUBTLE="no"> And anyone with a browser to aim at a
> search engine will figure it out without having to be cultured.
> </SNOBBERY>
>
> >The message uses a substition cipher
> >where the letters are pared ie if cT 'A' = pT 'T' then cT 'T' = pT
'A'.
> >
> >The problem is i cant make sense of the last line.
> >Can anyone help?
>
> Why don't you just use the substitutions you already learned
> from the ciphertext above?
>
> >-TIA-
>
> Cej'ho aopyeno.
>
> -Scott
>
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Rijndael test vectors
Date: 10 Oct 2000 15:58:47 +0200
In article <[EMAIL PROTECTED]>,
Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
>Roger Schlafly wrote:
>>
>> Brian Gladman wrote:
>> > Welcome to the endian world of AES!
>> > A world I hope we can remove by getting the specification right on
>> > such matters.
>>
>> Yes. I once implemented DES based on the spec, and then discovered
>> that others used the bits in a different order. It seems the
>> official spec talked about bits, but not bytes, leaving the
>> order of bits in a byte ambiguous.
>
>That's because DES was originally intended to ONLY be used in hardware.
>Who cares about bytes, when what you're putting together is gates?
> Roger Schlafly wrote:
>
>> Brian Gladman wrote:
>>> Welcome to the endian world of AES!
>>> A world I hope we can remove by getting the specification right on
>>> such matters.
>>
>> Yes. I once implemented DES based on the spec, and then discovered
>> that others used the bits in a different order. It seems the
>> official spec talked about bits, but not bytes, leaving the
>> order of bits in a byte ambiguous.
>
> That's because DES was originally intended to ONLY be used in hardware.
> Who cares about bytes, when what you're putting together is gates?
So DES defines how to encrypt/decrypt a bitstream them. That's fine,
if you already have a bitstream you want to en/decrypt (e.g. a serial
connection).
But if a hardware implementation of DES is to be used to en/decrypt
actual data, in the form of bytes on a computer disk file, one must
specify the conversion from the disk file data to the bit stream data.
Which brings up two questions:
1. In which order should the bytes be sent to the bitstream? I guess
everyone takes for granted that the byte with the lowest address
should be sent first. Nevertheless one could choose to send the bytes
in the other order, so this must really be specified, even if it's
implicitly assumed to be that way.
2. In which order should the bits within each byte be sent to the
bitstream? This bit order isn't as obvious as the byte order above,
and different people obviosuly make different assumptions here, in
the absence of a specification.
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Subject: Re: AES Runner ups
Date: Tue, 10 Oct 2000 15:24:23 +0100
Runu Knips <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
<SNIP>
> Btw, another really good cipher is AFAIK CAST-128 which
> didn't made it to the second round but is used, for
> example, in GnuPG.
CAST128 (AKA CAST5) is a 64-bit block /128-bit key cipher predating
AES by several years and certainly is employed in GnuPG and NAI/PGP.
I guess you mean CAST-256, which isn't (AFAIK) widely deployed at
all...........
--
Sam Simpson
Comms Analyst
http://www.scramdisk.clara.net/ for ScramDisk hard-drive encryption &
Delphi Crypto Components. PGP Keys available at the same site.
If you're wondering why I don't reply to Sternlight, it's because
he's kill filed. See http://www.openpgp.net/FUD for why!
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Crossposted-To: talk.politics.crypto
Subject: My view of election.
Date: 10 Oct 2000 14:36:59 GMT
I worked at a base and have talked to people since I have
left. If you think we are safer after Clinton and want more
of the same vote for Gore. He thinks things are great.
But check out the link below
http://www.opinionjournal.com/columnists/mhelprin/?id=65000400
It is a fact since I retired most honest people I know
who have been involved in this area agree, We are going down
hill very fast. I am not sure that Bush even has an idea
how bad it is. But think before you vote.
If you think this is a poor topic to write about don't read it.
I feel Gore will do more to keep crypto closed then Bush. If you
feel defferent. Write a response why Gore would be better for us.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott LATEST UPDATED source for scott*u.zip
http://radiusnet.net/crypto/ then look for
sub directory scott after pressing CRYPTO
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Error-correcting code ?
Date: Tue, 10 Oct 2000 14:53:05 GMT
Peter Pearson <[EMAIL PROTECTED]> wrote:
: [EMAIL PROTECTED] wrote:
:> Does anyone know an algorithm, simple or well-documented (like, source code)
:> enough that an idiot like me can implement it, for error-correcting short
:> strings of digits ?
:> So that if someone writes down "123454321" and someone reads it back as
:> "123454327" or "lZ34S43Zl" that I can recover the original number.
: I'm sure there are more sophisticated approaches (c'mon, guys, help
: me out), but a simple technique is to add two check digits and
: to insist that all legal strings be multiples of, say, 97. When
I chased down the references I could understand (as I said, I'm
a few decades out of practice at this kind of thing - math - and
a bit stupid as a result) and found an explanation for a triangle
code. I wrote an awful implementation of a 9 data-digit, 5 check-digit
code using c = (sum dn) % 10 which works mostly - at least, it
will correct 1 wrong digit and maybe 1 missing digit and maybe detect
2 or more errors, though 2 wrong check digits seems to often
correct the wrong error. I put the check digits after the data; is there
any advantage to interspersing them in the data digits ?
Is there a better method than c1 = (d4+d5+d6+d3) % 10 etc. ?
I have to confess I can't understand the stuff about spheres in Hamming code
and was unable to fill in the "obvious" blanks in John Bailey's
method :-(
--
Andrew Daviel
PGP id 0xC7624B49
The geographic search engine at http://geotags.com
is looking for content.
------------------------------
From: Eric Young <[EMAIL PROTECTED]>
Subject: Re: working with huge numbers
Date: Tue, 10 Oct 2000 14:54:22 GMT
Mok-Kong Shen wrote:
> DeSilva wrote:
> > I would like to implement some encryption into software, but have come
> > across the obvious problem of doing math on huge numbers. How to device two
> > 500 digit numbers with eachother..
> Read e.g. the book by Knuth, The Art of Computer Programming,
> vol. 2. Your question has been often asked. You could dig
> out that in the archive (if you can). There are well-debugged
> packages. You don't have to re-invent the wheel.
Well, in my case I originally wrote my bignum library specifically to learn
how to do large number division. I was intimidated by it, so I took it as
a challenge to learn how it was done :-).
Knuth definitely has the details on how to do quite a few of the algorithms
but for fast multiplication in the range crypto needs, and specifically
exponentiations, other techniques are described in other places which give
better returns. I'm still experimenting with bignum algorithms 6 years
down the track (and I'm still improving the a^b%m performance; 10-15% in
the last few months :-)
eric
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
