Login [Register]
Don't have an account? Register now to chat, post, use our tools, and much more.
This is an archived, read-only copy of the United-TI subforum , including posts and topic from May 2003 to April 2012. If you would like to discuss any of the topics in this forum, you can visit Cemetech's Technology & Calculator Open Topic subforum. Some of these topics may also be directly-linked to active Cemetech topics. If you are a Cemetech member with a linked United-TI account, you can link United-TI topics here with your current Cemetech topics.

This forum is locked: you cannot post, reply to, or edit topics. Math and Science => Technology & Calculator Open Topic
Author Message
wesley


Newbie


Joined: 05 May 2009
Posts: 45

Posted: 22 Apr 2010 05:12:48 pm    Post subject:

Hey everyone,

I've been looking through the project on discovering the private keys for the calculators, but I'm a little confused as to how to get something going on my computer.

I have a pretty cruddy CPU (1 GHz and 1GB ram), but I also have access to some computers on campus (of course I can't install anything on them though).

I am just wondering what the best thing would be for me to do in factoring some large numbers. Could I get on the BOINC project somehow and put up some CPUs to do some factoring on some of my numbers?

Here are some examples:

R[1] := 856635008816114236287228889862706211601023274703568825790281732493598811489183201347792967433515761143227907320020567329633259067977601308187753;
R[2] := 262503444433443202297590751101961074929610529338524795169358249999355359738922201372169082275693161097217696397422937901342947981249;

EDIT: my platform is Windows XP/Fedora 10.


Last edited by Guest on 22 Apr 2010 05:15:23 pm; edited 1 time in total
Back to top
Graphmastur


Advanced Member


Joined: 25 Mar 2009
Posts: 360

Posted: 22 Apr 2010 10:11:37 pm    Post subject:

Try GNFS. I think that's what boinc uses. If you can program java, I would suggest a simple client/server system.
Back to top
wesley


Newbie


Joined: 05 May 2009
Posts: 45

Posted: 22 Apr 2010 11:24:35 pm    Post subject:

Hm... I can program Java, but I'm not sure how to set up a client/server system with Java. If I had the time, I would look into that route.

As of now, I am looking for something already implemented. I am in a cryptology class right now and when we take an exam, we have a 7 day period where we have a chance to crack classmates' keys. The exam starts in a little over a week, so I was wondering if I could get my hands on something pretty soon.

The keys will be smaller than 528 bits, and probably considerably smaller, so it won't be too terribly difficult if I could use something with other systems attached. My computer won't be sufficient unless my classmates make weak keys, in which case I could exploit attacks such as the following: Fermat, Pollard's Rho, P-1, ISA, and a couple of others we have learned. But since we are learning how to also defend against such attacks, and our class has 11 students, I doubt there will be very many mistakes. I just think it would be pretty fun to crack all the keys, but I guess I would need help for that :/.
Back to top
wesley


Newbie


Joined: 05 May 2009
Posts: 45

Posted: 23 Apr 2010 04:26:27 pm    Post subject:

Okay, I think I will go with the GGNFS route. I'm just struggling on what to put in the text file, as shown in k0A.txt at http://www.unitedti.org/forum/index.php?showtopic=8899.

What values do I need to edit inside of that file?
Back to top
wesley


Newbie


Joined: 05 May 2009
Posts: 45

Posted: 24 Apr 2010 01:12:01 pm    Post subject:

Okay, I see how the .poly files are created and they are similar to the k0A.txt one, but how do I modify it to set limits on the q size?
Back to top
Lionel Debroux


Member


Joined: 01 Aug 2009
Posts: 170

Posted: 25 Apr 2010 01:41:19 am    Post subject:

All lines (but "type: gnfs", of course Very Happy) need to be modified for optimal operation on your numbers.
I suggest you to use the factMsieve.pl or factmsieve.py scripts, under Fedora 10 (since on your Windows XP boxes, you won't be able to install Perl or Python), to see what invocations of ggnfs they run, and run that on your most powerful computers. See http://gilchrist.ca/jeff/factoring/nfs_beginners_guide.html for setting them up.


FYI, three things:
* msieve has a much more state-of-the-art polynomial selector than the pol5sel in ggnfs is. If you've got a CUDA-capable nVidia GPU (GeForce 8000 series and newer), by all means, use msieve-gpu, it's much faster for polynomial selection than msieve(-cpu);
* it will be hard to crack the C132 and C144 you posted in 7 days, unless you've got two or three appropriate computers doing the sieving: 1) factoring a C124 by GNFS takes between two and three days on a Core 2 Duo @ 2 GHz, both cores being used for the sieving and 2) in that range, GNFS factorization gets twice as hard every 5 or 6 digits.
* before running GNFS on a number, it's good to run it for 10 minutes or so in http://www.alpertron.com.ar/ECM.HTM . Besides ECM (which may weed out fishy keys quickly, as you've learnt), this applet uses a deterministic primality test (APRT-CLE).


Hope this helps Smile


Last edited by Guest on 25 Apr 2010 02:37:56 am; edited 1 time in total
Back to top
wesley


Newbie


Joined: 05 May 2009
Posts: 45

Posted: 25 Apr 2010 01:53:58 am    Post subject:

Lionel, thanks for the reply!

I've been looking through this, before you posted -- it's a great tutorial!

factmsieve.py was easy to get running on my Windows XP machine, but when I did, the thing went from start to go to the finish (finding the factors). The .poly file produced for the example shown in the tutorial you posted, is what I got below:


Code:
n: 2881039827457895971881627053137530734638790825166127496066674320241571446494762386620442953820735453
Y0: -731092230983186605374263
Y1: 122165114845223
c0: 2971226424358897923597990460
c1: -10644036891511329876471
c2: -16935647614701540
c3: 27796726924
c4: 10080
skew: 979472.53
type: gnfs


How would I modify this for limits? Do I need to stop the program once it creates the .poly file, then manually edit it? Or are there parameters for factmsieve.py that can take limits?
Back to top
wesley


Newbie


Joined: 05 May 2009
Posts: 45

Posted: 25 Apr 2010 01:56:19 am    Post subject:

Here's what my file doesn't have that the k0A file does have:


Code:
name: k0A
.
.
.
m: 4371032488381363880882149811025526045898926096451986525095113850210489193821605244360542467703827093867910920827107930978809502849809670495716078129760911

rlim:     27000000
alim:     27000000
lpbr:     29
lpba:     29
mfbr:     58
mfba:     58
rlambda:  2.7
alambda:  2.7

q0:       <STARTING VALUE HERE>
qlimit:   <ENDING VALUE HERE>
qintsize: 100000


Could anyone explain where these numbers come from? Do they come from factmsieve.py or are they manually entered?

EDIT: Oh, once I get this running on my home machine properly, I can get my hands on a few others, much more powerful than mine. I just need to get the initial setup steps down.


Last edited by Guest on 25 Apr 2010 01:59:50 am; edited 1 time in total
Back to top
Lionel Debroux


Member


Joined: 01 Aug 2009
Posts: 170

Posted: 25 Apr 2010 02:38:35 am    Post subject:

I have edited my previous post.

Polys that work, found in a couple hours with the pol5sel in ggnfs (while IIRC, factmsieve.py nowadays uses msieve's polsel):
(not very good)

Code:
name: R1
n: 262503444433443202297590751101961074929610529338524795169358249999355359738922201372169082275693161097217696397422937901342947981249
skew: 514824.81
# norm 2.75e+18
c5: 1920
c4: 71685955030
c3: -4768040907888497
c2: -14801470092795361539064
c1: -20926103112116815833666860
c0: 403693717649955385677727652688200
# alpha -6.07
Y1: 203391534082231
Y0: -42379047622915854816007701
# Murphy_E 5.07e-11
# M 152318487108331273687117324989684340019381948301885979275179441755728985609151234380141585194483272121184005210320209324307044180292
type: gnfs
rlim: 8000000
alim: 8000000
lpbr: 28
lpba: 28
mfbr: 55
mfba: 55
rlambda: 2.5
alambda: 2.5


(significantly better)

Code:
name: R1
n: 262503444433443202297590751101961074929610529338524795169358249999355359738922201372169082275693161097217696397422937901342947981249
skew: 200366.76
# norm 1.09e+18
c5: 57420
c4: -4574681012
c3: -21542079393779587
c2: -212259233180143701185
c1: 180702542932457844704521797
c0: 6028592968658263113225065152062
# alpha -5.46
Y1: 205994828828447
Y0: -21479018398375993973163971
# Murphy_E 6.09e-11
# M 258884740637388343174710061292900787290740560811459151138641417728839121909704317718760960651559488069430155962190359613912118652421
type: gnfs
rlim: 8000000
alim: 8000000
lpbr: 28
lpba: 28
mfbr: 55
mfba: 55
rlambda: 2.5
alambda: 2.5


To this, if you're not using factMsieve.pl or factmsieve.py on your target sieving machines (I do, I have never launched ggnfs-lasieve4I* directly), you'll probably want to add some "q0: " and "qintsize: " lines.


I'm not the good person to explain what the "m: " and other parameters really mean, since I haven't read any papers or even introduction to the principles of NFS factoring (or, in fact, basically any other algorithm besides trial division) Neutral
In order to use the algorithms (even for not-quite-amateur factorizations of the GNFS 165 and SNFS difficulty 250 class, which are the most demanding tasks we ever fed the RSALS grid with), I think that it's not necessary to understand how these algorithms work. We can just trust the helper scripts, the "ECM-ize up to ~2/7 for GNFS and ~2/9 for SNFS" rule of thumb, and several other basic tricks.


Last edited by Guest on 25 Apr 2010 04:11:07 am; edited 1 time in total
Back to top
wesley


Newbie


Joined: 05 May 2009
Posts: 45

Posted: 25 Apr 2010 08:45:48 am    Post subject:

Right, so how do I account for the differences in my .poly file as in the k0A file? How do I get the m, rlim, etc. for example? Could it be the way I setup the program to run, as shown in the tutorial?

Last edited by Guest on 26 Apr 2010 11:27:59 am; edited 1 time in total
Back to top
wesley


Newbie


Joined: 05 May 2009
Posts: 45

Posted: 26 Apr 2010 11:29:37 am    Post subject:

Oh, and what's the difference between factMsieve.pl and factmsieve.py? Does one run the other? The first is Perl while the second is Python, but I've only used the Python one.
Back to top
Lionel Debroux


Member


Joined: 01 Aug 2009
Posts: 170

Posted: 26 Apr 2010 12:53:16 pm    Post subject:

Quote:
How do I get the m, rlim, etc. for example?

Well, factMsieve.pl computes them for me using some algorithm that apriori gives good enough results. I haven't looked a it.
factmsieve.py can probably compute them, too, but I don't use it myself. factmsieve.py is a WIP rewrite in Python of the older factMsieve.pl contained in ggnfs, factmsieve.py still seems to be somewhat buggy at times (according to the thread on Mersenneforum).
Back to top
wesley


Newbie


Joined: 05 May 2009
Posts: 45

Posted: 26 Apr 2010 10:59:25 pm    Post subject:

Hmph... I can't seem to get GGNFS compiled on Fedora. Any suggestions? My machine has an Intel processor.

The tutorial we mentioned earlier doesn't note anything about libgmp, but Floppus mentions it here. First of all, do I need it? If so, how do I install it? I don't think yum has anything, and I can't find it in a search.

EDIT: What are the exact numbers for the ranges Floppus specified?

Code:
1M-2M limx (done, 847375 relations)
2M-6M BOINC clients
6M-8M Skittle (done, 2582020 relations)
8M-10M Skittle (done, 2606379 relations)
10M-13M fullmetalcoder (done, 4054840 relations)
13M-15M FloppusMaximus (done, 2745936 relations)
15M-17M Taricorp (done, 2764376 relations)
17M-20M fullmetalcoder (done, 4161960 relations)
20M-22M FloppusMaximus (done, 2765854 relations)
22M-25M Skittle (done, 4128280 relations)
25M-34M BOINC clients (done)
34M-35M FloppusMaximus (done, 1255021 relations)
35M-36M FloppusMaximus (done, 1254880 relations)
36M-44M BOINC clients
44M-45M FloppusMaximus (done, 1156504 relations)
45M-46M limx (done, 1153281 relations)
46M-50M BOINC clients


Is 1M-2M, 1 million (1000000) to 2 million (2000000)?

EDIT: You know what, I thought for some reason that the q0, qlimit, and qintsize, were a range of factors. These aren't by any means factors. Is there a way to set bounds on the program, so that if I wanted to split the work up between multiple machines, I could simply set a new bound on each to work on?


Last edited by Guest on 26 Apr 2010 11:48:05 pm; edited 1 time in total
Back to top
wesley


Newbie


Joined: 05 May 2009
Posts: 45

Posted: 27 Apr 2010 08:33:21 pm    Post subject:

Sorry for asking so many questions, but do I absolutely need a Debian version of Linux to use factMsieve.pl?
Back to top
Lionel Debroux


Member


Joined: 01 Aug 2009
Posts: 170

Posted: 28 Apr 2010 01:34:36 am    Post subject:

Quote:
Sorry for asking so many questions, but do I absolutely need a Debian version of Linux to use factMsieve.pl?

Nope, you don't need a Debian derivative. factMsieve.pl/factMsieveQ.pl (Benjamin's slightly modified version) work with other distro flavors :)

