mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2016-05-17, 15:59   #56
PawnProver44
 
PawnProver44's Avatar
 
"NOT A TROLL"
Mar 2016
California

197 Posts
Post

Quote:
Originally Posted by danaj View Post
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.
PawnProver44 is offline   Reply With Quote
Old 2016-05-17, 16:34   #57
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

5·7·227 Posts
Default

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

Xyzzy is offline   Reply With Quote
Old 2016-05-17, 16:42   #58
PawnProver44
 
PawnProver44's Avatar
 
"NOT A TROLL"
Mar 2016
California

110001012 Posts
Post

Quote:
Originally Posted by Xyzzy View Post
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!
PawnProver44 is offline   Reply With Quote
Old 2016-05-17, 16:48   #59
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

794510 Posts
Default

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:

Code:
#!/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
Xyzzy is offline   Reply With Quote
Old 2016-05-17, 16:51   #60
PawnProver44
 
PawnProver44's Avatar
 
"NOT A TROLL"
Mar 2016
California

197 Posts
Default

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.)

Last fiddled with by PawnProver44 on 2016-05-17 at 16:55
PawnProver44 is offline   Reply With Quote
Old 2016-05-17, 18:02   #61
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2·3·151 Posts
Default

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

Last fiddled with by danaj on 2016-05-17 at 18:05 Reason: Note difference in scripts
danaj is offline   Reply With Quote
Old 2016-05-18, 02:38   #62
axn
 
axn's Avatar
 
Jun 2003

113568 Posts
Default

Quote:
Originally Posted by PawnProver44 View Post
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
axn is online now   Reply With Quote
Old 2016-05-18, 03:48   #63
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

2×23×199 Posts
Default

Quote:
Originally Posted by axn View Post
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...
LaurV is online now   Reply With Quote
Old 2016-05-18, 04:27   #64
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

5×7×227 Posts
Default

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

Xyzzy is offline   Reply With Quote
Old 2016-05-18, 04:40   #65
PawnProver44
 
PawnProver44's Avatar
 
"NOT A TROLL"
Mar 2016
California

C516 Posts
Post

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.

Last fiddled with by PawnProver44 on 2016-05-18 at 04:47
PawnProver44 is offline   Reply With Quote
Old 2016-05-18, 04:48   #66
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2·3·151 Posts
Default

Quote:
Originally Posted by Xyzzy View Post
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.
danaj is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Near- and quasi-repunit PRPs Batalov And now for something completely different 10 2019-09-12 13:31
OEIS - 2^n-5 - LLT-like algorithm for finding PRPs T.Rex Miscellaneous Math 13 2015-09-01 13:09
PRPs not prime schickel FactorDB 1 2015-08-03 02:50
Proven PRPs? Random Poster FactorDB 0 2012-07-24 10:53
PRPs that are composites gd_barnes Conjectures 'R Us 57 2011-09-12 12:31

All times are UTC. The time now is 13:45.

Sun Jan 24 13:45:27 UTC 2021 up 52 days, 9:56, 0 users, load averages: 3.22, 3.20, 3.20

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.