Very (large) PRPs?

[PawnProver44]

I was reading this list, when I found out it wasn't too hard to find all those PRPs. I looked at the end of the list, and found that "random" PRPs are discovered with 50,000 digits. What should I best use to find "random" PRPs say between 50k and 200k digits? Not that I would want to ever submit them on the PRPtop because the site simply does not accept "random" PRPs and there are no such PRPs there either. I would expect this to be done in about a week too, (200k digits almost), but correct me if that is not possible, please.

[LaurV]

The "list" will accept "random" PRPs. Find one with more than 46k digits and send it there. Just find one.

[axn]

The submission page lists 20,000 digit as the minimum. But to actually enter Top 10000, it should be 42k+.

The submission page also says that

please type one number by line using the following format :
number,its number of digits in base 10
and don't type their decimal expansion

So it is possible that if your number doesn't have a compact form, it might not be accepted.

[PawnProver44]

Can you find any examples of "random" PRPs on the site? I was looking for a specific program that I could input the large number in a .txt file (about 200,000 digits) and call nextprime(x) or previousprime(x), Pfgw is too slow is my guess?

[Batalov]

Originally Posted by PawnProver44

...and call nextprime(x) or previousprime(x), Pfgw is too slow is my guess?

PRPtop is full of them as it is:
nextprime(10^x) (and next and next and next)
nextprime(12^x)
some other random example
Finding one is very easy, if that's your goal or if you find it fun thing to do. Most contributors there don't stop until they submit tens of thousands.

[PawnProver44]

First, with what text editor can carry 200k+digits (need at least 400k digits) so I can input into pfgw (or some other program which can give me a direct result regardless the size for nextprime(x) = ?):

input.txt:
------------------------------------------
nextprime(597612129456797651389670218204770656.........(199,928 more digits).........107345799455301271768055018207593331)-597612129456797651389670218204770656.........(199,928 more digits).........107345799455301271768055018207593331
------------------------------------------

And get a result like this

-f -i input.txt

nextprime(x)-x is a 3-PRP!

-t -q input.txt

nextprime(597612129456797651389670218204770656.........(199,928 more digits).........107345799455301271768055018207593331)

is a Fermat and Lucus PRP!

I don't want to risk notepad, but someone who has tried that please let me know.

Pfgw output I do nextprime(x)-x, but when i input nextprime(x) it gives me:

nextprime(x) is a 3-PRP!

So I do not know what nextprime(x) is, but I can ignore that using nextprime(x)-x.

[Batalov]

Originally Posted by PawnProver44

So I do not know what nextprime(x) is, but I can ignore that.

Dude, I can tell you that nextprime(10^1000000000) is a billion-digit prime (even without calculating it; I can ignore that, too).

Where can I get my EFF money!??

[alpertron]

Originally Posted by Batalov

Dude, I can tell you that nextprime(10^1000000000) is a billion-digit prime (even without calculating it; I can ignore that, too).

Where can I get my EFF money!??

prevprime(10^1000000000) is a billion-digit prime but nextprime(10^1000000000) is not.

[Batalov]

Good point! I lost a "+" in the message: it is a billion+ digit number and qualifies for the EFF prize not!

[PawnProver44]

Here are my running times with Wolfram | Alpha? (random 10, 20, 40, 80 digit numbers) Can anyone compare to Pfgw to see if it is faster?

nextprime(1615940397) = 1615940399 (1.2 s)

nextprime(14068924638939642180) = 14068924638939642181 (1.3 s)

nextprime(3718587170008038384873784221963098409550) = 3718587170008038384873784221963098409563 (1.3 s)

nextprime(97783010505674166402735696905325823805408510851148150244960782744188145048695585) = 97783010505674166402735696905325823805408510851148150244960782744188145048695591 (1.3 s)

I was expecting the time to be at lest 16 times as much for doubling the number of digits? Is this true for Pfgw? Thanks to anyone who can give approximate running times for Pfgw for (1,000; 2,000; 4,000; 8,000; digits PRPs please) as a larger version of my test.

Edit: I forgot to call nextprime(x) for random 80 digit number.

[alpertron]

Originally Posted by PawnProver44

Here are my running times with Wolfram | Alpha? (random 10, 20, 40 digit numbers) Can anyone compare to Pfgw to see if it is faster?

nextprime(1615940397) = 1615940399 (1.2 s)

nextprime(14068924638939642180) = 14068924638939642181 (1.3 s)

nextprime(3718587170008038384873784221963098409550) = 3718587170008038384873784221963098409563 (1.3 s)

nextprime(97783010505674166402735696905325823805408510851148150244960782744188145048695585) = 97783010505674166402735696905325823805408510851148150244960782744188145048695591 (1.3 s)

From those timings, it is clear that the real time for nextprime is 0.0 s for all instances, and 1.2 s - 1.3 s is lost in the Web service. It can even include an artificial delay where no computation is done, so you cannot send too many requests to the server.