IIRC, you need gmp if you want to compile ggnfs yourself indeed. Either use the packages provided by your distro's repositories (all mainstream distros have some form of the "GNU MultiPrecision" library), or compile it yourself:

Code:

wget ftp://ftp.gnu.org/gnu/gmp/gmp-4.3.2.tar.bz2
tar xjf gmp-4.3.2.tar.bz2
cd gmp-4.3.2
./configure --prefix=$PREFIX --enable-cxx
make
make check
make install

(try 5.0.1, at your own risk, since ggnfs might not be compatible with it - I haven't tried)

Quote:
Is 1M-2M, 1 million (1000000) to 2 million (2000000)?

Yes.

Quote:
EDIT: You know what, I thought for some reason that the q0, qlimit, and qintsize, were a range of factors. These aren't by any means factors.

Indeed, they aren't factors. I don't know exactly what they represent, however. For my practical purposes, they're an input value for ggnfs-lasieve4I*.

Quote:
Is there a way to set bounds on the program, so that if I wanted to split the work up between multiple machines, I could simply set a new bound on each to work on?

Yes, q0 and qlimit with Benjamin's script are the way we used to split sieving of k0A across different hosts, and q0 and qintsize are the (equivalent, but doesn't require Benjamin's modified script) way we're using to split sieving of the RSALS integers across many computers.


Hope that helps Smile


Last edited by Guest on 28 Apr 2010 01:47:14 am; edited 1 time in total
Back to top
wesley


Newbie


Joined: 05 May 2009
Posts: 45

Posted: 28 Apr 2010 08:18:09 am    Post subject:

Well, for some reason, after installing all of the required libraries (e.g., Perl, Python, GMP), ggnfs and msieve still don't want to compile. I simply get tons of errors. How do I tell what Intel processor I have (difference between Pentium 2, Pentium 3, etc.). But even then, I've tried it with every option for the processor.
Back to top
Lionel Debroux


Member


Joined: 01 Aug 2009
Posts: 170

Posted: 29 Apr 2010 12:47:09 am    Post subject:

Are you the "Romulas" who posted http://www.mersenneforum.org/showthread.php?t=13367 ? Smile
Whether you are or you aren't, it's a good idea to post there, since you'll certainly get more help there with multiple persons than here with one person.
Back to top
wesley


Newbie


Joined: 05 May 2009
Posts: 45

Posted: 29 Apr 2010 12:55:27 am    Post subject:

Lionel Debroux wrote:

Are you the "Romulas" who posted http://www.mersenneforum.org/showthread.php?t=13367 ? Smile
Whether you are or you aren't, it's a good idea to post there, since you'll certainly get more help there with multiple persons than here with one person.

I sure am! That's why I started to post over there. Thank you for your great help thus far, Lionel. You are awesome!

(I just can't seem to get factMsieve.pl working on Linux...)
Back to top
Display posts from previous:   
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
    »
» View previous topic :: View next topic  
Page 1 of 1 » All times are GMT - 5 Hours

 

Advertisement