Home Windows 7 Sydney PCUG PIC Club Web Design Primes Factors Factor Records Nice Split Digital Photos Links Downloads Archives Contact Us

Factors

>  Recent Factors, below 

• Msieve

See new Perl script, below:

Jason Papadopoulos wrote the factoring program Msieve which started life a few years ago using the Quadratic Sieve method.  It can now easily handle numbers up to 200 digits by a single machine.

The current version is Msieve v. 1.48 and is available either as a Linux C++ source code package in a tar.gz file (400 KB) or as a Windows executable (about 600 KB).

The more advanced Number Field Sieve method is now being added into the program.  Both methods involve sieving followed by the solution of a large linear matrix.  The code has become so good that for very large numbers, the NFS sieving part can be done by GGNFS (see below), but the linear algebra, too large for GGNFS, can be handled by Msieve.

In fact, it has been used to tackle a record 180-digit General number and also a Special number of 277-digits.

A General number of 190 digits has just been factored on Nov 8, 2010. -- See below the 180 digit report.


The 180-digit number was the residual composite left from 5421-1 which factorises as:

p1=22
p8=14894981 •
p17=3141046615­9536169 •
p23=7368841216­3867840421­869 •
p31=2510106373­3405280839­6049223493­9 •
p37=6226633359­2762264691­0709069143­4236881 • C180

The worldwide cooperative effort was run from about July 2008 to November 2008 and involved many dozens of researchers with hundreds of computers. Go to the Mersenne Forum for the full story. The final result from all this effort was a p66 • p115 factorisation.

p66=6222327587­8035877812­6190590256­7499545249­9950589085­9340251987­532999 •
p115=1376892416­9868916608­6888895270­9866680522­2124048774­1405278143­2896337974­1975243459­7633402206­7211965993­2497612307­43801

The 190-digit number factored using Msieve was the RSA-190 Challenge Number.

"The job was done by I.Popovyan from MSU, Russia and A. Timofeev from CWI, Netherlands and took a few months of a pure computer time on various parallel systems in both MSU and CWI".

For the full report, see the Mersenne Forum.

"We are happy to report that after almost a half a year on November 8th, 2010 we finally got the factorization of the RSA-190 as follows:"

C190=1907556405­0606964910­6145043264­6028861081­1797595331­8446064797­5622318915­0255871841­7575405497­6155121593­2934922604­6415263009­3238509246­6032074171­2472612158­0858185985­9389469454­9048172175­6401423481
 
p95= 3171195257­6901527094­8517128974­0475929805­1473160294­5032778476­1927832793­6427981256­5424157243­09619 •
p95=6015260020­4445616415­8764168552­6676183243­5433594718­1107259976­3828083615­7040460481­6253556194­04899

The Special number of 277-digits was 12256+1 which is a Generalised Fermat Number - Fermat Numbers are of the form 22n+1. There were three known factors (with 7, 12 and 31 digits), so there remained a C228 to be factored. The SNFS difficulty was, however, still 277.

p7=8253953 •
p12=2952786426­89 •
p31=5763919006­3231428310­6505961369­7 • C228

This enormous factorisation was carried out by the researchers Thomas Womack and Bruce Dodson (collectively fivemack on the Mersenne Forum). It was conducted over several months in 2009, ending on 17 August with a p96 • p132 factorisation.

p96=4522716540­4509537635­4829024468­6206551071­6804453718­9917947981­8782845448­9108248533­1470888529­210881 •
p132=2933511005­3407333932­0273736685­5540405469­8977355897­8742766077­6301320178­6599660198­3557083266­5439209636­2493681035­4879103450­0207780817­93

• Msieve / GGNFS Comparison

I recently came across a 183 digit composite number that caused a memory allocation error when GGNFS came to load the matrix into memory, saying that it wanted 721 MB.  The machine actually had 2 GB, so previous memory requests had probably fragmented the memory, causing the crash.

