mersenneforum.org Discussion of definitions
 Register FAQ Search Today's Posts Mark Forums Read

 2021-05-12, 09:57 #1 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2×1,087 Posts 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
2021-05-12, 10:20   #2
paulunderwood

Sep 2002
Database er0rr

F5E16 Posts

Quote:
 Originally Posted by a1call 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

2021-05-12, 10:40   #3
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

2·1,087 Posts

Quote:
 Originally Posted by paulunderwood 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

2021-05-12, 13:02   #4
Dr Sardonicus

Feb 2017
Nowhere

2×33×5×19 Posts

Quote:
 Originally Posted by a1call 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

2021-05-12, 13:27   #5
rudy235

Jun 2015
Vallejo, CA/.

40216 Posts

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ē/

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.

2021-05-12, 14:31   #6
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

2·1,087 Posts

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

2021-05-12, 19:56   #7
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

2·1,087 Posts

Quote:
 Originally Posted by Batalov 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post kladner GPU to 72 43 2012-01-27 20:43 Raman Cunningham Tables 27 2008-12-04 21:17 R.D. Silverman NFSNET Discussion 15 2007-04-11 12:50 AntonVrba Prime Cullen Prime 5 2007-04-04 04:59 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