Primality testing non-Mersennes

[lukerichards]

Hi,

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

One in particular is 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]

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

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]

Originally Posted by lukerichards

Hi,

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

One in particular is 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

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]

Originally Posted by lukerichards

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.

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]

Originally Posted by science_man_88

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

Eh?

[science_man_88]

Originally Posted by lukerichards

Eh?

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

[lukerichards]

Originally Posted by VBCurtis

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.

Thanks.

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

[lukerichards]

Originally Posted by science_man_88

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

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

[science_man_88]

Originally Posted by lukerichards

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

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