Msieve, however, loaded the GGNFS-format data and solved the 779,725 × 779,973 matrix, not only using less memory (250 MB vs. 721 MB), but in a shorter time (05:11:32 hrs compared to possibly 24 hrs for such a large number).  The prime factors turned out to be p48 • p48 • p87 showing that very large composites don't always have very large prime factors.

Here are the comparative matrix-solution times for a 166 digit number (with SNFS difficulty 167 digits) that succeeded using both GGNFS and Msieve:

• For GGNFS:

Initial matrix: 433802 x 491774 with sparse part having weight 54393195.
Pruned matrix : 412924 x 415157 with weight 43131647.
...
Matrix solve time: 5.82 hours.
Total square root time: 0.15 hours, sqrts: 1.

• For Msieve:

matrix is 543812 x 544059 with weight 35189856 (avg 64.68/col)
...
commencing square root phase
reading relations for dependency 1
...
elapsed time 02:03:21

• Msieve Perl Script

The parameter files for Msieve are slightly different from the GGNFS format and need conversion (only a matter of a few seconds) before running Msieve.  The makems Perl script to automate this process was posted to the XYYXF Yahoo! Group as message number 1185 in October, 2007.  See below for the script:


• SNFS

Most of the factors listed below were found using the Special Number Field Sieve method.  In the past, this has been only available to mathematical researchers at Universities with super-computers like the CWI (Centrum voor Wiskunde en Informatica, or the Center for Mathematics and Computer Science) in the Netherlands.

See a very interesting CWI report produced by Dr. Herman te Riele which covers several recent record factorisations on the topic: Factoring large integers with the Number Field Sieve.

• GGNFS

In 2005, an open-source C program called GGNFS was written by Chris Monico of the Texas Tech University to run on fast PCs with 1 or 2 GB of memory. The software is provided as a set of source modules along with a Makefile script to install and run on Linux. The program itself is then run via a Perl script which executes the various phases of the calculation (sieving, processing, matrix inversion and finally the sqrt phase).

It is by no means a set-and-forget method since it is still in development and being improved by contributions from many people around the world. There are still bugs present and when it crashes, it takes some ingenuity to resume the calculations without too much loss of data - a typical run generating several gigabytes.

For answers to typical questions, go to the GGNFS Yahoo! Group.

• Cygwin

The software can also be run on Windows based PCs under a program called Cygwin.  This gives a command line interface to a simulated Linux shell which allows the factoring program to run.  Quoting from the Cygwin web-site:

Cygwin is a Linux-like environment for Windows.  It consists of two parts:
  • A DLL (cygwin1.dll) which acts as a Linux API emulation layer providing substantial Linux API functionality.
  • A collection of tools which provide Linux look and feel.

• Recent Factors NEW

>  Top of page  ::  Bottom of page 

Feb 12, 2012
 
55 • 10187 + 17  [611863]c177p54: 5733956797­0740069938­5348747479­8343937527­9396740949­0749 •
   p124: 1245645552­6444757149­1425763503­9358945570­9502786509­0741093799­0090328439­0472255461­3780802021­3496628143­0010276270­7139074608­5277
 
37 • 10187 + 17  [411863]c177p89: 1629276562­1288919609­4788170546­2842456295­3771570853­1716297036­1137936552­9746626204­307635029 •
   p89: 6080928134­8649681244­7190417066­1120594828­4047834909­9598453291­7992017294­4231048578­394381343
Feb 11, 2012
 
53 • 10186 - 17  [581857]c176p53: 1008451315­6525457970­7274631968­7289952795­3549967140­989 •
   p124: 6036217412­7233310399­1751514983­5578292552­8366099904­5555579007­3034039585­6680740255­9178021902­3725303827­1394685563­8415316166­8349
Feb 10, 2012
 
25 • 10186 - 61  [271851]c176p46: 5414636935­2814069133­4945885710­5484780449­526483 •
   p53: 1500911619­0485478016­5771388114­9360863109­1125451562­089 •
   p78: 3421959667­6389262887­9123527833­4538860160­6416410572­7964142669­3620579243­57193181
 
