[RC5] possible third project...
Ryan Malayter
rmalayter at bai.org
Tue Jul 31 11:24:15 EDT 2001
Hey, you're right. I was fat-fingering the parenthesis keys on my
calculator, so my exponents weren't fractional.
Sometimes I wish I still had a copy of Maple...
-----Original Message-----
From: Dave Huang [mailto:khym at azeotrope.org]
Sent: Monday, July 30, 2001 6:04 PM
To: 'rc5 at lists.distributed.net'
Subject: RE: [RC5] possible third project...
On Mon, 30 Jul 2001, Ryan Malayter wrote:
> Hmm... I guess I don't remember those algorithms classes to well.
>
> The running time of the GNFS is:
> O( exp(c*ln(n)^1/3 * ln(ln(n))^2/3 ) )
>
> I assumed N represented the size of the input the number field - all
> integers to be tested as factors, which would be 2^64 times as large
> the field for RSA-512. Is N calculated differently?
I don't know either, but even if n is the number of integers to be tested,
about 11 times harder sounds right to me.
For n=2^512, ln(n) = 512*ln(2) ~= 354.891, so the complexity works out to
about e^44.296. For n=2^576, ln(n) = 576*ln(2) ~= 399.253, so the complexity
works out to about e^46.684.
e^46.684/e^44.296 = e^2.388 = 10.892.
--
Name: Dave Huang | Mammal, mammal / their names are called /
INet: khym at azeotrope.org | they raise a paw / the bat, the cat /
FurryMUCK: Dahan | dolphin and dog / koala bear and hog -- TMBG
Dahan: Hani G Y+C 25 Y++ L+++ W- C++ T++ A+ E+ S++ V++ F- Q+++ P+ B+ PA+
PL++
--
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest
--
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest
More information about the rc5
mailing list