PRPs that are composites

[mdettweiler]

Originally Posted by rogue

Yes. Note that -f and -f100 are equivalent. These false PRPs probably would have been factored by -f200, but the extra time to factor is probably not worth it. You could try -b5 to change the base for the PRP test. I don't know if that works with a script though.

It does--I've tried it before.

[Puzzle-Peter]

Some more:

855419506*3^3-1 = 23,096,326,661 = 87,743*263,227          prime at n=10
862434914*3^4-1 = 69,857,228,033 = 152,597*457,789        prime at n=12
870070870*3^7-1 = 1,902,844,992,689 = 563,153*3,378,913 prime at n=15

[gd_barnes]

Originally Posted by rogue

Yes. Note that -f and -f100 are equivalent. These false PRPs probably would have been factored by -f200, but the extra time to factor is probably not worth it. You could try -b5 to change the base for the PRP test. I don't know if that works with a script though.

Mark,

Please explain why you continue to indicate that there is a problem with GMP or gwnum. Why are these false PRPs? They look like good PRPs to me as found by PFGW. They just happen to be composite with large factors found. It isn't like PFGW completely missed a small factor. The script and PFGW appear to be acting like they should be. Upon a primality test, they find them to be composite and continue to test the k's until they find a prime.

Peter,

I would suggest using -f30 for base 3. I've tested it with -f100 and -f30 and found -f30 to be faster for scripting to n=25K. Although you'll get more composite PRPs, that's not a problem. The pl_prime file will be the same.


Gary

[rogue]

Originally Posted by gd_barnes

Please explain why you continue to indicate that there is a problem with GMP or gwnum. Why are these false PRPs? They look like good PRPs to me as found by PFGW. They just happen to be composite with large factors found. It isn't like PFGW completely missed a small factor. The script and PFGW appear to be acting like they should be. Upon a primality test, they find them to be composite and continue to test the k's until they find a prime.

In an optimal environment, only prime numbers would be output as PRP from a PRP test, but the PRP test is not perfect (which is why it is called a PRP test and what I sometimes forget). These numbers are some of the exceptions

My point is that I need to verify that the results of the test are valid and not caused by an underlying software issue. At this time, I do not believe that there is software issue in either GMP or gwnum.

As I stated above, I think that it is a good idea to use a different base than the default (which happens to be 3) when PRP testing base 3 numbers. The number of PRPs that turn out to be composite should be reduced.

[Puzzle-Peter]

Originally Posted by gd_barnes

Peter,

I would suggest using -f30 for base 3. I've tested it with -f100 and -f30 and found -f30 to be faster for scripting to n=25K. Although you'll get more composite PRPs, that's not a problem. The pl_prime file will be the same.

Gary

Next time I will. BTW did you get the mails for R3 k=850M to 875M and k= 875M to 900M? They were about the size you said was the limit of your mailbox.

[henryzz]

Originally Posted by Puzzle-Peter

Some more:

855419506*3^3-1 = 23,096,326,661 = 87,743*263,227          prime at n=10
862434914*3^4-1 = 69,857,228,033 = 152,597*457,789        prime at n=12
870070870*3^7-1 = 1,902,844,992,689 = 563,153*3,378,913 prime at n=15

I've just tested these numbers with my calculator. I can confirm that they are all 3-prp.
Would a SPRP test be hard to implement in pfgw? Would it be noticeably slower than the current PRP test?

[axn]

Originally Posted by henryzz

I've just tested these numbers with my calculator. I can confirm that they are all 3-prp.
Would a SPRP test be hard to implement in pfgw? Would it be noticeably slower than the current PRP test?

No. SPRP test is exactly the same as PRP test, except it would be a few iterations lesser (1 iteration less in case of composite, 1 or more iterations less in case of a PRP).

[gd_barnes]

Originally Posted by Puzzle-Peter

Next time I will. BTW did you get the mails for R3 k=850M to 875M and k= 875M to 900M? They were about the size you said was the limit of your mailbox.

Yes, I got them. It just takes me a while to get them added to the pages.

[gd_barnes]

Originally Posted by rogue

In an optimal environment, only prime numbers would be output as PRP from a PRP test, but the PRP test is not perfect (which is why it is called a PRP test and what I sometimes forget). These numbers are some of the exceptions

My point is that I need to verify that the results of the test are valid and not caused by an underlying software issue. At this time, I do not believe that there is software issue in either GMP or gwnum.

As I stated above, I think that it is a good idea to use a different base than the default (which happens to be 3) when PRP testing base 3 numbers. The number of PRPs that turn out to be composite should be reduced.

Hum, I see. I always expect that there will be composite PRPs at some point. Otherwise it wouldn't be called a PRP test. It would be a primality test.

As long as -b5 would not slow down testing of base 3, that seems like a reasonable idea. But...keep in mind that we're only finding perhaps 3 to 10 PRPs for every 10 million to 25 million k's that are tested on base 3, an amazingly small percentage. So if there's even a small slowdown by using -b5, I would recommend against it.


Gary

[mdettweiler]

Originally Posted by gd_barnes

Hum, I see. I always expect that there will be composite PRPs at some point. Otherwise it wouldn't be called a PRP test. It would be a primality test.

As long as -b5 would not slow down testing of base 3, that seems like a reasonable idea. But...keep in mind that we're only finding perhaps 3 to 10 PRPs for every 10 million to 25 million k's that are tested on base 3, an amazingly small percentage. So if there's even a small slowdown by using -b5, I would recommend against it.


Gary

Last time I started a base, I used -b8 (just for the heck of it ) and found that it didn't make any difference in the test times. The residues will of course be different (though they're comparable with others of the same base) but that's not really a big deal for new bases since we're not saving residues for those n-levels anyway.

[Batalov]

44766250*3^7+1 = 97903788751 is a composite base 3 PRP (also base 5 PRP and base 15 PRP).

97903788751 = 221251 * 442501 = p(2p-1).


(Found as 1933902*15^4+1. 1933902*15^7+1 is prime.)