5 • 10185 - 3  [491847]c175p50: 1139858391­8308311218­7069776303­4622841489­3336146411 •
   p126: 6062809651­1316272731­7335313147­8078042491­4642174329­4918972031­0725096293­6013389271­3710215314­0346468464­3530751483­5203848156­835539
Feb 9, 2012
 
16 • 10185 - 61  [171841]c175p58: 3915166379­9011741171­4685051252­2031279127­4288873244­86329099 •
   p117: 8312803770­5677669912­5672696659­0901081773­6235386672­4263173674­0932989863­2084839985­4987890490­4876468118­0165074577­1445097
 
6 • 10181 - 7  [591803]c171p38: 8989933398­4936105365­3878191869­86113099 •
   p55: 1289747829­9590695218­6985591695­8833257526­3650347991­35453 •
   p79: 2936165076­2891673275­8488988892­6912970057­2185596552­6362909601­1171234579­616000291
 
8 • 10181 - 11  [261803]c171p53: 1805714475­4324462860­9809527003­3140322913­6335844665­561 •
   p119: 1494769664­1251754547­8423434150­3540339037­4999327855­9819016634­2709306512­2255797738­0793347581­8741285931­0023657585­899298051
Feb 8, 2012
 
2 • 10181 - 7  [191803]c171p76: 2422412979­8000280608­7585527338­5371436650­3074974819­2399654530­5433879222­350917 •
   p96: 2926420580­6109979269­8815532391­4475785701­5329330044­9978434095­4506192999­3461541788­7567871388­531427
 
3 • 10180 + 7  [301797]c170p52: 3357886592­2249648134­2489396092­5970858540­2490848168­07 •
   p118: 6421772340­7627072595­2188451351­0240331991­3957546937­0522952169­4663499363­3970529347­9648006118­9870059727­0499364656­43276799
 
7 • 10179 - 9  [691781]c169p70: 1257951721­2636043521­3958982910­6892400427­5514256452­9471018264­2789568763 •
   p100: 7646682242­1905911615­5619837363­7317987171­3353147572­3530275508­3444223092­4189173356­9583889752­2440941369
 
14 • 10178 - 17  [461771]c168p77: 2854682101­9147319808­6505852821­9729441019­8331762531­7979160329­0837909904­1809097 •
   p92: 2483279880­1999526689­3310641814­5264736533­6077731458­0379389998­5681760890­9966198557­8053604403­87
Feb 7, 2012
 
65 • 10177 + 43  [721767]c167p80: 1692447876­8088386980­4984605548­8313420950­9010986941­8018471515­3181861847­1942261317 •
   p88: 1467786839­4364294281­8056399749­8291748574­9486066521­2090592425­1950685514­0952109800­66161771
 
55 • 10177 + 71  [611769]c167p55: 2851128820­7438884758­3623701027­6601462602­3379354807­87861 •
   p113: 1089547451­9832749198­2339666192­7767600824­7730710565­8577861466­0313980162­0537451903­7882095032­3256191735­9117479223­413
 
7 • 10188 - 3  [691877]c179p52: 8980629593­7798378817­7587230982­4081556163­0299181489­21 •
   p128: 1023039446­0543631963­8629267852­8874832817­3848556134­8209323837­8999008593­0266983455­3798843489­0916144541­3917516502­1026540625­16131561
Feb 6, 2012
 
58 • 10188 + 23  [641877]c179p67: 4225510255­1586799222­6716886843­6266349800­9070329765­2646982018­1398279 •
   p112: 3641607396­6133409165­9576819712­9946213530­1481521105­3137629558­0741540284­8456343446­1086979739­3934839694­6392410546­97
 
46 • 10188 + 17  [511873]c179p49: 3483918410­4176533280­2602529180­9676294239­358737081 •
   p130: 6031940532­8449452050­3170823697­2941727762­7532254968­9864596958­3576605344­6151264834­1308592024­6168251254­5392044182­1605854293­0622437761
Feb 5, 2012
 
