Factoring database

[maxal]

Here is a new version that supports both msieve and yafu:

#!/usr/bin/perl
use strict;

print("FactorDB Helper 1.5\n");

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

# msieve and/or yafu executables
my $msieve = "/home/maxal/libs/msieve/msieve/trunk/msieve -t 3";
my $yafu = "/home/maxal/libs/yafu-1.19.2/yafu";

# "M" for msieve, "Y" for yafu
my $MorY = "Y";

# min and max number of digits to factor
my $mindig = 65;
my $maxdig = 100;


$| = 1;
$/ = undef;

while(1) {

    my @todo;
    
    # getting 100 random unfactored numbers
    $_ = `$wget -O - "http://factordb.com/getrandom.php?n=100&t=3&mindig=$mindig&maxdig=$maxdig"`;
    
    # getiing 100 smallest unfactored numbers
    #$_ = `$wget -O - "http://factordb.com/listtype.php?t=3&scriptmode=1"`;
    
    
    while( /(\d{19})\s(\d+)/gs ) {
    
    #  /<a href=\"index\.php\?id=([^\"]*)\"><font color=\"\#002099\">([^<]*)<\/font><\/a><sub>&lt;(\d+)&gt;<\/sub>/gs ) {
    
        my $id = $1;
        my $digits = $2;
        
        if( ($digits >= $mindig) && ($digits <= $maxdig) ) {
            push(@todo,$id);
        }
    }
    
    print("Todo size: ",scalar(@todo),"\n");
    
    if( scalar(@todo) == 0 ) {
        print("No suitable numbers. Resting for a while.\n");
        sleep 60;
        next;
    }
    
    shuffle(@todo);
    
    
    foreach (@todo) { 
        my $id = $_;
    
        # checking status and getting the number in decimal
        $_ = `$wget -O - http://factordb.com/getnumber.php?id=$id`;
        if( ! /(\S+)\s(\d+)/ ) {
            print("Error 1\n");
            sleep 60;
            next;
        }
        
        if( $1 ne "C" ) {
            print("\nid=$id has known factors.\n\n");
            next;
        }
        
        my $number = $2;
        my $digits = length($number);
        
        print("Factoring $digits-digit number (id=$id)\n");
    
    
        my $factor = 0;
        
        
        if( $MorY eq "M" ) {
            # factoring with msieve
        
            if( $digits >= 80 ) {
                $_ = `$msieve -v -n $number`;
            }
            else {
                $_ = `$msieve -v $number`;
            }
            if( /prp\d+ factor: (\d+)\s/s ) {
                $factor = $1;
            }
        }
        
        if( $MorY eq "Y" ) {
            #factoring with yafu
        
            $_ = `$yafu "factor($number)"`;
            if( /PRP\d+ = (\d+)\s/s ) {
                $factor = $1;
            }
        }
        
        if( $factor == 0 ) {
            print("Error 2\n");
            sleep 60;
            next;
        }
        
        # reproting the factor
        print("\nFactor found: $factor\n\n");
        $_ = `$wget --post-data "report=$factor&format=0" -O - http://factordb.com/index.php?id=$id`;
    }
}

exit;


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

[firejuggler]

So far, Yafu seem a bit quicker, so I stay with it.

[kar_bon]

Here's a slightly changed version of Syd's script (uses only yafu, here WIN) Version 1.4.1.

Changes:

- logging on screen lists only numbers (with FactorDB-id and decimal representation) and factors found
- same logging in file 'log.txt'
- only one number is selected with "getrandom.php" not 100
- changing the digit-range for factoring on the fly:
-- if no number was found in the range of 65 to 75 digits (default) the max range border is increased by 1
-- if 5 numbers were tested in a row of the same digit-range, the max border is decreased by 1

The output looks like this:

Decreasing range to 65-73 digits.
Factoring C72, id=1100000000215417418
107698193083421293260516846795731434061232959793477539564812373340276287
Factors:
26405284013285459123374233622798414903151
4078660658572519568543061554737

