Bob Backstrom - Factors

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 5⁴²¹-1 which factorises as:

p1 = 2² •

p8 = 14894981 •

p17 = 31410466159536169 •

p23 = 73688412163867840421869 •

p31 = 2510106373340528083960492234939 •

p37 = 6226633359276226469107090691434236881 • 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 = 622232758780358778126190590256749954524999505890859340251987532999 •

p115 = 1376892416986891660868888952709866680522212404877414052781432896337974197524345976334022067211965993249761230743801

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 = 1907556405060696491061450432646028861081179759533184460647975622318915025587184175754054976155121593293492260464152630093238509246603207417124726121580858185985938946945490481721756401423481

p95 = 31711952576901527094851712897404759298051473160294503277847619278327936427981256542415724309619 •

p95 = 60152600204445616415876416855266761832435433594718110725997638280836157040460481625355619404899

The Special number of 277-digits was 12²⁵⁶+1 which is a Generalised Fermat Number - Fermat Numbers are of the form 2^2ⁿ+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 = 295278642689 •

p31 = 5763919006323142831065059613697 • 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 = 452271654045095376354829024468620655107168044537189917947981878284544891082485331470888529210881 •

p132 = 293351100534073339320273736685554040546989773558978742766077630132017865996601983557083266543920963624936810354879103450020778081793

• 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:

#!/usr/bin/perl
#
# Make Msieve NFS format files from GGNFS poly file
#   -- Bob Backstrom Oct 2007 --
#
# Run GGNFS with "$SAVEPAIRS=1;" in factLat.pl to
# save rels in gzip format at each cycle.
#
# msieve.dat     Write N ddddd to first line then
#                append rels with cmd:
#                gunzip -c spairs.save.gz >> msieve.dat
#
#                or manually:
#                cat spairs.dump.i >> msieve.dat
#                for all dump files.
#
# msieve.fb      N ddddd, R0, R1 (R1 = 1 if m present),
#                Y0 -> R0 and Y1 -> R1
#                coeffs ci -> Ai 0<= i <= {deg}
#
# worktodo.ini   N
#
# ------------------------------------------------

$PREFIX = "n";               # Poly file prefix
$SAVE   = "spairs.save.gz";  # Rels save file
$MSIEVE = "msieve -nc -v";   # Msieve NFS, verbose

# ------------------------------------------------

$FILE1 = "$PREFIX.poly";     # Input poly file
$FILE2 = "msieve.dat";       # Output dat file
$FILE3 = "msieve.fb";        # Factor base file
$FILE4 = "worktodo.ini";     # Work to do file

$r[0] = "0";
$r[1] = "0";

# c5: 9000
# c4: -76048988
# ...

$deg = 0;

open(IN, "$FILE1");          # Find poly degree

while($line = <IN>)
{
    $line = lc($line);

    if($line =~ /^\s*c(\d+)/)
    {
        if($deg < $1) { $deg = $1 }
    }
}

if(!$deg)
{
    close(IN);
    print "Coeffs \"cn: [-]ddd\" not found in \"$FILE1\"\n";
    exit 1;
}

for($i = 0; $i <= $deg; $i++){ $c[$i] = "0"; }

if( -e $FILE2 )              # Check for dat file 
{
    print "\nFile: \"$FILE2\" already present\n\n";
    open(REP, "-");

    while(print "Overwrite (y/n): ")
    {
        $reply = <REP>;
        $reply = lc($reply);

        if($reply =~ /^\s*n\s*$/)
        {
            print "\nExit\n\n";
	    close(IN);
            close(REP);
            exit 1;
        }
        elsif($reply =~ /^\s*y\s*$/)
        {
            print "\nCont...\n";
            close(REP);
            last;
        }
    }
}

print "\ndeg: $deg\n";

seek(IN, 0, 0);             # rewind input file
open(OUT1, ">$FILE2");      # dat file
open(OUT2, ">$FILE3");      # fb file
open(OUT3, ">$FILE4");      # worktodo file

while($line = <IN>)
{
    $line = lc($line);                # lower case

    if($line =~ /^\s*n\s*:\s*(\d+)/)  # n: ddd
    {
       $n = $1;
    }
    elsif($line =~ /^\s*m\s*:\s*(\d+)/) # m: ddd
    {
        $r[0] = "-" . $1;    # (no arith, just strings)
        $r[1] = 1;
    }
    elsif($line =~ /^\s*y(\d+)\s*:\s*(-*)(\d+)/)
    {
        $r[$1] = $2 . $3;    # yi: [-]ddd
    }

# deg: 5
# c5: 200
# c0: -7

    elsif($line =~ /^\s*c(\d+)\s*:\s*(-*)(\d+)/)
    {
        $c[$1] = $2 . $3;    # ci: [-]ddd
    }

# rlim: 3000000
# alim: 3000000

    elsif($line =~ /^\s*rlim\s*:\s*(\d+)/)  # rlim: ddd
    {
        $frmax = $1;
    }
    elsif($line =~ /^\s*alim\s*:\s*(\d+)/)  # alim: ddd
    {
        $famax = $1;
    }

# lpbr: 28
# lpba: 28

    elsif($line =~ /^\s*lpbr\s*:\s*(\d+)/)  # lpbr: ddd
    {
        $srtfbits = $1;
    }
    elsif($line =~ /^\s*lpba\s*:\s*(\d+)/)  # lpba: ddd
    {
        $satfbits = $1;
    }
}

