- **Software**
(*https://www.mersenneforum.org/forumdisplay.php?f=10*)

- - **Primality testing non-Mersennes**
(*https://www.mersenneforum.org/showthread.php?t=22962*)

Primality testing non-MersennesHi,
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 |

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

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

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

[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? |

[QUOTE=lukerichards;478281]Eh?[/QUOTE]
An extention of Fermat's little theorem is what I used. |

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

[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? |

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