Factoring C71, id=1100000000215417870
28504080459937869696853196518741764601588734850800683566672894693639223
Factors:
1748688300560557
16300263718125547456234420973318896388823562351146807539

Increasing range to 65-74 digits.
Increasing range to 65-75 digits.
Increasing range to 65-76 digits.
Factoring C76, id=1100000000025315182
1974478705750231792145699016077046904574325297781281987720170399119810269059
Factors:
29295408896033352638313544033
67398912667765477451991694259949184848483041123

Perhaps the output of the timings of siqs from yafu could also be logged.

Note:
First I used wget 1.8.2 from a UnixUtils package to run that script under WIN, but that version does not support data-upload with the "--post-data" option.
So I searched for another version, comes with gawk.exe but without some needed DLL's.
That 'wget.exe' needs libeay32.dll, libiconv2.dll, libintl3.dll and libssl32.dll.
After I found them, it's working great now.

I've changed the extension of the attached file into *.txt, rename to *.pl again.

[Andi_HB]

Thank you kar bon !
Now i have a other wget.exe with .dll`s and it`s running for me too.
I was wondering me why the factors are not submitted before.
Now it works fine. Thanks again.

Regards Andi_HB

[Syd]

I made a small change so you dont need to "POST" the factors anymore, simple "GET" will do now, too.

[Andi_HB]

Syd you don`t want to increase the Smallest unproven prime from 1000 digits to 2000 digits or more? There are only 8450 Unproven (probable) primes in the List.

[Syd]

Originally Posted by Andi_HB

Syd you don`t want to increase the Smallest unproven prime from 1000 digits to 2000 digits or more? There are only 8450 Unproven (probable) primes in the List.

Sure, can do. But it will take a lot of time to prove them all.

Btw.: Whats the best/fastest tool to use for primality proving?

[kar_bon]

The (few minutes ago) unproven 1000-digit number 10^999+7:

Here are different callings with pfgw V3.3.6:

