mersenneforum.org Very (large) PRPs?
 Register FAQ Search Today's Posts Mark Forums Read

2016-05-17, 15:59   #56
PawnProver44

"NOT A TROLL"
Mar 2016
California

197 Posts

Quote:
 Originally Posted by danaj Yes, that should be the most efficient method. Sieve a range using whatever appropriate tool to get just the candidates without small factors. Run PFGW on those candidates. This just runs its Fermat test with the default base. When one passes, congrats, you have your PRP. (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.

 2016-05-17, 16:34 #57 Xyzzy     "Mike" Aug 2002 22·5·397 Posts 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
2016-05-17, 16:42   #58
PawnProver44

"NOT A TROLL"
Mar 2016
California

197 Posts

Quote:
 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!

 2016-05-17, 16:48 #59 Xyzzy     "Mike" Aug 2002 22·5·397 Posts 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
 2016-05-17, 16:51 #60 PawnProver44     "NOT A TROLL" Mar 2016 California 197 Posts 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  2016-05-17, 18:02 #61 danaj "Dana Jacobsen" Feb 2011 Bangkok, TH 2·3·151 Posts 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
2016-05-18, 02:38   #62
axn

Jun 2003

47·103 Posts

Quote:
 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 2016-05-18, 03:48 #63 LaurV Romulan Interpreter Jun 2011 Thailand 23×397 Posts Quote:  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...

2016-05-18, 04:27   #64
Xyzzy

"Mike"
Aug 2002

22×5×397 Posts

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

 2016-05-18, 04:40 #65 PawnProver44     "NOT A TROLL" Mar 2016 California 197 Posts 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
2016-05-18, 04:48   #66
danaj

"Dana Jacobsen"
Feb 2011
Bangkok, TH

2·3·151 Posts

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

 Similar Threads Thread Thread Starter Forum Replies Last Post Batalov And now for something completely different 10 2019-09-12 13:31 T.Rex Miscellaneous Math 13 2015-09-01 13:09 schickel FactorDB 1 2015-08-03 02:50 Random Poster FactorDB 0 2012-07-24 10:53 gd_barnes Conjectures 'R Us 57 2011-09-12 12:31

All times are UTC. The time now is 06:22.

Sat Jan 16 06:22:03 UTC 2021 up 44 days, 2:33, 0 users, load averages: 3.57, 3.45, 3.17

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.