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.

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
Graphmastur

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.
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 :/.
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?
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?
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 ) 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 Last edited by Guest on 25 Apr 2010 02:37:56 am; edited 1 time in total
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?
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:        qlimit:    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
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) 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
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
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.
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).
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
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?
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 Last edited by Guest on 28 Apr 2010 01:47:14 am; edited 1 time in total
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.
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 ? 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.
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 ? 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...)
 Display posts from previous: All Posts Oldest FirstNewest First
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.

»
 Page 1 of 1 » All times are GMT - 5 Hours