Very (large) PRPs?

[PawnProver44]

Originally Posted by danaj

Yes, that should be the most efficient method.

1. Sieve a range using whatever appropriate tool to get just the candidates without small factors.
   
2. Run PFGW on those candidates. This just runs its Fermat test with the default base. When one passes, congrats, you have your PRP.
   
3. (Optional) A Fermat test is one of the weaker tests, so we might want to do a little better.
   • We could run PFGW with a few different bases. I believe this is what factordb does.
   • We could run Paul's program that does his Frobenius-Underwood test, which is an efficient and pretty stringent test. If you go through the math, it essentially runs a Fermat and Lucas test at the same time with a good base selection process. I believe this is better than running a few more Fermat bases. Since this uses gwnum it's quite fast for large numbers.
   • We could run BPSW. Sadly there is no gwnum implementation, so it will be much slower at the sizes we're talking about. Since we only run one, the speed isn't as critical. You could run various Frobenius tests as well, but I think a Fermat plus BPSW would be convincing enough: people who accept PRPs would think this is enough, while people that want proofs aren't going to be more convinced by further PRP testing.

Exactly! I would use the weak prp tests, then on one weak-prp result, preform more strong tests to see that it is even very unlikely to be composite, and in that case just treat them as primes after all tests are performed.

[Xyzzy]

FWIW

Our wrapper script:

until [ -e pfgw.log ]; do nice -19 ./program4.py > tmp && ../pfgw64 -f -k tmp; done; rm tmp && rm pfgw.ini

program4.py is our (very lame) sieve program

More craziness here: http://www.mersenneforum.org/showthread.php?t=21252

So far 50,000 digit PRPs have been (fairly easily?) found using our very slow NUC. We are slowly improving our sieve program before going larger.

YMMV

[PawnProver44]

Originally Posted by Xyzzy

FWIW

Our wrapper program:

until [ -e pfgw.log ]; do nice -19 ./program4.py > tmp && ../pfgw64 -f -k tmp; done; rm tmp && rm pfgw.ini

program4.py is our (very lame) sieve program

More craziness here: http://www.mersenneforum.org/showthread.php?t=21252

So far 50,000 digit PRPs have been (fairly easily?) found using our very slow NUC. We are slowly improving our sieve program before going larger.

YMMV

My record for prps stands at 6,056 digits and want it to be slightly more than 200k digits. (200,192 digits for computing at least.) Your wrapper program should definitely help as well!

[Xyzzy]

We forgot to mention this:

Our sieve program is most likely slower than just feeding pfgw the unsieved candidates, but we want to convince ourselves that we have done at least a little of the programming to find stuff. Perhaps it gives us the illusion of control?

We are interested in improving our code but most suggestions will be beyond our math understanding. We hope to slowly remedy this.

The following code is lame, but for us it represents a lot of hard work and learning:

#!/usr/bin/python

from random import randint
from random import randrange

mp = 46
length = 50000
sievesize = 1000000

def quicktest(n):
    for p in smallprimes:
        if n % p == 0:
            return False
    return True

def sieve(n):
    multiples = set()
    for i in range(2, n + 1):
        if i not in multiples:
            yield i
            multiples.update(range(i * i, n + 1, i))

smallprimes = list(sieve(sievesize))

with open(str(mp)) as f:
   data = f.read()

flag = False

while flag == False:
    start = randint(0, len(data) - length)
    result = int(data[start:start + length])
    if len(str(result)) == length:
        if result % 10 == 1 or result % 10 == 3 or result % 10 == 7 or result % 10 == 9:
            if quicktest(result) == True:
                print result
                flag = True

[PawnProver44]

The sieve size I can choose, but I hope I do not pick a large range with no primes, that's the worst, though composites are limited by maximum prime gaps.

Here is a sieve example:

ABC2 233100857649...(200k+digits)...210016697705+$a

a: from 1 to 1000000 "step 2"

then auto-stop prp testing when one prime (prp) is found.

(As I am confused at "step 2" though I think I am just locating another .txt file with my remaining candidates.)

[danaj]

For generating a list of primes in python, RWH's python functions are short and very fast.

One thing I don't see in the docs is how to make PFGW stop once it finds a PRP. Your (Xyzzy) script would seem to make pfgw run on every value. Maybe that's ok -- you just find multiple PRPs. It does avoid the overhead of making the script call it one at a time.

For something not too dissimilar to generate a random 50k digit number then sieve 100k to depth 1e8:

perl -Mntheory=:all -E 'use bigint; my $n = join("",1+int(rand(9)),map { int(rand(10)) } 2..50000); say for Math::Prime::Util::GMP::sieve_primes($n,100000+$n,1e8);' >foo

or with my dev version with a bit less overhead:

perl -Mntheory=:all -E 'my $n = join("",1+int(rand(9)),map { int(rand(10)) } 2..50000); say "$n+$_" for sieve_range($n,100000,1e8);' >foo

Sieving to 1e6 takes under a second, and is too little for best efficiency.
Sieving to 1e9 on the 50k-digit random input with width 100k takes about 90 seconds.
Sieving to 1e9 on 100k-digit random input with width 500k takes about 3 minutes.
We would want deeper sieving for these sizes, but this shows the idea and gives an indication of time.

It looks like your program generates many random results, while mine is generating one then sieving a range. This should be more efficient than the trial division on each candidate.

Looks like PFGW is taking about 90-100 seconds for each 50k-digit candidate (with no trial factoring).

For 100k-digits it is taking about 400 seconds. About 4x longer for 2x larger input, which is great vs. the ~6x longer time for GMP BPSW for doubling bits. That doesn't count the lowered expectations of finding a prime at the larger size, meaning more expected tests per PRP found.

[axn]

Originally Posted by PawnProver44

Here is a sieve example:

ABC2 233100857649...(200k+digits)...210016697705+$a

a: from 1 to 1000000 "step 2"

Hopefully, while doing this in real life, you'll manage to not generate only even numbers as you're doing in the example

[LaurV]

Originally Posted by axn

Hopefully, while doing this in real life, you'll manage to not generate only even numbers as you're doing in the example

hahaha
BTW, couldn't he use +2*$a and avoid the "step 2" contraption? beside of the fact he said he is confused by it, the increment would be faster
Told ye he is only trolling...

[Xyzzy]

Originally Posted by danaj

One thing I don't see in the docs is how to make PFGW stop once it finds a PRP. Your (Xyzzy) script would seem to make pfgw run on every value. Maybe that's ok -- you just find multiple PRPs. It does avoid the overhead of making the script call it one at a time.

The wrapper script looks to see if a pfgw.log file exists, and quits if it does. The pfgw.log file is only written if a PRP is found.

[PawnProver44]

Sucess!!

nextprime(233100857649...(200k+digits)...210016697705) = 233100857649...(200k+digits)...210016702491



My point: I actually had someone else give me an output example using everything suggested here to give me a sample output of a "random" prp that size.

[danaj]

Originally Posted by Xyzzy

The wrapper script looks to see if a pfgw.log file exists, and quits if it does. The pfgw.log file is only written if a PRP is found.

Ah, I thought the Python script was writing multiple lines to the file. It seems to try to open a file named 46, so I couldn't run it, but now I see it just writes one line at a time.