mersenneforum.org  

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

Reply
 
Thread Tools
Old 2016-05-17, 07:28   #45
PawnProver44
 
PawnProver44's Avatar
 
"NOT A TROLL"
Mar 2016
California

197 Posts
Post

Phew. Thanks for saving me the stress about the time. I am only finding prps up to 200k digits to save even more hassel.
PawnProver44 is offline   Reply With Quote
Old 2016-05-17, 08:26   #46
axn
 
axn's Avatar
 
Jun 2003

3·5·17·19 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
PFGW will take 4 times as long for a doubling in length of the number, remembering that the primes are sparser for bigger numbers.
Wouldn't that be 8 times as much (4x for an individual PRP test, and 2x number of PRP tests)?
axn is offline   Reply With Quote
Old 2016-05-17, 08:29   #47
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,533 Posts
Default

Quote:
Originally Posted by axn View Post
Wouldn't that be 8 times as much (4x for an individual PRP test, and 2x number of PRP tests)?
Yes, this is what I have experienced when searching.
paulunderwood is offline   Reply With Quote
Old 2016-05-17, 14:49   #48
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

16128 Posts
Default

I'm confused where this 8k digit restriction is coming from. It works fine on 140k digit numbers.

Quote:
However, running Dana's perl is_prime() on a random 500k digit number will not work. You will have to call out to PFGW instead.
It would work fine if done correctly, but it in a practical sense you're right -- at this size PFGW is so much faster at this size that you really should run it first.
]
danaj is offline   Reply With Quote
Old 2016-05-17, 15:00   #49
PawnProver44
 
PawnProver44's Avatar
 
"NOT A TROLL"
Mar 2016
California

197 Posts
Post

200k digits for n/thoery at most?

EDIT: Is it the same for Dana's perl next_prime(x) and random_ndigit_prime(x) functions?

Last fiddled with by PawnProver44 on 2016-05-17 at 15:04
PawnProver44 is offline   Reply With Quote
Old 2016-05-17, 15:11   #50
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,533 Posts
Default

Quote:
Originally Posted by danaj View Post
It would work fine if done correctly, but it in a practical sense you're right -- at this size PFGW is so much faster at this size that you really should run it first.
Aha, your is_prime(n) is BPSW+another test; I was thinking in terms of is_provable_prime(n). I was confused.

I guess PawnProver44 can, in a single script file, sieve with one of your perl functions and call PFGW on surviving candidates. Is this right?

Last fiddled with by paulunderwood on 2016-05-17 at 15:21
paulunderwood is offline   Reply With Quote
Old 2016-05-17, 15:15   #51
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

38A16 Posts
Default

I guess I should try some larger numbers just to say that it's been done.

Even at 10k digits, using PFGW is faster, but not overwhelmingly so. Once you get much larger, I think using PFGW for an initial test, followed by Paul's standalone F-U program would give a very good combination. Paul's program uses gwnum, same as PFGW, takes about 3x longer to run, but a much more stringent test so good to use to confirm PFGW's result. It's still a PRP, but passing two Fermat tests and a Lucas test is good.

There has been a bit of confusion on the nextprime issue. PFGW has the (AFAIK) fastest available PRP test (albeit just a Fermat test). It also includes an expression evaluator that includes a nextprime command that happens to be very slow. I suspect it was intended for simple things like 'nextprime(50)#+59' where it works great, rather than for huge inputs.
danaj is offline   Reply With Quote
Old 2016-05-17, 15:22   #52
PawnProver44
 
PawnProver44's Avatar
 
"NOT A TROLL"
Mar 2016
California

197 Posts
Post

So then I can use the text file link like you sugessted earlier, then use the sieve command not listed in the module description, then prp test remaining candidates, then after that preform Paul's BPSW test and verify to make sure it is a Fermat and Lucus PRP? Perfect!

Last fiddled with by PawnProver44 on 2016-05-17 at 15:22
PawnProver44 is offline   Reply With Quote
Old 2016-05-17, 15:25   #53
PawnProver44
 
PawnProver44's Avatar
 
"NOT A TROLL"
Mar 2016
California

197 Posts
Post

Quote:
Originally Posted by axn View Post
Wouldn't that be 8 times as much (4x for an individual PRP test, and 2x number of PRP tests)?
Ok, I'll just record the time for a 391 digit prime using pfgw's nextprime(x) and then double each candidate 9 times to get to 200192 digits (close to my aim of 200k digits).
PawnProver44 is offline   Reply With Quote
Old 2016-05-17, 15:30   #54
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2×3×151 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Aha, your is_prime(n) is BPSW+another test; I was thinking in terms of is_provable_prime(n). I was confused.
Ah, that makes sense. Yes, my is_provable_prime is good for maybe 2k digits (and honestly you need one of the extended poly sets to run well past 500 digits). Primo is better once past 1k. Practically good to maybe 15k, works fine to ~35k if you have the time and resources.

Quote:
I guess PrawnProver44 can, in a single script file, sieve with one of your perl functions and call PFGW on surviving candidates. Is this right?
Yes. You could do the same with cnewpgen I believe, and I'm sure others have sieves that work well. I wrote a slightly nicer script in the 500k+ prime gaps thread, and tested it on Windows. It is appropriate for simple expressions -- using huge random inputs would need something different.
danaj is offline   Reply With Quote
Old 2016-05-17, 15:48   #55
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2×3×151 Posts
Default

Quote:
Originally Posted by PawnProver44 View Post
So then I can use the text file link like you sugessted earlier, then use the sieve command not listed in the module description, then prp test remaining candidates, then after that preform Paul's BPSW test and verify to make sure it is a Fermat and Lucus PRP? Perfect!
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.
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 12:10.

Sun Jan 24 12:10:18 UTC 2021 up 52 days, 8:21, 0 users, load averages: 2.66, 2.10, 1.81

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.