Then if a calculation (say differential analysis) was determined to need
10^16 (hours say) to analyze a certain code, a quantum computer (if it
existed) could reduce that to approx. 10^8 and therefore improve the time by
a factor of some 10 million. If this is correct that is impressive. With
that computer, I could do my taxes in milleseconds! 8-)
*-----Original Message-----
*From: [EMAIL PROTECTED]
*[mailto:[EMAIL PROTECTED]]On Behalf Of Ben Nagy
*Sent: Sunday, December 03, 2000 7:56 PM
*To: 'Todd'; '[EMAIL PROTECTED]'
*Subject: RE: Ben's Big Crypto Flamefest
*
*
*> -----Original Message-----
*> From: Todd [mailto:[EMAIL PROTECTED]]
*> Sent: Friday, 1 December 2000 3:44
*> To: '[EMAIL PROTECTED]'
*> Subject: Re: Ben's Big Crypto Flamefest
*>
*>
*> folx,
*>
*> On Thu, 30 Nov 2000, Ben Nagy wrote:
*>
*> > No. You couldn't. Brute forcing a 4kb key is not possible
*> without a trapdoor
*> > or flaw in the algorithm. IOW - even taking factoring as an
*> example...
*> > Quantum computing may become real. This effectively square roots the
*> > complexity of an arbitrary calculation. That makes a 4096
*> bit number as hard
*> > to factor as a 2048 bit one. Big deal. 2048 bits is well
*> outside the realms
*> > of possibility with an amazing new algorithm for factoring.
*>
*> careful here. unless i'm misunderstanding your calculation, quantum
*> algorithms (when running on quantum computing devices that don't exist
*> yet) reduce complexity to the square root, but srt(4096) = 64, not
*> 2048. 64 bits is quite tolerable (not easy, but tolerable),
*> especially if
*> there are any entropy-reducing errors in the algorithm already.
*>
*> am i missing something?
*
*Yeah - you're misunderstanding. If you square root the complexity of an
*exponential calculation then you halve the exponent. It does not sqrt the
*keyspace.
*
*Check out some links or mail archives that talk about "Grover's Algorithm"
*if you're interested. Grover's alg is the funky search-space one
*that allows
*those sort of speedups for "general" searching (like keyspace brute
*forcing). Shor's is the factoring one.
*
*As an interesting aside - I'm trying really hard to find some hard
*information on the effect of Shor's factoring algorithm on large
*factorisation problems. We know that it brings the complexity back to
*poly-time but I'm yet to find a hard reference about what that means for
*work times in real situations (assuming that it's possible to build a QC
*that big in the first place).
*
*
*>
*> =========================================================
*> Todd Underwood, [EMAIL PROTECTED]
*>
*
*Cheers,
*
*--
*Ben Nagy
*Marconi Services
*Network Integration Specialist
*Mb: +61 414 411 520 PGP Key ID: 0x1A86E304
*-
*[To unsubscribe, send mail to [EMAIL PROTECTED] with
*"unsubscribe firewalls" in the body of the message.]
*
-
[To unsubscribe, send mail to [EMAIL PROTECTED] with
"unsubscribe firewalls" in the body of the message.]