print OUT1 "N $n\n";    # N ddd to dat
print OUT3 "$n\n";      # ddd to worktodo

print OUT2 "N $n\n";    # N ddd to fb
print      "N $n\n";

$s = "R0 $r[0]\n" .
     "R1 $r[1]\n";

print OUT2 $s;          # R0, R1 to fb
print      $s;

for($i = 0, $s = ""; $i <= $deg; $i++)
{
    $s = $s . "A$i $c[$i]\n";
}

print OUT2 $s;          # A0 - A{deg} to fb
print      $s;

$s = "FRMAX $frmax\n" .
     "FAMAX $famax\n" .
     "SRTFBITS $srtfbits\n" .
     "SATFBITS $satfbits\n"; 

print OUT2 $s;          # FRMAX etc to fb
print      $s;

close(IN);
close(OUT1);
close(OUT2);
close(OUT3);

$cmd = "gunzip -c $SAVE >> $FILE2";

print "==> $cmd\n";
system($cmd);           # Append rels to dat

$cmd = "$MSIEVE";

print "==> $cmd\n";
system($cmd);           # Run Msieve

# Send 5 BELLS at end of run
use IO::Handle;
STDOUT->autoflush(1);

for($i = 0; $i < 5; $i++){sleep 1;print "\a";}

• 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 • 10¹⁸⁷ + 17 [61₁₈₆3]	c177	p54:	573395679707400699385348747479834393752793967409490749 •
		p124:	1245645552644475714914257635039358945570950278650907410937990090328439047225546137808020213496628143001027627071390746085277

37 • 10¹⁸⁷ + 17 [41₁₈₆3]	c177	p89:	16292765621288919609478817054628424562953771570853171629703611379365529746626204307635029 •
		p89:	60809281348649681244719041706611205948284047834909959845329179920172944231048578394381343
Feb 11, 2012

53 • 10¹⁸⁶ - 17 [58₁₈₅7]	c176	p53:	10084513156525457970727463196872899527953549967140989 •
		p124:	6036217412723331039917515149835578292552836609990455555790073034039585668074025591780219023725303827139468556384153161668349
Feb 10, 2012

25 • 10¹⁸⁶ - 61 [27₁₈₅1]	c176	p46:	5414636935281406913349458857105484780449526483 •
		p53:	15009116190485478016577138811493608631091125451562089 •
		p78:	342195966763892628879123527833453886016064164105727964142669362057924357193181

5 • 10¹⁸⁵ - 3 [49₁₈₄7]	c175	p50:	11398583918308311218706977630346228414893336146411 •
		p126:	606280965113162727317335313147807804249146421743294918972031072509629360133892713710215314034646846435307514835203848156835539
Feb 9, 2012

16 • 10¹⁸⁵ - 61 [17₁₈₄1]	c175	p58:	3915166379901174117146850512522031279127428887324486329099 •
		p117:	831280377056776699125672696659090108177362353866724263173674093298986320848399854987890490487646811801650745771445097

6 • 10¹⁸¹ - 7 [59₁₈₀3]	c171	p38:	89899333984936105365387819186986113099 •
		p55:	1289747829959069521869855916958833257526365034799135453 •
		p79:	2936165076289167327584889888926912970057218559655263629096011171234579616000291

8 • 10¹⁸¹ - 11 [26₁₈₀3]	c171	p53:	18057144754324462860980952700331403229136335844665561 •
		p119:	14947696641251754547842343415035403390374999327855981901663427093065122255797738079334758187412859310023657585899298051
Feb 8, 2012

2 • 10¹⁸¹ - 7 [19₁₈₀3]	c171	p76:	2422412979800028060875855273385371436650307497481923996545305433879222350917 •
		p96:	292642058061099792698815532391447578570153293300449978434095450619299934615417887567871388531427

3 • 10¹⁸⁰ + 7 [30₁₇₉7]	c170	p52:	3357886592224964813424893960925970858540249084816807 •
		p118:	6421772340762707259521884513510240331991395754693705229521694663499363397052934796480061189870059727049936465643276799

7 • 10¹⁷⁹ - 9 [69₁₇₈1]	c169	p70:	1257951721263604352139589829106892400427551425645294710182642789568763 •
		p100:	7646682242190591161556198373637317987171335314757235302755083444223092418917335695838897522440941369

