mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > And now for something completely different

Reply
 
Thread Tools
Old 2021-05-12, 09:57   #1
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2×1,087 Posts
Default Discussion of definitions

I think it is important to distinguish (here) between known pseudoprime PRP's and Probably-Prime PRP's. There is a known Carmichael numbers with much greater digits count.

https://www.mersenneforum.org/showpo...1&postcount=19

Last fiddled with by a1call on 2021-05-12 at 10:27
a1call is offline   Reply With Quote
Old 2021-05-12, 10:20   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

F5E16 Posts
Default

Quote:
Originally Posted by a1call View Post
I think it is important to distinguish (here) between known pseudoprime PRP's and Probably-Prime PRP's.
PRP means "probable prime". So it is tautological to say probable prime PRP..

Pseudoprimes are abbreviated to PSP.

Last fiddled with by paulunderwood on 2021-05-12 at 10:39
paulunderwood is offline   Reply With Quote
Old 2021-05-12, 10:40   #3
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2·1,087 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
PRP means "probable prime". So it is tautology to say probable prime PRP..

Pseudoprimes are abbreviated to PSP.
It is semantics and the intention is obvious here but:

Quote:
In number theory, a probable prime (PRP) is an integer that satisfies a specific condition that is satisfied by all prime numbers, but which is not satisfied by most Composite numbers.
https://en.m.wikipedia.org/wiki/Probable_prime

Accordingly, a pseudoprime (composite) can be categorized as a PRP with that definition.
I still think a distinguishment is in order here.

Last fiddled with by a1call on 2021-05-12 at 11:00
a1call is offline   Reply With Quote
Old 2021-05-12, 13:02   #4
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2×33×5×19 Posts
Default

Quote:
Originally Posted by a1call View Post
It is semantics and the intention is obvious here but:



https://en.m.wikipedia.org/wiki/Probable_prime

Accordingly, a pseudoprime (composite) can be categorized as a PRP with that definition.
I still think a distinguishment is in order here.
As I understand it, "PRP" is used for a number which does not test as composite by a given compositeness test (Fermat, Euler, Miller-Rabin, Lucas, BPSW, what have you) but whose nature (prime or composite) is not known, while "pseudoprime" is used for a number which does not test as composite, but which is known to be composite. AFAIK none of the values (10^p - 1)/9 designated as PRP are known to be composite, so the distinction is nugatory here. The case p = 49081 is currently being tested with PRIMO by the intrepid paulunderwood. When the test is complete, the number will be designated either prime or composite, with "prime" the odds-on favorite.

The name of the Pari-GP function ispseudoprime() has been publicly lamented elsewhere on this Forum precisely because it ignores the above distinction.

Last fiddled with by Dr Sardonicus on 2021-05-12 at 13:03 Reason: w
Dr Sardonicus is offline   Reply With Quote
Old 2021-05-12, 13:27   #5
rudy235
 
rudy235's Avatar
 
Jun 2015
Vallejo, CA/.

40216 Posts
Default

Hello Dr Sardonicus. I just learned a new word in English, something that seldom happens. And it is a nice word too.


nu·ga·to·ry
/ˈn(y)o͞oɡəˌtôrē/

adjective
of no value or importance.
"a nugatory and pointless observation"


Quote:
AFAIK none of the values (10^p - 1)/9 designated as PRP are known to be composite, so the distinction is nugatory here.
You made my morning!
rudy235 is offline   Reply With Quote
Old 2021-05-12, 14:31   #6
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2·1,087 Posts
Default

@Dr Sardonicus,

I agree with your assessment that a probable prime should be defined clearly as an integer which passes some probable-primality-test such as the Fermat test and is not known to be composite aka "Probable-Prime" and if it is known to be composite then it should not be referred to as a Probable-Prime but rather a Pseudo-Prime. However, The definition of a Probable-Prime (PRP) is vague/imprecise at the moment as indicated by my admittedly superficial internet search:

Quote:
In number theory, a probable prime (PRP) is an integer that satisfies a specific condition that is satisfied by all prime numbers, but which is not satisfied by most composite numbers. Different types of probable primes have different specific conditions. While there may be probable primes that are composite (called pseudoprimes), the condition is generally chosen in order to make such exceptions rare.
https://en.wikipedia.org/wiki/Probable_prime

Quote:
A pseudoprime is a probable prime (an integer that shares a property common to all prime numbers) that is not actually prime. Pseudoprimes are classified according to which property of primes they satisfy.

Some sources use the term pseudoprime to describe all probable primes, both composite numbers and actual primes.
https://en.wikipedia.org/wiki/Pseudo...ctual%20primes.

I even seem to recall that that (or some other Wikipedia article on the subject) indicating (Not the current version) that the term Pseudo-Prime & Probable-Prime were at some point interchangeable (used by some authors) and since have been distinguished by more recent authors.
a1call is offline   Reply With Quote
Old 2021-05-12, 19:56   #7
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2·1,087 Posts
Default

Quote:
Originally Posted by Batalov View Post
Discussion of definitions (once again supporting the earlier observation that "A thought, once spoken, is a lie") is moved to a separate thread.
No such implications was implied. I am very much aware of how awesome these achievements are. I was only pointing out a lack in the definition's preciseness. It is a shame to have the meaning not properly defined.
Congrats to both of you gentlemen. You have my outmost respect, please be assured of that.
a1call is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
P-1 discussion kladner GPU to 72 43 2012-01-27 20:43
10,375- LA discussion Raman Cunningham Tables 27 2008-12-04 21:17
Open Discussion R.D. Silverman NFSNET Discussion 15 2007-04-11 12:50
P-1 discussion AntonVrba Prime Cullen Prime 5 2007-04-04 04:59
New .dat discussion VJS Prime Sierpinski Project 7 2006-07-25 14:31

All times are UTC. The time now is 10:07.


Fri Dec 3 10:07:32 UTC 2021 up 133 days, 4:36, 0 users, load averages: 1.20, 1.31, 1.27

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