Factoring database

[smh]

Originally Posted by maxal

As an experiement, I've run a little helper that factors low hanging fruits from http://factordb.com/listtype.php?t=3 (in random order) with msieve and submits the factors. The current speed is about a couple of minutes per number.

So, don't be surprised if the length of "Smallest numbers without known factors" will increase soon. ;)

I've factored several thousand 70-74 digit numbers over the last week or so, but this is getting to labor intensive. How have you automated this?

[maxal]

Originally Posted by kar_bon

Do you pick the number by random also? Or the lowest (currently at 74 digits) first?

It grabs all numbers (out of 100) with 65+ and factors them in random order.
Before each factoring, the scripts check if the number still does not have FF status to avoid repeating job already completed by someone else.

Originally Posted by smh

How have you automated this?

Simple perl script does the job.

Actually, I run six such scripts concurrently.

[maxal]

btw, does factordb.com support cyclotomic polynomials?
I've tried notation Phi(n,x) (adopted in ECM) but there was no luck.

[mdettweiler]

Originally Posted by maxal

It grabs all numbers (out of 100) with 65+ and factors them in random order.
Before each factoring, the scripts check if the number still does not have FF status to avoid repeating job already completed by someone else.

Are you doing ECM on these prior to QSing them? From what I've seen, many of the numbers on the list can be easily knocked out in the first couple of rounds of the "scan" button.

[maxal]

Originally Posted by mdettweiler

Are you doing ECM on these prior to QSing them?

msieve does all the job (including brief ECM).

[Andi_HB]

Can you please post you Perl Program?

[CRGreathouse]

Originally Posted by mdettweiler

Are you doing ECM on these prior to QSing them? From what I've seen, many of the numbers on the list can be easily knocked out in the first couple of rounds of the "scan" button.

I wonder what the optimal amount of ECM is for these numbers. msieve does 30 curves at B1 = 2000 if I read the source correctly, plus a good number of P-1 and P+1 tests.

[maxal]

Here is my script.
Please notice that I did not mean to make it comprehensive or fault-tolerant.
Don't blame me if it occasionally resulted in DDoS of factordb.com or something.
Also, the script highly depends on the current format of data received from factordb.com. Any changes in this format may break the script functionality.
So, use it with caution on your own risk and periodically monitor its activity.

Currently it uses msieve for factoring and wget for communicating with factordb.com
You need to specify full path and executable names of these programs in the header.

Multiple instances of the script must be run from different directories.

#!/usr/bin/perl
use strict;

print("FactorDB Helper 1.2\n");

# wget executable
my $wget = "wget --no-check-certificate";

# msieve executable
my $msieve = "/home/maxal/libs/msieve/msieve/trunk/msieve -t 3";

$| = 1;
$/ = undef;

while(1) {

my @todo;

# getting 100 smallest unfactored numbers
$_ = `$wget -O - http://factordb.com/listtype.php?t=3`;

# however, it may be a good idea to get the second hundred
#$_ = `$wget -O - http://factordb.com/listtype.php?t=3&start=100`;


while( /<a href=\"index\.php\?id=([^\"]*)\"><font color=\"\#002099\">([^<]*)<\/font><\/a><sub>&lt;(\d+)&gt;<\/sub>/gs ) {
    my $id = $1;
    my $digits = $3;
    
    if( $digits >= 65 ) {
	push(@todo,$id);
    }
}

if( scalar(@todo) == 0 ) {
    print("No suitable numbers. Resting for a while.\n");
    sleep 60;
    next;
}

#shuffle todo
shuffle(@todo);

print("Todo size: ",scalar(@todo),"\n");

foreach (@todo) { 
    my $id = $_;

    # checking status, just in case
    $_ = `$wget -O - http://factordb.com/index.php?id=$id`;
    if( /<td>FF<\/td>/ ) {
	print("\nid=$id is already factored.\n\n");
	next;
    }

    # getting number in decimal
    $_ = `$wget -O - http://factordb.com/index.php?showid=$id`;
    if( ! /<td align=\"center\">(\d+)<br>/gs ) {
	print("Error 1\n");
	sleep 60;
	next;
    }
    
    my $number = $1;
    my $digits = length($number);
    
    print("Factoring $digits-digit number (id=$id)\n");
    
    if( $digits >= 80 ) {
	$_ = `$msieve -v -n $number`;
    }
    else {
	$_ = `$msieve -v $number`;
    }
    
    if( /prp\d+ factor: (\d+)\s/s ) {
	my $factor = $1;
	print("\nFactor found: $factor\n\n");
	$_ = `$wget --post-data "report=$factor&format=0" -O - http://factordb.com/index.php?id=$id`;
    }
    else {
	print("Error 2\n");
	sleep 60;
    }
}
}


exit;


sub shuffle {
    for (my $i = 0; $i < @_; $i++) {
        my $j = rand(@_ - $i) + $i;             # pick random element
        ($_[$i], $_[$j]) = ($_[$j], $_[$i]);    # swap 'em
    }
}

[Syd]

Nice script!

I added a new parameter to listtype.php - perpage. If you want you can display more or less than 100 per page now. Limit is 1000.

Another one:
&scriptmode=1

Displays just the internal id's + the number of digits, seperated by a space. One id per line.

This is a lot faster than retrieving all the other information from the database.

And the last one:

getrandom.php
Parameters:
n: number of numbers [1..100], 1 default
t: type. 2=> Unknown, 3=> Composite, default: Probable prime
mindig: minimum number of digits [40..?] , 65 default

returns the same format as listtype.php with scriptmode enabled.

Maybe these are useful to you :-)

[firejuggler]

to adapt the script for windows machine, just change the 3 first line to

#!H:\strawbery\perl <---- where you have installed perl
use strict;

print("FactorDB Helper 1.2\n");

# wget executable
my $wget = "H:/Docume~1/Vincent/Bureau/script/wget --no-check-certificate";
 <--- where you have wget

# msieve executable
my $msieve = "H:/Docume~1/Vincent/Bureau/script/msieve147 -t 3"; <---- where you have msieve

and you might want to add a shortcut
with

H:\strawberry\perl\bin\perl.exe "H:\Documents and Settings\Vincent\Bureau\script\script.pl" 
<-- where your script is

and if it is not too much too ask, is there a way to copy the factorisation to a file?

[maxal]

Originally Posted by Syd

getrandom.php
Parameters:
n: number of numbers [1..100], 1 default
t: type. 2=> Unknown, 3=> Composite, default: Probable prime
mindig: minimum number of digits [40..?] , 65 default

returns the same format as listtype.php with scriptmode enabled.

Maybe these are useful to you :-)

Thanks, that's helpful
But n=100 seems to produce only a couple of dozens id's ;(
Also, parameter maxdig would be helpful to avoid factorization of monsters.

On a different topic, could you please add support for cyclotomic polynomials (similarly to Phi() in ecm) ?