What does 3-PRP means exactly ? (in pfgw primality test)
up vote
4
down vote
favorite
When i do primality test for large integers with the software pfgw, it returns either composite or 3-PRP.
1: What does 3-PRP means exactly?
2: What is the error ratio?
3: When the test return Composite, does it mean "probably composite"?
prime-numbers primality-test
edited Nov 21 at 12:08
amWhy
191k27223439
asked Aug 4 at 21:26
François Huppé
18410
add a comment |
up vote
4
down vote
favorite
When i do primality test for large integers with the software pfgw, it returns either composite or 3-PRP.
1: What does 3-PRP means exactly?
2: What is the error ratio?
3: When the test return Composite, does it mean "probably composite"?
prime-numbers primality-test
edited Nov 21 at 12:08
amWhy
191k27223439
asked Aug 4 at 21:26
François Huppé
18410
1
strangely, there is not much information when i google this...
– François Huppé
Aug 5 at 4:18
2
The result "composite" is definitely correct. If the result is $3-PRP$, the number is very probably prime, unless it has a very special form. I am not sure, whether pfgw applies the weak or the strong Fermat-pseudoprime-test.
– Peter
Aug 6 at 8:34
add a comment |
up vote
4
down vote
favorite
up vote
4
down vote
favorite
When i do primality test for large integers with the software pfgw, it returns either composite or 3-PRP.
1: What does 3-PRP means exactly?
2: What is the error ratio?
3: When the test return Composite, does it mean "probably composite"?
prime-numbers primality-test
edited Nov 21 at 12:08
amWhy
191k27223439
asked Aug 4 at 21:26
François Huppé
18410
When i do primality test for large integers with the software pfgw, it returns either composite or 3-PRP.
1: What does 3-PRP means exactly?
2: What is the error ratio?
3: When the test return Composite, does it mean "probably composite"?
prime-numbers primality-test
prime-numbers primality-test
edited Nov 21 at 12:08
amWhy
191k27223439
asked Aug 4 at 21:26
François Huppé
18410
edited Nov 21 at 12:08
amWhy
191k27223439
asked Aug 4 at 21:26
François Huppé
18410
edited Nov 21 at 12:08
amWhy
191k27223439
edited Nov 21 at 12:08
amWhy
191k27223439
edited Nov 21 at 12:08
amWhy
191k27223439
191k27223439
asked Aug 4 at 21:26
François Huppé
18410
asked Aug 4 at 21:26
François Huppé
18410
asked Aug 4 at 21:26
François Huppé
18410
18410
1
strangely, there is not much information when i google this...
– François Huppé
Aug 5 at 4:18
2
The result "composite" is definitely correct. If the result is $3-PRP$, the number is very probably prime, unless it has a very special form. I am not sure, whether pfgw applies the weak or the strong Fermat-pseudoprime-test.
– Peter
Aug 6 at 8:34
add a comment |
1
strangely, there is not much information when i google this...
– François Huppé
Aug 5 at 4:18
2
The result "composite" is definitely correct. If the result is $3-PRP$, the number is very probably prime, unless it has a very special form. I am not sure, whether pfgw applies the weak or the strong Fermat-pseudoprime-test.
– Peter
Aug 6 at 8:34
1
1
strangely, there is not much information when i google this...
– François Huppé
Aug 5 at 4:18
strangely, there is not much information when i google this...
– François Huppé
Aug 5 at 4:18
2
2
The result "composite" is definitely correct. If the result is $3-PRP$, the number is very probably prime, unless it has a very special form. I am not sure, whether pfgw applies the weak or the strong Fermat-pseudoprime-test.
– Peter
Aug 6 at 8:34
The result "composite" is definitely correct. If the result is $3-PRP$, the number is very probably prime, unless it has a very special form. I am not sure, whether pfgw applies the weak or the strong Fermat-pseudoprime-test.
– Peter
Aug 6 at 8:34
add a comment |
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
It means it is a base 3 pseudoprime, i.e. it passes a Fermat test for base 3:
$3^{n-1} = 1pmod n$.
I agree this finding the test type is not obvious. I looked in gw_prp.cpp to see the test, as the documentation doesn't seem really explicit. It is also noted on the Wikipedia page for Fermat primality test. I just verified it with some base-3 PSPs that are not base-3 SPSPs.
There is typically trial factoring done before, which greatly reduces the error rate. E.g. 1000067795191 with only report 3-PRP if "-f 0" is used to turn off trial factoring. But 100000185552877 will report as 3-PRP using the default trial factoring.
For the probability of the test itself, I will defer to Kim and Pomerance (1989). For general purpose use, we would normally want something much stronger (e.g. BPSW), but PFGW typically is using this test for quite large numbers where the probabilities are vastly smaller. Given the speed of the underlying gwnum library and the PFGW implementation, it makes an excellent pre-test for multi-thousand digit numbers.
Like most useful compositeness tests (often called probable prime tests), the possible answers are:
- Composite. Barring implementation bugs, this is 100% correct.
- Definitely prime. If this is returned, it is 100% correct.
- Probably prime. It passes this test, which may be more or less stringent.
- Error. This test may be inappropriate for the input, or we can't understand the input, or our algorithm has failed somehow. In these cases this is a far better return value than any of the above.
While it is possible to construct tests that give "probably composite" as a possible result, that is generally not useful. I can't think of any examples in common use.
answered Nov 30 at 17:55
DanaJ
2,3061917
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
It means it is a base 3 pseudoprime, i.e. it passes a Fermat test for base 3:
$3^{n-1} = 1pmod n$.
I agree this finding the test type is not obvious. I looked in gw_prp.cpp to see the test, as the documentation doesn't seem really explicit. It is also noted on the Wikipedia page for Fermat primality test. I just verified it with some base-3 PSPs that are not base-3 SPSPs.
There is typically trial factoring done before, which greatly reduces the error rate. E.g. 1000067795191 with only report 3-PRP if "-f 0" is used to turn off trial factoring. But 100000185552877 will report as 3-PRP using the default trial factoring.
For the probability of the test itself, I will defer to Kim and Pomerance (1989). For general purpose use, we would normally want something much stronger (e.g. BPSW), but PFGW typically is using this test for quite large numbers where the probabilities are vastly smaller. Given the speed of the underlying gwnum library and the PFGW implementation, it makes an excellent pre-test for multi-thousand digit numbers.
Like most useful compositeness tests (often called probable prime tests), the possible answers are:
- Composite. Barring implementation bugs, this is 100% correct.
- Definitely prime. If this is returned, it is 100% correct.
- Probably prime. It passes this test, which may be more or less stringent.
- Error. This test may be inappropriate for the input, or we can't understand the input, or our algorithm has failed somehow. In these cases this is a far better return value than any of the above.
While it is possible to construct tests that give "probably composite" as a possible result, that is generally not useful. I can't think of any examples in common use.
answered Nov 30 at 17:55
DanaJ
2,3061917
add a comment |
up vote
1
down vote
accepted
It means it is a base 3 pseudoprime, i.e. it passes a Fermat test for base 3:
$3^{n-1} = 1pmod n$.
I agree this finding the test type is not obvious. I looked in gw_prp.cpp to see the test, as the documentation doesn't seem really explicit. It is also noted on the Wikipedia page for Fermat primality test. I just verified it with some base-3 PSPs that are not base-3 SPSPs.
There is typically trial factoring done before, which greatly reduces the error rate. E.g. 1000067795191 with only report 3-PRP if "-f 0" is used to turn off trial factoring. But 100000185552877 will report as 3-PRP using the default trial factoring.
For the probability of the test itself, I will defer to Kim and Pomerance (1989). For general purpose use, we would normally want something much stronger (e.g. BPSW), but PFGW typically is using this test for quite large numbers where the probabilities are vastly smaller. Given the speed of the underlying gwnum library and the PFGW implementation, it makes an excellent pre-test for multi-thousand digit numbers.
Like most useful compositeness tests (often called probable prime tests), the possible answers are:
- Composite. Barring implementation bugs, this is 100% correct.
- Definitely prime. If this is returned, it is 100% correct.
- Probably prime. It passes this test, which may be more or less stringent.
- Error. This test may be inappropriate for the input, or we can't understand the input, or our algorithm has failed somehow. In these cases this is a far better return value than any of the above.
While it is possible to construct tests that give "probably composite" as a possible result, that is generally not useful. I can't think of any examples in common use.
answered Nov 30 at 17:55
DanaJ
2,3061917
add a comment |
up vote
1
down vote
accepted
up vote
1
down vote
accepted
It means it is a base 3 pseudoprime, i.e. it passes a Fermat test for base 3:
$3^{n-1} = 1pmod n$.
I agree this finding the test type is not obvious. I looked in gw_prp.cpp to see the test, as the documentation doesn't seem really explicit. It is also noted on the Wikipedia page for Fermat primality test. I just verified it with some base-3 PSPs that are not base-3 SPSPs.
There is typically trial factoring done before, which greatly reduces the error rate. E.g. 1000067795191 with only report 3-PRP if "-f 0" is used to turn off trial factoring. But 100000185552877 will report as 3-PRP using the default trial factoring.
For the probability of the test itself, I will defer to Kim and Pomerance (1989). For general purpose use, we would normally want something much stronger (e.g. BPSW), but PFGW typically is using this test for quite large numbers where the probabilities are vastly smaller. Given the speed of the underlying gwnum library and the PFGW implementation, it makes an excellent pre-test for multi-thousand digit numbers.
Like most useful compositeness tests (often called probable prime tests), the possible answers are:
- Composite. Barring implementation bugs, this is 100% correct.
- Definitely prime. If this is returned, it is 100% correct.
- Probably prime. It passes this test, which may be more or less stringent.
- Error. This test may be inappropriate for the input, or we can't understand the input, or our algorithm has failed somehow. In these cases this is a far better return value than any of the above.
While it is possible to construct tests that give "probably composite" as a possible result, that is generally not useful. I can't think of any examples in common use.
answered Nov 30 at 17:55
DanaJ
2,3061917
It means it is a base 3 pseudoprime, i.e. it passes a Fermat test for base 3:
$3^{n-1} = 1pmod n$.
I agree this finding the test type is not obvious. I looked in gw_prp.cpp to see the test, as the documentation doesn't seem really explicit. It is also noted on the Wikipedia page for Fermat primality test. I just verified it with some base-3 PSPs that are not base-3 SPSPs.
There is typically trial factoring done before, which greatly reduces the error rate. E.g. 1000067795191 with only report 3-PRP if "-f 0" is used to turn off trial factoring. But 100000185552877 will report as 3-PRP using the default trial factoring.
For the probability of the test itself, I will defer to Kim and Pomerance (1989). For general purpose use, we would normally want something much stronger (e.g. BPSW), but PFGW typically is using this test for quite large numbers where the probabilities are vastly smaller. Given the speed of the underlying gwnum library and the PFGW implementation, it makes an excellent pre-test for multi-thousand digit numbers.
Like most useful compositeness tests (often called probable prime tests), the possible answers are:
- Composite. Barring implementation bugs, this is 100% correct.
- Definitely prime. If this is returned, it is 100% correct.
- Probably prime. It passes this test, which may be more or less stringent.
- Error. This test may be inappropriate for the input, or we can't understand the input, or our algorithm has failed somehow. In these cases this is a far better return value than any of the above.
While it is possible to construct tests that give "probably composite" as a possible result, that is generally not useful. I can't think of any examples in common use.
answered Nov 30 at 17:55
DanaJ
2,3061917
edited Nov 30 at 18:03
answered Nov 30 at 17:55
DanaJ
2,3061917
answered Nov 30 at 17:55
DanaJ
2,3061917
answered Nov 30 at 17:55
DanaJ
2,3061917
2,3061917
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2872406%2fwhat-does-3-prp-means-exactly-in-pfgw-primality-test%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
strangely, there is not much information when i google this...
– François Huppé
Aug 5 at 4:18
2
The result "composite" is definitely correct. If the result is $3-PRP$, the number is very probably prime, unless it has a very special form. I am not sure, whether pfgw applies the weak or the strong Fermat-pseudoprime-test.
– Peter
Aug 6 at 8:34