Re: [stella] I can't find it

Subject: Re: [stella] I can't find it
From: "Andrew Davie" <adavie@xxxxxxxxxxxxx>
Date: Tue, 12 Sep 2000 14:30:47 +1000
Hi everyone
I wrote to George Woltman regarding this - George is the head honcho in
charge of GIMPS - the great internet mersenne prime search
(www.entropia.com/primenet).  Mersenne primes are of the form (2^p) - 1, and
they are dealing with million-decimal-digit primes these days.  I run
Prime95, a distributed prime checker, on my PC eating up idle cycles - and
have done so for a number of years, now.  I was hoping the system/program
could be used to crack our number.  George was kind enough to respond, but
unfortunately quenched my hope.
I copy his email verbatim...  we need a different approach :)
Cheers
A

Hi,

         You won't be able to factor it.  The best known factoring algorithm
at
present is the Number Field Sieve (NFS).  Using current computers it can
crack numbers up to roughly 200 digits.  That's using a distributed
approach to run the sieve and a supercomputer to run the final step.

         The suggestion of factoring it by brute force by dividing up the
key space would take eons.

         The poster that thought he would get a list of known large primes
doesn't understand how this number was constructed.  It is not done
using a list of known 130 digit primes.  My PC can find 2 130 digit
primes in less than a second.

Hope that helps,
George

At 01:56 PM 9/12/00 +1000, you wrote:
>However, a recent discussion on the [stella] mailing list (devoted to
>modern-day programmers of the video game systems from the mid 1970s - in
>particular, the Atari 2600) about the copy protection on an Atari machine
>which uses a rather large decimal number which needs to be factorised,
>prompts me to write.
>You can see the number and some discussion in the email copied, below.
>I'm wondering, is it possible to factorise this number using Prime95?  A
>long shot, I suppose, but I'm thinking that prime95 is dealing with numbers
>many magnitudes larger than this already.  By factorising this number, many
>homebrew programmers would be able to produce new games/programs for this
>long-dead console.
>Thanks for any help/advice you might be able to provide.
>Hope this finds you well.
>Cheers
>A
>--
>Andrew Davie adavie@xxxxxxxxxxxxx & adavie@xxxxxxxxxxxxxxxxx ICQ #3297382
>Museum of Soviet Calculators @ www.taswegian.com/MOSCOW/soviet.html
>FAQ @ www.taswegian.com/TwoHeaded/faq.html  Work @ www.bde3d.com
>
>
>----- Original Message -----
>From: "Russ Perry Jr" <slapdash@xxxxxxxxxxxx>
>To: <stella@xxxxxxxxxxx>
>Sent: Tuesday, September 12, 2000 12:13 PM
>Subject: RE: [stella] I can't find it
>
>
> > Do we know anything else about this number?  It's the product of two
> > large primes, right?  Or possibly more than that??
> >
> > I remember looking one other time for a list of large primes without
> > much success.  But I guess if such lists existed, this sort of problem
> > wouldn't be very insteresting, would it?  And determining primes isn't
> > exactly a quick science either from what I understand.
> >
> > Heh, it's not divisible by 2 or 3...  And the last digits would be 1 & 3
> > or 7 & 9 if only two multiplicands.  That should narrow it down enough
> > for you guys.  :-)
> >
> > More seriously, perhaps a distributed computing effort like the RSA/DES
> > challenges or SETI would work?  Break the keyspace up into all numbers
> > between 1 and that whole thing that end in 1 & 3 or 7 & 9, and let
people
> > try multiplying all those numbers until SOMEONE finds it.  Might be a
> > nice RGVC project, assuming the keyspace splitter and calculator server
> > & client aren't too hard to program...
> >
> > John Saeger wrote:
> > >Here's the number that we'd like to factor:
> > >
> >
>
>372763642186038806257268716646134295445276919770501371632454989813933011717
>1
> >
>
>918154782270776663547170932295686631340166371502363305352251508921925382211
>5
> >
>
>983319169296763298520553286632782878137984247708495679525591638977292185426
>5
> > >394451056360909015523895044054544800868529030160209747657273
> >
> > John K. Harvey wrote:
> > >> I've browsed the stella archives, and can't find the big base-10
> > >> respresentation of the 7800 encryption number that can't be broken.
>Can
> > >> anyone help me find it?
> > --
> > //*================================================================++
> > ||  Russ Perry Jr   2175 S Tonne Dr #105   Arlington Hts IL 60005  ||
> > ||  847-952-9729    slapdash@xxxxxxxxxxxx    VIDEOGAME COLLECTOR!  ||
> > ++================================================================*//
> >
> > --
> > Archives (includes files) at
http://www.biglist.com/lists/stella/archives/
> > Unsub & more at http://www.biglist.com/lists/stella/
> >


--
Andrew Davie adavie@xxxxxxxxxxxxx & adavie@xxxxxxxxxxxxxxxxx ICQ #3297382
Museum of Soviet Calculators @ www.taswegian.com/MOSCOW/soviet.html
FAQ @ www.taswegian.com/TwoHeaded/faq.html  Work @ www.bde3d.com


----- Original Message -----
From: "Rob" <kudla@xxxxxxxxx>
To: <stella@xxxxxxxxxxx>
Cc: <stella@xxxxxxxxxxx>
Sent: Tuesday, September 12, 2000 12:52 PM
Subject: RE: [stella] I can't find it


> At 09:13 PM 9/11/00 -0500, Russ Perry Jr wrote:
> >More seriously, perhaps a distributed computing effort like the RSA/DES
> >challenges or SETI would work?  Break the keyspace up into all numbers
>
> Well, it took a distributed team a couple weeks last year to crack a
> 128-bit key, so if we got the same size team together, it would only take
> 2^(960-128) weeks to crack this one.... right?
>
> Rob
>
> kudla@xxxxxxxxx ... http://kudla.org/raindog ... Rob
>
>
> --
> Archives (includes files) at http://www.biglist.com/lists/stella/archives/
> Unsub & more at http://www.biglist.com/lists/stella/
>


--
Archives (includes files) at http://www.biglist.com/lists/stella/archives/
Unsub & more at http://www.biglist.com/lists/stella/

Current Thread