Discussion of definitions

[a1call]

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

[paulunderwood]

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.

[a1call]

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:

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.

[Dr Sardonicus]

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.

[rudy235]

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"

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!

[a1call]

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

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

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]

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.