[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