>pfgw -l -t -q"10^999+7"
PFGW Version 3.3.6.20100908.Win_Stable [GWNUM 25.14]
Output logging to file pfgw.out
Primality testing 10^999+7 [N-1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 5
Calling Brillhart-Lehmer-Selfridge with factored part 0.51%
10^999+7 is PRP! (0.1865s+0.0033s)

>pfgw -l -tp -q"10^999+7"
PFGW Version 3.3.6.20100908.Win_Stable [GWNUM 25.14]
Output logging to file pfgw.out
Primality testing 10^999+7 [N+1, Brillhart-Lehmer-Selfridge]
Running N+1 test using discriminant 5, base 1+sqrt(5)
Calling Brillhart-Lehmer-Selfridge with factored part 1.30%
10^999+7 is Lucas PRP! (0.4724s+0.0021s)

>pfgw -l -tc -q"10^999+7"
PFGW Version 3.3.6.20100908.Win_Stable [GWNUM 25.14]
Output logging to file pfgw.out
Primality testing 10^999+7 [N-1/N+1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 5
Running N+1 test using discriminant 13, base 1+sqrt(13)
Calling N+1 BLS with factored part 1.30% and helper 0.51% (4.46% proof)
10^999+7 is Fermat and Lucas PRP! (0.5927s+0.0022s)

Those all only gets a PRP.

Using a helper file with the factors of N-1 and N+1:

2
139
557
3
7
29
25243
44267
93199469863
16622228274680328721
129828685855865750907048113732006068712091646588660399057028288891675878011928140341693521730335952497241789568992132121979762823763531070211612968223909822033434002496345971636586658440721130839012689196098180606762153068539938809143782413354282490083035830899694616965129832580716441426879575325175418028894153009338058058869

(Note: The last factor is composite! Don't know if this is allowed.)

gives:

>pfgw -l -tc -hfact.txt -q"10^999+7"
PFGW Version 3.3.6.20100908.Win_Stable [GWNUM 25.14]
Output logging to file pfgw.out
Primality testing 10^999+7 [N-1/N+1, Brillhart-Lehmer-Selfridge]
Reading factors from helper file fact.txt
Running N-1 test using base 5
Running N+1 test using discriminant 13, base 1+sqrt(13)
Calling N+1 BLS with factored part 36.98% and helper 0.51% (111.48% proof)
10^999+7 is prime! (0.8895s+0.0023s)

This will give a prime here and all timings are neglectable.

[Mini-Geek]

Originally Posted by kar_bon

(Note: The last factor is composite! Don't know if this is allowed.)

No, it's not allowed:

 -h   Factor Helper file 
      An argument is required for this switch.
      Use this option when you are using the n-1 or n+1 test and run short of
      small factors to get to the 33.33% limit. If you have found larger
      factors with other programs (ecm, rho, whatever) you can put them in
      the helper file one on a line.
      You should ONLY use prime factors in this file, or the result is invalid.
      The file can also be made up of expressions, and not simply
      numbers Example: pfgw -tp -hhelper.txt
      When testing (-t -tp -tm -tc) any factor in this file that is
      not part of the N-1 or N+1 (either or both depending upon which method
      of testing), will be printed to screen with a warning listing that 
      this factor does not "fit".  (Note this behavior can be overridden
      by using the HideNoFactor=true in the pfgw.ini file)
      Multiple -h command line switches can be used (for multiple 
      factor files).  Example pfgw -tc -hplus -hminus input_file

I tested this again with the composite factor removed, and PFGW was only able to PRP it.

WinPFGW ran with "-tc -hhelper.txt -q10^999+7"

PFGW Version 3.3.6.20100908.Win_Stable [GWNUM 25.14]

Output logging to file pfgw.out
Primality testing 10^999+7 [N-1/N+1, Brillhart-Lehmer-Selfridge]
Reading factors from helper file helper.txt
Running N-1 test using base 5
Special modular reduction using all-complex FFT length 192 on 10^999+7
Running N+1 test using discriminant 13, base 1+sqrt(13)
Special modular reduction using all-complex FFT length 192 on 10^999+7
Calling N+1 BLS with factored part 4.34% and helper 0.51% (13.53% proof)
10^999+7 is Fermat and Lucas PRP! (0.0888s+0.0404s)

If I'm not mistaken, the known factors have to come to 33.33% of the size of the number. This is rarely possible/easy with 1000-2000 digit numbers.

For this particular number, I have already ran a primality test with Primo. The certificate is attached. The test took about 21 minutes. The verification takes about 0.03 seconds. As far as I know, and without having N-1 or N+1 easily factored to 33.33% of the size of N, this is the fastest way to prove primality for numbers this size.

[kar_bon]

Originally Posted by Mini-Geek

No, it's not allowed:

Thanks, not read that part.

For this particular number, I have already ran a primality test with Primo. The certificate is attached. The test took about 21 minutes. The verification takes about 0.03 seconds. As far as I know, and without having N-1 or N+1 easily factored to 33.33% of the size of N, this is the fastest way to prove primality for numbers this size.

Please try the same number with the ECM-applet from D-Alpern, I've tested few numbers some time ago and compared with PRIMO, the applet seems faster if I remember right.

[Mini-Geek]

Originally Posted by kar_bon

Please try the same number with the ECM-applet from D-Alpern, I've tested few numbers some time ago and compared with PRIMO, the applet seems faster if I remember right.

Yes, a good deal faster.
The applet:

Factorization complete in 0d 0h 14m 25s
ECM: 0 modular multiplications
Prime checking: 5552675 modular multiplications

Timings:
Primality test of 1 number: 0d 0h 14m 21.2s

Primo:

[Running Times]
Initialization=0.48s
1stPhase=19mn 30s
2ndPhase=5mn 50s
Total=25mn 21s

Is there a faster implementation of the method the applet uses? I'd expect an efficient native implementation to run much faster than an applet.