mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2018-01-24, 21:29   #1
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

4408 Posts
Default Primality testing non-Mersennes

Hi,

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

One in particular is 3^{19217} - 2 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
lukerichards is offline   Reply With Quote
Old 2018-01-24, 21:44   #2
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

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.

Last fiddled with by Dubslow on 2018-01-24 at 21:48
Dubslow is offline   Reply With Quote
Old 2018-01-24, 21:58   #3
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by lukerichards View Post
Hi,

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

One in particular is 3^{19217} - 2 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.
science_man_88 is offline   Reply With Quote
Old 2018-01-24, 22:04   #4
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

22×3×359 Posts
Default

Quote:
Originally Posted by lukerichards View Post
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.
VBCurtis is offline   Reply With Quote
Old 2018-01-24, 22:21   #5
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

1001000002 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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?
lukerichards is offline   Reply With Quote
Old 2018-01-24, 22:25   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by lukerichards View Post
Eh?
An extention of Fermat's little theorem is what I used.
science_man_88 is offline   Reply With Quote
Old 2018-01-24, 22:26   #7
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

12016 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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 is offline   Reply With Quote
Old 2018-01-24, 22:27   #8
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

25·32 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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?
lukerichards is offline   Reply With Quote
Old 2018-01-24, 22:30   #9
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by lukerichards View Post
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.

Last fiddled with by science_man_88 on 2018-01-24 at 23:02 Reason: Fixed major typo
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Testing an expression for primality 1260 Software 17 2015-08-28 01:35
Testing Mersenne cofactors for primality? CRGreathouse Computer Science & Computational Number Theory 18 2013-06-08 19:12
a new Deterministic primality testing wsc812 Computer Science & Computational Number Theory 36 2013-03-04 06:25
Automated primality testing with LLRnet mdettweiler Conjectures 'R Us 18 2008-03-04 00:06
a new primality testing method jasong Math 1 2007-11-06 21:46

All times are UTC. The time now is 15:59.

Sat Sep 19 15:59:59 UTC 2020 up 9 days, 13:10, 1 user, load averages: 1.58, 1.25, 1.23

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.