Cryptography-Digest Digest #971, Volume #13 Thu, 22 Mar 01 14:13:00 EST
Contents:
Re: Multiple encryption, more secure ciphers (John Myre)
Re: One-time Pad really unbreakable? (Tim Tyler)
Re: Speed of factoring (John Myre)
Re: A future supercomputer (Darren New)
Re: Speed of factoring (John Myre)
Re: NSA in the news on CNN (JPeschel)
Re: Fill-in-the-blank codes (similar to Error-correcting codes) (Dilip V. Sarwate)
Re: Fill-in-the-blank codes (similar to Error-correcting codes) (Jim Reeds)
Re: redodancy (amateur)
Re: What happens when RSA keys don't use primes? (Stefan Katzenbeisser)
Re: Fast and Easy crypt send (amateur)
Re: Idea (amateur)
Re: Most secure way to add passphrase verification to "CipherSaber" (Yamaneko)
Re: Most secure way to add passphrase verification to "CipherSaber" (Yamaneko)
How to avoid known-plaintext attack (Re: Most secure way to add (Yamaneko)
Re: Most secure way to add passphrase verification to "CipherSaber" ("John L. Allen")
Re: Most secure way to add passphrase verification to "CipherSaber" ("Joseph
Ashwood")
Re: ECC rather than PGP ? ("Joseph Ashwood")
Crypto Contest? ("Tom St Denis")
Re: can a remailer send a message to multiple people? (William Hugh Murray)
Re: Idea (Jeffrey Williams)
Re: Speed of factoring (Bill Unruh)
----------------------------------------------------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Multiple encryption, more secure ciphers
Date: Thu, 22 Mar 2001 09:10:15 -0700
Frank Gerlach wrote:
<snip>
> Never ever make the keys functionally dependent
"Never ever" is probably too strong. After all, we quite
commonly accept "pseudo-random" values when we really want
"random", because our entropy pool is too small. That is,
we stretch our entropy into multiple outputs.
> (which includes the
> trivial dependency f(k1)=k2 with k1=k2).
I'll buy that, certainly. But if f() is "strong", we can
do stuff like k(i) = f(k0,i). For example, use your
cipher in counter mode to produce the keys needed for the
actual message encryption. This is essentially what an
entropy-stretching "random" pool does. The point is that
k0 is not used for message encryption at all, only to
produce other keys, which then "appear" to be independant.
I imagine that if you want to extend this, you could.
JM
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: One-time Pad really unbreakable?
Reply-To: [EMAIL PROTECTED]
Date: Thu, 22 Mar 2001 16:18:01 GMT
Jonathan Thornburg <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:>There's no evidence /against/ it either - it is quite consistent with
:>all of your observations. It is quite simple - I would not like to be
:>told to wield Occam's rasor in this instance. When there's no evidence
:>either way, both options must remain possibilities - which was my point.
: There's also no evidence either fore or against against the hypothesis
: that an invisble elf is sitting on my forehead directing my actions.
: This hypothesis too is quite consistent with all observations of my
: behavior. Do you take it seriously? Should anyone else?
The question was whether it is *impossible*. Your example seems to be
a possibility. I recommend you think again about what impossibility means.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Speed of factoring
Date: Thu, 22 Mar 2001 09:24:50 -0700
Soeren Gammelmark wrote:
<snip>
> What I don't understand is the 0(1)?
<snip>
It isn't a zero, but the letter (oh). It comes from the
arena of computational complexity, and is a way of denoting
the "order of magnitude" of how long something takes, based
on the size of the problem. (What's worse, from the standpoint
of typography, is that there are actually *three* functions
like this: "big oh", "little oh", and "omega". Yuck.)
In this particular case, "O(1)" means "limited by some
constant". That is, there is some constant you could use
there in the formula that would bound the time taken even
when trying to factor, say, numbers with billions of digits.
The formula itself gives no indication of what the constant
is, though.
JM
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: Re: A future supercomputer
Date: Thu, 22 Mar 2001 16:35:48 GMT
JCA wrote:
> There is probably so much we ignore on the human brain's internal
> working that the computing power afforded by Blue Gene is likely to make
> no substantial difference in the effort to attain the goal you mention. Hence
> my skepticism about Blue Gene being a solid foundation, etc.
Most times I've seen computing power compared with a brain, it's something
along the lines of "each synapse is worth N bits" and then you count the
synapses and the number of bits in the omputer. Or say "each nerve can fire
Q times per second, and there are W nerves, so the brain does Q*W MIPS" or
something. In other words, I've never seen a comparison where the actual
structure of the brain is taken into acount. Nor do such comparisons take
into account the rest of the body, like the spinal cord, the eyes, the motor
nerves, and so on.
Hence, it's generally as silly as saying a pocket 4-banger calculator is as
powerful as a 6502, because the 4-banger can support 8 digits and the 6502
has only 6 bytes of internal registers.
--
Darren New / Senior MTS & Free Radical / Invisible Worlds Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Speed of factoring
Date: Thu, 22 Mar 2001 09:34:48 -0700
John Myre wrote:
<snip>
> In this particular case, "O(1)" means "limited by some
> constant".
<snip>
And so "1 + O(1)" means "some constant at least as large
as one".
JM
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Date: 22 Mar 2001 17:03:33 GMT
Subject: Re: NSA in the news on CNN
Mok-Kong Shen [EMAIL PROTECTED] writes, in part:
>So they set up businesses ranging from pizza restaurants
>(very common) to banks (few), which solves simultaneously
>the financial, lodging, etc. etc. problems. Wouldn't it be
>wise for the government secret agencies to do the same, at
>least for the purpose of reducing the budgets?
I believe the NSA is relying, primarily, on its secret, upcoming bake sales
for most of its funding. It is anticapting huge revenues from its
cryptographically-strong hash brownies.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
Crossposted-To: sci.math,comp.dsp
Subject: Re: Fill-in-the-blank codes (similar to Error-correcting codes)
From: [EMAIL PROTECTED] (Dilip V. Sarwate)
Date: Thu, 22 Mar 2001 17:14:47 GMT
Jyrki Lahtonen <[EMAIL PROTECTED]> writes:
>Extending a decoding algorithm to correct erasures as well as
>errors is not trivial, but has been solved, e.g. for BCH-codes.
>If you don't mind doubling the time-complexity of the decoding
>algorithm then a trivial way to do it is to make two decoding
>attempts: for the first attempt replace all the erasures with
>zeros, for the second attempt replace all the erasures with
>ones. In at least one of the attempts at least one half of the
>erasure were "corrected" by the replacement, and this is
>sufficient for the errors-only decoding algorithm!
Let's be a bit careful here. Suppose that we are using a
(2^m -1, 2^m - 1 - m) Hamming code with m paritycheck bits.
An important property of this code is that ANY binary received
word (of length 2^m - 1) is at Hamming distance 1 or less from
a (unique) codeword of the Hamming code.
Suppose that two bits (both zeroes) happened to get erased.
Then, when both erasures are replaced by zeroes, the "received"
word is in fact the correct codeword, and the decoder will
successfully find it. On the second try, the "received" word
will have ones where the erasures were, and will be decoded
into some OTHER codeword (at Hamming distance 3 from the correct
codeword.) Note that neither of the ones that replaced the erasures
will be changed during the decoding. Thus, both decodings will
produce valid codewords and it is not immediately obvious which is
the correct one. The receiver chooses between them using the
criterion that the decoding that corrected fewer errors is the
one that has produced the right answer.
Note that essentially the same argument applies when two ones get
erased. On the other hand, if a zero and a one got erased, then
both decodings will correct a single error, and produce the same
(correct) codeword. Both decodings have corrected the same number
of errors, but either choice of codeword is acceptable :-).
--
.-. .-. .-. .-. .-. .-. .-.
/ D \ I / L \ I / P \ / S \ A / R \ W / A \ T / E \
`-' `-' `-' `-' `-' `-'
------------------------------
Crossposted-To: sci.math,comp.dsp
From: [EMAIL PROTECTED] (Jim Reeds)
Subject: Re: Fill-in-the-blank codes (similar to Error-correcting codes)
Date: Thu, 22 Mar 2001 17:25:59 GMT
|> On Wed, 21 Mar 2001 21:07:54 -0500, Bob Harris
|> <[EMAIL PROTECTED]> wrote:
...
|> >
|> >The idea is to have a code that includes two redundant bits, and be able to
|> >'correct' any two errors, with the additional knowledge of which two bits
|> >might be errant.
|> >
|> >For example, if I wanted to have a 7-bit code (2 of the bits are redundant),
|> >I might receive 0 0 x 0 x 1 0, where 'x' indicates missing bits. I need to
|> >be able to fill in the missing bits (which is why I called this 'fill in the
|> >blanks).
|>
I believe the following recipe works. Notation: your code
words have n bits, they obey k check equations. You want the
code to correct up to d deletions. The check matrix C has k
rows and n columns. The code words w all obey the check
equation C w = 0.
You want C to have the property that all k by d submatrices of
C have full rank.
If d = 1, you must chose k=1 and C=(1 1 1 1 1 ... 1),
all 1 by 1 submatrices of which are the same & of full rank.
If d = 2, you need for all the columns of C to be non zero and
distinct; this means that (2^k-1) >= n. But since we are working
in binary, these conditions on C are sufficient, as well.
So if n=7, we need 3 check equations, and the matrix C is
(up to reordering of the columns) completely determined.
For d>2 things get more interesting: C must be the parity check
matrix of a code of minimum distance >= d+1.
--
Jim Reeds, AT&T Labs - Research
Shannon Laboratory, Room C229, Building 103
180 Park Avenue, Florham Park, NJ 07932-0971, USA
[EMAIL PROTECTED], phone: +1 973 360 8414, fax: +1 973 360 8178
------------------------------
From: amateur <[EMAIL PROTECTED]>
Subject: Re: redodancy
Date: Thu, 22 Mar 2001 12:36:35 -0400
Transcodification eliminate redundancy.
So, what is a difference?
dexMilano wrote:
>
> This doesn't remove redodancy. It's a transcodification.
> dex
> "amateur" <[EMAIL PROTECTED]> ha scritto nel messaggio
> news:[EMAIL PROTECTED]...
> > Simple. You assign specific code to every character.
> > It's easy.
> >
> >
> > dexMilano wrote:
> > >
> > > Is there some simple algoritm to remove redodancy in text?
> > > I tried ZIP but it's too heavy.
> > >
> > > Thx
> > >
> > > dex
------------------------------
Date: Thu, 22 Mar 2001 18:41:21 +0100
From: Stefan Katzenbeisser <[EMAIL PROTECTED]>
Subject: Re: What happens when RSA keys don't use primes?
Tom St Denis wrote:
> Ok RSA requires at least two primes P and Q. You then calculate the private
> exponent via D = E^-1 mod lcm(P-1, Q-1). If lcm(P-1,Q-1) is not the order
> of the group (totient function function) then D will not be the inverse
> exponent.
Not necessarily. As it was mentioned earlier in this thread, RSA works if
both p and q (with gcd(p,q)=1) are Carmichael numbers, which are surely
composite (the reason is quite simple: by definition we have a^(p-1)=1 mod p
for all integers with gcd(a,p)=1; this is all you need in the correctness
proof of the RSA cryptosystem). But there are other pairs of integers p,q
(which are no Carmichael numbers) where RSA works (so you cannot use the
"working" of an RSA cryptosystem as a test for primality or as a test for
p and q being Carmichael numbers).
It is quite interesting to note that one can indeed estimate the number
of messages on which the RSA system "works" if both p and q are _squarefree_
composite integers. In this case, RSA either works for all messages or it
fails at least for about half of all messages. Unfortunately, this theorem
does _not_ extend to general integers p,q.
This was proved by H. Hule and W. B. Mueller in a paper entitled
"On the RSA-Cryptosystem with Wrong Keys", which appeared in "Contributions to
General Algebra 6", 1988, Hoelder-Pichler-Tempsky (a small Austrian
publishing house), Vienna, 1988, pp. 103-109. The paper is quite old now
(and perhaps difficult to get); unfortunately I don't know of any more
recent work on this problem...
--Stefan.
------------------------------
From: amateur <[EMAIL PROTECTED]>
Subject: Re: Fast and Easy crypt send
Date: Thu, 22 Mar 2001 12:42:02 -0400
Even if every letter is represented differently.
0110 = 2798 or 4936 or even odd odd even using odd and even categories.
0110 = apco or izxu or vowel consonant consonant vowel
That's what I don't understand.
Joseph Ashwood wrote:
>
> Your sequence is not random, almost all of the randomness disappeared
> immediately when you eliminated the outer key (which I assume we both agree
> happened). From there the only randomness left is the randomness in the
> original sequences, which had very little discernable randomness, so they
> can be pulled apart with a minor amount of difficulty. The first thing you
> need to realize is that the text you're encrypting is far from random, it
> has strong order, bias, etc. English is a good example, English text has
> between 1 and 2 bits of entropy per character (depending on several
> factors), this is quite a distance from the 8 bits that are used per
> character in ASCI, and further from the 16 and 32 bits that are used in
> various Unicodes. I still say that the place you need to start is in reading
> a book on cryptography.
> Joe
>
> "amateur" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > I'm still not convinced. I do not have to know cryptography to
> > undertstand that a RANDOM sequence is non information at all.
> > My encrypted text is RANDOM serie.
> > How could you exploit random sequence???
> >
> >
> >
> > Joseph Ashwood wrote:
> > >
> > > Honestly, I have explained it, I'm not going to explain it any more,
> read
> > > the sci.crypt FAQ, read a book on cryptography, if you still don't get
> it,
> > > then just realize that you don't get cryptography, and don't try. If you
> do
> > > get it then you will immediately realize that the only valid decryption
> of
> > > your example was in fact 10011001, and that attempting to fix this
> problem
> > > is useless. To reiterate please read a book on cryptography, please read
> the
> > > sci.crypt FAQ, both will explain in great detail just exactly why your
> > > algorithm is completely useless.
> > > Joe
> > >
> > > "amateur" <[EMAIL PROTECTED]> wrote in message
> > > news:[EMAIL PROTECTED]...
------------------------------
From: amateur <[EMAIL PROTECTED]>
Subject: Re: Idea
Date: Thu, 22 Mar 2001 12:48:14 -0400
Ok Thank you for your explanations. I understood something else.
I'm sorry and I apologize to all internauts.
So if I understand, should I have to be an expert crypto to
contribute?I'm just suggesting ideas.
I will never post anything.
Bye bye and thank you.
Joseph Ashwood wrote:
>
> To translate (since you are obviously either new to newsgrouos, the
> internet, or playing dumb), "those who . . . ." wants you to stop switching
> the e-mail address you are coming from. This will allow him to set his
> newsreader to simply ignore everything you say. It's a very useful feature
> when someone demonstrates that their only purpose in a newsgroup is to waste
> bandwidth. Since you are being uncooperative about it, he is prepared to
> block all of netcom.ca simply because he finds your posts that useless (at
> least useless enough to block all the other posters from netcom.ca). I'm
> sure you're addresses have made it into several killfiles.
> Joe
>
> "amateur" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > ????????????????
> >
> >
> >
> > those who know me have no need of my name wrote:
> > >
> > > <[EMAIL PROTECTED]> divulged:
> > >
> > > >I'm not using a secret algorithm.
> > >
> > > will you please keep a single from header. i really don't want to
> > > killfile all of netcom.ca. thank you.
> > >
> > > --
> > > okay, have a sig then
------------------------------
From: Yamaneko <[EMAIL PROTECTED]>
Subject: Re: Most secure way to add passphrase verification to "CipherSaber"
Date: Thu, 22 Mar 2001 17:20:24 -0100
Reply-To: [EMAIL PROTECTED]
"John L. Allen" wrote:
>
> Now _that's_ interesting! Using the rc4 output itself as the "Hash" of
> the passphrase. I think I like it. But is giving away some of the
> rc4 stream to the attacker a good idea? Maybe
>
> IV, E(throw-away bytes), E(msg)
>
> would be better?
In case of a known plaintext attack, you know msg and E(msg) and can
calculate the entire random stream that was used for encrypting msg.
I assume that rc4 is safe. (Correct me if I'm wrong!) That means even
if you know megabytes of random output, you shoudn't be able to calculate
the internal state. Then you also shoudn't have to worry about leaking 10
throw-away-bytes.
--
======================================================================
Someday I want to experience the following situation: People
discuss something very vividly but one person remains rather
silent. They'd ask him about his opinion and he'd answer: "Well, I
can't tell because I don't know enough about it." Then everybody
would say full of admiration: "Hey, that's a really wise man!"
======================================================================
------------------------------
From: Yamaneko <[EMAIL PROTECTED]>
Subject: Re: Most secure way to add passphrase verification to "CipherSaber"
Date: Thu, 22 Mar 2001 17:25:18 -0100
Reply-To: [EMAIL PROTECTED]
> Please note that I'm an amateur, so others please correct me if I claim
> something wrong. I'd say that double-encrypting the IV does not add
> significant security. How about
>
> IV, E(salt+IV), E(msg)
Is salt+IV an addition of numbers or a concatenation? Remember that
RC4 is a stream cipher so in case of a concatenation:
E(salt+IV) = E(salt)+E(IV)
--
======================================================================
Someday I want to experience the following situation: People
discuss something very vividly but one person remains rather
silent. They'd ask him about his opinion and he'd answer: "Well, I
can't tell because I don't know enough about it." Then everybody
would say full of admiration: "Hey, that's a really wise man!"
======================================================================
------------------------------
From: Yamaneko <[EMAIL PROTECTED]>
Subject: How to avoid known-plaintext attack (Re: Most secure way to add
Date: Thu, 22 Mar 2001 17:38:18 -0100
Reply-To: [EMAIL PROTECTED]
There were some suggestions about adding a checksum of some kind to
the ciphertext. That reminded me of the threat of a known plaintext attack:
Let the encrypt message be:
IV + opt:throw-away-bytes + E(K+IV, pt+opt:H(pt))
where + is the concatenation of strings, E(K,pt) the encyption function,
H(pt) some kind of checksum (CRC32) or hash (MDx), opt:xxx optional terms.
If an attacker happens to know pt, he could calculate the entire random
stream (hopefully not the key). Then he could chose a forged plaintext pt2
with len(pt2) <= len(pt) and replace E(K+IV, pt+opt:H(pt)) by
E(K+IV, pt2+opt:H(pt2)). The recipient would decrypt the ct without
noticing the fraud.
You could avoid this attack by prepending random bytes to pt and hashing
them too:
IV + throw-away-bytes + E(K+IV, random + pt + H(random + pt))
Would that be too complicated? Secure?
------------------------------
From: "John L. Allen" <[EMAIL PROTECTED]>
Subject: Re: Most secure way to add passphrase verification to "CipherSaber"
Date: Thu, 22 Mar 2001 18:23:10 GMT
"Joe H. Acker" wrote:
> John L. Allen <[EMAIL PROTECTED]> wrote:
>
> > "Joe H. Acker" wrote:
>
> > Remember, I want to avoid the slow H(msg), so this simpler version
> > of your first suggestion might be ok:
> >
> > IV, E(H(CRC32(msg))), E(MSG)
> >
> > But it still suffers from having to read the entire plaintext before being
> > able to start writing the encrypted result. So, why then not
> >
> > IV, E(msg), E(H(CRC32(msg)))
> >
> > ? That would mean you'd have to read the entire encrypted stream
> > before being able to verify the password. And I guess Paul Rubin
> > is right in saying doing a hash _and_ a CRC is too complicated for
> > CS.
> >
> > So, I go back to one of my first ideas:
> >
> > IV, E(E(IV)), E(msg)
> >
> > Does this obviously give too much away?
>
> Please note that I'm an amateur, so others please correct me if I claim
> something wrong. I'd say that double-encrypting the IV does not add
> significant security. How about
I guess I don't care if it adds security, as long as it doesn't subtract it :-)
I know that passing (x, E(x)) gives an attacker known plaintext, but what's
wrong with giving him (x, E(E(x))) ?
>
> IV, E(salt+IV), E(msg)
>
> where salt is a few pseudo-random bytes from a PRNG. You can use Arcfour
> as the PRNG, and the actual entropy of the random seed will be
> implementation depend. Even if the entropy source is not optimal, this
> seems more secure to me than just encrypting IV (known plaintext).
If the salt is generated by rc4, then that looks a lot like Mike De Turi's
"throw-away-bytes" idea, and is similarly interesting.
I then slap myself in the head and ask what about this
IV, E(msg{1..10}), E(msg)
where the two encryptions of msg{1..10} will not be the same because they
use different parts of the rc4 stream. This does not seem to weaken
things at all (or does it?) and provides an easy way to verify the passphrase:
if the two decryptions of msg{1..10} are the same, you win. You could
also xor the first msg{1..10} with some "throw-away" rc4 output (your "salt")
prior to encryption:
IV, E(salt ^ msg{1..10}), E(msg)
That looks pretty good. And very simple. But I am only an amateur too :-)
John.
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Most secure way to add passphrase verification to "CipherSaber"
Date: Thu, 22 Mar 2001 10:37:57 -0800
It's really very simple to add an integrity check to something like
ciphersaber.
Given Key, IV, msg
has = Hash(Key, IV, msg)
Encrypt(msg, has)
verification depends on knowing the key, IV and msg'
has = last several bytes of msg'
remove last several bytes from msg'
h2 = Hash(key, IV, msg)
is has == h2 decrypted correctly
There it is very simple.
Joe
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: ECC rather than PGP ?
Date: Thu, 22 Mar 2001 10:40:43 -0800
Well the biggest one's I know of are:
1) It's not nearly as popular, so everyone you want to talk to has to
download it
2) I think this is the first time I've ever heard of it, so it's not likely
to be reputable
3) You don't say what field's it's over that would distinctly help us to
know if it has severe problems.
Joe
"Anonymous" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> I have just downloaded Greg Ofiesh's ECC public key encryption
> program (Hidden Point Conceal 3.1).
> I think that it is a viable alternative to PGP at this point, and the
> executable is only 120kb in size (BIG GRIN).
> Any Caveats ??.
>
>
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Crypto Contest?
Date: Thu, 22 Mar 2001 18:49:50 GMT
What happend to the crypto contest? and is it still on the web?
--
Tom St Denis
---
http://tomstdenis.home.dhs.org
------------------------------
From: William Hugh Murray <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: can a remailer send a message to multiple people?
Date: Thu, 22 Mar 2001 18:50:48 GMT
An Metet wrote:
> > Can I use the mixmaster 2.0.3 to send a message anonymously to more
> > than one person? Thanks.
>
> Up to four individuals or newsgroups per invocation. Good Luck.
They will help you hide your identity but they will not help you spam.
------------------------------
From: Jeffrey Williams <[EMAIL PROTECTED]>
Subject: Re: Idea
Date: Thu, 22 Mar 2001 12:57:05 -0600
No. Don't stop posting. DO follow the suggestions of several folks and do some
study and/or research. Ask questions.
Do expect that when someone with little or no background in any area of study
starts making impressive claims, those who have taken the time to study that area
will be doubtful of those claims. The doubt does not invalidate the claims (nor
does it validate them); it's the normal human response to the situation.
Don't go away.
amateur wrote:
> Ok Thank you for your explanations. I understood something else.
> I'm sorry and I apologize to all internauts.
> So if I understand, should I have to be an expert crypto to
> contribute?I'm just suggesting ideas.
> I will never post anything.
> Bye bye and thank you.
>
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Speed of factoring
Date: 22 Mar 2001 19:02:15 GMT
In <[EMAIL PROTECTED]> Soeren Gammelmark <[EMAIL PROTECTED]> writes:
>Hi
>Yeasterday I read in Applied Cryptography, that the time-estimate of the
>fastest variants of the quadratic sieve was
>e^((1+0(1))ln(n)^(1/2)ln(ln(n))^(1/2))
>What I don't understand is the 0(1)? Is it really zero multiplied with
The is the capital letter Oh, not the number zero. It means Order 1--
some function which is bounded as n->infinity.
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