14 • 10¹⁷⁸ - 17 [46₁₇₇1]	c168	p77:	28546821019147319808650585282197294410198331762531797916032908379099041809097 •
		p92:	24832798801999526689331064181452647365336077731458037938999856817608909966198557805360440387
Feb 7, 2012

65 • 10¹⁷⁷ + 43 [72₁₇₆7]	c167	p80:	16924478768088386980498460554883134209509010986941801847151531818618471942261317 •
		p88:	1467786839436429428180563997498291748574948606652120905924251950685514095210980066161771

55 • 10¹⁷⁷ + 71 [61₁₇₆9]	c167	p55:	2851128820743888475836237010276601462602337935480787861 •
		p113:	10895474519832749198233966619277676008247730710565857786146603139801620537451903788209503232561917359117479223413

7 • 10¹⁸⁸ - 3 [69₁₈₇7]	c179	p52:	8980629593779837881775872309824081556163029918148921 •
		p128:	10230394460543631963862926785288748328173848556134820932383789990085930266983455379884348909161445413917516502102654062516131561
Feb 6, 2012

58 • 10¹⁸⁸ + 23 [64₁₈₇7]	c179	p67:	4225510255158679922267168868436266349800907032976526469820181398279 •
		p112:	3641607396613340916595768197129946213530148152110531376295580741540284845634344610869797393934839694639241054697

46 • 10¹⁸⁸ + 17 [51₁₈₇3]	c179	p49:	3483918410417653328026025291809676294239358737081 •
		p130:	6031940532844945205031708236972941727762753225496898645969583576605344615126483413085920246168251254539204418216058542930622437761
Feb 5, 2012

2 • 10¹⁸⁷ - 3 [19₁₈₆7]	c178	p62:	30188495243559431954129076808724172422794849359392479901419669 •
		p116:	62523352205841974641767247686152369037786705686420794585068971430543609011985992247691266480187863785691927767719697
Feb 4, 2012

76 • 10¹⁸⁶ - 31 [84₁₈₅1]	c177	p51:	549912142248176426540374928191713556628153736428687 •
		p63:	139947160526923518637115866924995979080921958077022614090765997 •
		p64:	1330233117551404608027769538269470145154474038858930771641831359

23 • 10¹⁸⁶ + 1 [76₁₈₅7]	c177	p74:	82852533287089694323679764305245118514955218464542290650087686067157533887 •
		p103:	2427646868274669847990548662348786299820114576030390825552946317745212049456729871591740702807339148439

4 • 10¹⁸⁵ - 3 [39₁₈₄7]	c176	p44:	24544359207043689314883852987401263868524717 •
		p64:	1711254231106590390191469193234817699792475403912781328971783723 •
		p69:	270313594614181001025713349777904935988854107792014326687398953865981
Feb 3, 2012

76 • 10¹⁸⁴ - 31 [84₁₈₃1]	c175	p59:	29460257503252184970709166351635031930764364878114240357159 •
		p116:	74663419348000381298846732070866283068117367730428952360716033656340344447268473304568155003281325712591590998685467

77 • 10¹⁸³ - 23 [85₁₈₂3]	c174	p58:	6744382706193432641832885793386737167677761517184697668901 •
		p116:	90647777027425773029509550850435602579653517479739306740131823901260703866178973840768526489238057807840308662203143
Feb 2, 2012

6 • 10¹⁸¹ + 7 [60₁₈₀7]	c172	p60:	410017432524380165263628364615764230851743814725679469252361 •
		p112:	3182332185507896285509820418496848430448675599100716022605720663029243697716260322491423099353138680884612531017

11 • 10¹⁸¹ + 1 [36₁₈₀7]	c172	p77:	10905410780162656819613512455615837082468916188215552894644437145282544436421 •
		p96:	367019267812351470809773879128645674324689358075404776986456768496906939191541539509582451096203

7 • 10¹⁸¹ - 54 • 10⁹⁰ - 7 [7₉₀17₉₀]	c171	p68:	55044964558230548226715805354895941529243390609498854364080111602501 •
		p104:	11949118162523157933642618955742334829658207744413603335544885387132310467425482592203495415286751669489
Feb 1, 2012

58 • 10¹⁷⁸ + 23 [64₁₇₇7]	c169	p64:	1879648905210242779506742210680008175641391002894787905369910181 •
		p106:	3734894355985399192947926070678889627596132194943997013702162544043609024082392806121810470762077249450191

47 • 10¹⁷⁸ + 61 [52₁₇₇9]	c169	p78:	115408121164094735012236175664796745389444902756462350565310383181720875166223 •
		p92:	11034103582781337864927757606282630036211683990647968980583740201381062663832992545798233093

44 • 10¹⁹⁵ - 71 [48₁₉₄1]	c187	p63:	186845470107006737433272393672146713833382868952776188334682761 •
		p125:	16702000706236220312036776285302483076538341383058505144014360796350368924725188782442691877133923333309755758789171502834417

> Top of page

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