mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Software (https://www.mersenneforum.org/forumdisplay.php?f=10)
-   -   Primality testing non-Mersennes (https://www.mersenneforum.org/showthread.php?t=22962)

lukerichards 2018-01-24 21:29

Primality testing non-Mersennes
 
Hi,

I've used P95 to identify a number of smallish PRPs. They are not of the form 2[SUP]p[/SUP]-1.

One in particular is [TEX]3^{19217} - 2[/TEX] which I believe has 9169 digits. I assume, in a world tackling the search for Megaprimes, that the fact this is not available on The Prime Database means that this is composite. However, I'd like to test this myself...

Is it possible to do this with P95? To get a proof one way or another. Or is there some alternative software which can test a prime like this?

Thanks,

Luke

Dubslow 2018-01-24 21:44

[url]http://factordb.com/index.php?query=3%5E19217-2[/url]

It was proven prime in July 2015 by a member of this forum.

He probably used the Primo software for it.

It's not too difficult to establish the compositeness (or lack thereof) of such small numbers. Even using Python and a naively-simple implementation of the Euler PRP test or Miller-Rabin test can quickly establish that it is a least a pseudo-prime (or composite for other similar sized numbers) in a minute or two on a now-slow Sandy Bridge laptop.

For all further efforts, I highly recommend using the FactorDB as your launching point.

science_man_88 2018-01-24 21:58

[QUOTE=lukerichards;478273]Hi,

I've used P95 to identify a number of smallish PRPs. They are not of the form 2[SUP]p[/SUP]-1.

One in particular is [TEX]3^{19217} - 2[/TEX] which I believe has 9169 digits. I assume, in a world tackling the search for Megaprimes, that the fact this is not available on The Prime Database means that this is composite. However, I'd like to test this myself...

Is it possible to do this with P95? To get a proof one way or another. Or is there some alternative software which can test a prime like this?

Thanks,

Luke[/QUOTE]
You can even use your brain ( literally proved it in my head it doesn't have divisors below 19) modular tricks can be used.

VBCurtis 2018-01-24 22:04

[QUOTE=lukerichards;478273]I assume, in a world tackling the search for Megaprimes, that the fact this is not available on The Prime Database means that this is composite. [/QUOTE]
Eh? Which database are you referring to?

If you find a number is PRP, it is very very very likely prime. Two different PRP tests convince most folks, but since exceptions exist a proof is required to call it prime. Assuming any PRP is not prime isn't a wise plan- you either find documentation it's an exception (PRP but not prime, I mean), or you should assume it's actually a prime.

lukerichards 2018-01-24 22:21

[QUOTE=science_man_88;478276]You can even use your brain ( literally proved it in my head it doesn't have divisors below 19) modular tricks can be used.[/QUOTE]

Eh?

science_man_88 2018-01-24 22:25

[QUOTE=lukerichards;478281]Eh?[/QUOTE]

An extention of Fermat's little theorem is what I used.

lukerichards 2018-01-24 22:26

[QUOTE=VBCurtis;478277]Eh? Which database are you referring to?

If you find a number is PRP, it is very very very likely prime. Two different PRP tests convince most folks, but since exceptions exist a proof is required to call it prime. Assuming any PRP is not prime isn't a wise plan- you either find documentation it's an exception (PRP but not prime, I mean), or you should assume it's actually a prime.[/QUOTE]

Thanks.

I was referring to Primes.utm.edu but I've since realised their database only searches for top5000 primes, not all primes.

lukerichards 2018-01-24 22:27

[QUOTE=science_man_88;478282]An extention of Fermat's little theorem is what I used.[/QUOTE]

To test that a 9000 digit number was prime in your head? Impressive. Could you elaborate?

science_man_88 2018-01-24 22:30

[QUOTE=lukerichards;478284]To test that a 9000 digit number was prime in your head? Impressive. Could you elaborate?[/QUOTE]

a^(k*(p-1)) is congruent to 1 mod p. I trial factored up to p = 19.


All times are UTC. The time now is 08:44.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.