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

 2016-05-17, 07:28 #45 PawnProver44     "NOT A TROLL" Mar 2016 California 197 Posts Phew. Thanks for saving me the stress about the time. I am only finding prps up to 200k digits to save even more hassel.
2016-05-17, 08:26   #46
axn

Jun 2003

113518 Posts

Quote:
 Originally Posted by paulunderwood 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)?

2016-05-17, 08:29   #47
paulunderwood

Sep 2002
Database er0rr

3,527 Posts

Quote:
 Originally Posted by axn 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.

2016-05-17, 14:49   #48
danaj

"Dana Jacobsen"
Feb 2011
Bangkok, TH

11100010102 Posts

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

 2016-05-17, 15:00 #49 PawnProver44     "NOT A TROLL" Mar 2016 California 19710 Posts 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
2016-05-17, 15:11   #50
paulunderwood

Sep 2002
Database er0rr

3,527 Posts

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

 2016-05-17, 15:15 #51 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 38A16 Posts 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.
 2016-05-17, 15:22 #52 PawnProver44     "NOT A TROLL" Mar 2016 California 197 Posts 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
2016-05-17, 15:25   #53
PawnProver44

"NOT A TROLL"
Mar 2016
California

19710 Posts

Quote:
 Originally Posted by axn 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).

2016-05-17, 15:30   #54
danaj

"Dana Jacobsen"
Feb 2011
Bangkok, TH

38A16 Posts

Quote:
 Originally Posted by paulunderwood 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.

2016-05-17, 15:48   #55
danaj

"Dana Jacobsen"
Feb 2011
Bangkok, TH

2·3·151 Posts

Quote:
 Originally Posted by PawnProver44 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.

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

Sat Jan 16 06:25:09 UTC 2021 up 44 days, 2:36, 0 users, load averages: 4.15, 3.69, 3.31