mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > FactorDB

Reply
 
Thread Tools
Old 2010-09-21, 01:06   #892
maxal
 
maxal's Avatar
 
Feb 2005

FC16 Posts
Default

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

Code:
#!/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
    }
}

Last fiddled with by maxal on 2010-09-21 at 01:07
maxal is offline   Reply With Quote
Old 2010-09-21, 01:17   #893
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

2·5·11·23 Posts
Default

So far, Yafu seem a bit quicker, so I stay with it.
firejuggler is online now   Reply With Quote
Old 2010-09-21, 13:36   #894
kar_bon
 
kar_bon's Avatar
 
Mar 2006
Germany

2·1,439 Posts
Default

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:
Code:
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.
Attached Files
File Type: txt DByafu.txt (2.8 KB, 161 views)
kar_bon is offline   Reply With Quote
Old 2010-09-21, 17:12   #895
Andi_HB
 
Andi_HB's Avatar
 
Mar 2007
Germany

4108 Posts
Default

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
Andi_HB is offline   Reply With Quote
Old 2010-09-22, 12:24   #896
Syd
 
Syd's Avatar
 
Sep 2008
Krefeld, Germany

111001102 Posts
Default

I made a small change so you dont need to "POST" the factors anymore, simple "GET" will do now, too.
Syd is offline   Reply With Quote
Old 2010-09-22, 12:36   #897
Andi_HB
 
Andi_HB's Avatar
 
Mar 2007
Germany

23×3×11 Posts
Default

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.
Andi_HB is offline   Reply With Quote
Old 2010-09-22, 12:53   #898
Syd
 
Syd's Avatar
 
Sep 2008
Krefeld, Germany

3468 Posts
Default

Quote:
Originally Posted by Andi_HB View Post
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?
Syd is offline   Reply With Quote
Old 2010-09-22, 13:14   #899
kar_bon
 
kar_bon's Avatar
 
Mar 2006
Germany

54768 Posts
Default

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

Here are different callings with pfgw V3.3.6:

Code:
>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)
Code:
>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)
Code:
>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:
Code:
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:

Code:
>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.

Last fiddled with by kar_bon on 2010-09-22 at 13:16
kar_bon is offline   Reply With Quote
Old 2010-09-22, 13:29   #900
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

Quote:
Originally Posted by kar_bon View Post
(Note: The last factor is composite! Don't know if this is allowed.)
No, it's not allowed:
Code:
 -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.
Code:
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.
Attached Files
File Type: txt primo-B33520443BDB7-001.out.txt (115.2 KB, 107 views)

Last fiddled with by Mini-Geek on 2010-09-22 at 13:32
Mini-Geek is offline   Reply With Quote
Old 2010-09-22, 13:37   #901
kar_bon
 
kar_bon's Avatar
 
Mar 2006
Germany

2×1,439 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
No, it's not allowed:
Thanks, not read that part.

Quote:
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.
kar_bon is offline   Reply With Quote
Old 2010-09-22, 14:20   #902
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts
Default

Quote:
Originally Posted by kar_bon View Post
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:
Code:
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:
Code:
[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.

Last fiddled with by Mini-Geek on 2010-09-22 at 14:20
Mini-Geek is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Database for k-b-b's: 3.14159 Miscellaneous Math 325 2016-04-09 17:45
Factoring database issues Mini-Geek Factoring 5 2009-07-01 11:51
database.zip HiddenWarrior Data 1 2004-03-29 03:53
Database layout Prime95 PrimeNet 1 2003-01-18 00:49
Is there a performance database? Joe O Lounge 35 2002-09-06 20:19

All times are UTC. The time now is 18:29.

Sat Mar 6 18:29:00 UTC 2021 up 93 days, 14:40, 0 users, load averages: 1.71, 1.76, 1.75

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.