2 • 10187 - 3  [191867]c178p62: 3018849524­3559431954­1290768087­2417242279­4849359392­4799014196­69 •
   p116: 6252335220­5841974641­7672476861­5236903778­6705686420­7945850689­7143054360­9011985992­2476912664­8018786378­5691927767­719697
Feb 4, 2012
 
76 • 10186 - 31  [841851]c177p51: 5499121422­4817642654­0374928191­7135566281­5373642868­7 •
   p63: 1399471605­2692351863­7115866924­9959790809­2195807702­2614090765­997 •
   p64: 1330233117­5514046080­2776953826­9470145154­4740388589­3077164183­1359
 
23 • 10186 + 1  [761857]c177p74: 8285253328­7089694323­6797643052­4511851495­5218464542­2906500876­8606715753­3887 •
   p103: 2427646868­2746698479­9054866234­8786299820­1145760303­9082555294­6317745212­0494567298­7159174070­2807339148­439
 
4 • 10185 - 3  [391847]c176p44: 2454435920­7043689314­8838529874­0126386852­4717 •
   p64: 1711254231­1065903901­9146919323­4817699792­4754039127­8132897178­3723 •
   p69: 2703135946­1418100102­5713349777­9049359888­5410779201­4326687398­953865981
Feb 3, 2012
 
76 • 10184 - 31  [841831]c175p59: 2946025750­3252184970­7091663516­3503193076­4364878114­240357159 •
   p116: 7466341934­8000381298­8467320708­6628306811­7367730428­9523607160­3365634034­4447268473­3045681550­0328132571­2591590998­685467
 
77 • 10183 - 23  [851823]c174p58: 6744382706­1934326418­3288579338­6737167677­7615171846­97668901 •
   p116: 9064777702­7425773029­5095508504­3560257965­3517479739­3067401318­2390126070­3866178973­8407685264­8923805780­7840308662­203143
Feb 2, 2012
 
6 • 10181 + 7  [601807]c172p60: 4100174325­2438016526­3628364615­7642308517­4381472567­9469252361 •
   p112: 3182332185­5078962855­0982041849­6848430448­6755991007­1602260572­0663029243­6977162603­2249142309­9353138680­8846125310­17
 
11 • 10181 + 1  [361807]c172p77: 1090541078­0162656819­6135124556­1583708246­8916188215­5528946444­3714528254­4436421 •
   p96: 3670192678­1235147080­9773879128­6456743246­8935807540­4776986456­7684969069­3919154153­9509582451­096203
 
7 • 10181 - 54 • 1090 - 7  [7901790]c171p68: 5504496455­8230548226­7158053548­9594152924­3390609498­8543640801­11602501 •
   p104: 1194911816­2523157933­6426189557­4233482965­8207744413­6033355448­8538713231­0467425482­5922034954­1528675166­9489
Feb 1, 2012
 
58 • 10178 + 23  [641777]c169p64: 1879648905­2102427795­0674221068­0008175641­3910028947­8790536991­0181 •
   p106: 3734894355­9853991929­4792607067­8889627596­1321949439­9701370216­2544043609­0240823928­0612181047­0762077249­450191
 
47 • 10178 + 61  [521779]c169p78: 1154081211­6409473501­2236175664­7967453894­4490275646­2350565310­3831817208­75166223 •
   p92: 1103410358­2781337864­9277576062­8263003621­1683990647­9689805837­4020138106­2663832992­5457982330­93
 
44 • 10195 - 71  [481941]c187p63: 1868454701­0700673743­3272393672­1467138333­8286895277­6188334682­761 •
   p125: 1670200070­6236220312­0367762853­0248307653­8341383058­5051440143­6079635036­8924725188­7824426918­7713392333­3309755758­7891715028­34417

>  Top of page 
(New Tab) Built With NOF (New Tab) Validate XHTML 1.0 Transitional ©2012 Bob Bäckström

Home Windows 7 Sydney PCUG PIC Club Web Design Primes Factors Factor Records Nice Split Digital Photos Links Downloads Archives Contact Us