## Other

drummers-lowrise

Message boards : Generalized Fermat Prime Search : Generalized Fermat with odd base?

 Subscribe SortOldest firstNewest firstHighest rated posts first
Author Message
Bur
Volunteer tester

Joined: 25 Feb 20
Posts: 511
ID: 1241833
Credit: 408,509,608
RAC: 26,999

Message 142689 - Posted: 25 Aug 2020 | 17:59:15 UTC

I saw on OEIS A253242 that generalized Fermat number with odd base b are defined as (b^2^n + 1)/2.

Is it possible to efficiently test these for primality with genefer?

Ravi Fernando
Volunteer tester
Project scientist

Joined: 21 Mar 19
Posts: 206
ID: 1108183
Credit: 11,990,357
RAC: 5,561

Message 142692 - Posted: 25 Aug 2020 | 18:47:51 UTC - in response to Message 142689.

I don't think there's any fast primality test known for these numbers. Your best bet would be to run a PRP test (which can be done quickly for numbers of any form), and if it's a PRP, try to prove it either with ECPP or by factoring p-1 = (b^2^n - 1)/2 as much as possible.

JeppeSN

Joined: 5 Apr 14
Posts: 1727
ID: 306875
Credit: 41,389,304
RAC: 13,476

Message 142694 - Posted: 25 Aug 2020 | 19:35:12 UTC

You can find a bunch of these with this search: http://www.primenumbers.net/prptop/searchform.php?form=%28b%5En%2B1%29%2F2

For most of them, it has never been proved they are prime. PRP Top is a list of probable primes for which it is not practically possible to prove their primality.

/JeppeSN

Bur
Volunteer tester

Joined: 25 Feb 20
Posts: 511
ID: 1241833
Credit: 408,509,608
RAC: 26,999

Message 142697 - Posted: 26 Aug 2020 | 7:14:30 UTC

I suspected it might be problematic the prove their primality, but wasn't sure.

The background ist that I'm trying to find a use for a cheaper card like a 1650. From what I read here it will likely not produce any 1st. While a certain amount of double checking is of course no problem, without any 1st the search feels a bit pointless. So I thought I might use it for manual search of some more exotic primes.

Is there anything else that could be done specifically with a GPU?

dannyridel
Volunteer tester

Joined: 3 Feb 19
Posts: 966
ID: 1097922
Credit: 38,502,054
RAC: 179,264

Message 142698 - Posted: 26 Aug 2020 | 7:43:44 UTC - in response to Message 142697.

I suspected it might be problematic the prove their primality, but wasn't sure.

The background ist that I'm trying to find a use for a cheaper card like a 1650. From what I read here it will likely not produce any 1st. While a certain amount of double checking is of course no problem, without any 1st the search feels a bit pointless. So I thought I might use it for manual search of some more exotic primes.

Is there anything else that could be done specifically with a GPU?

PPS SV, AP, incoming WW. Or GFN14 which is ending soon.
____________
My lucky number is 6219*2^3374198+1

Bur
Volunteer tester

Joined: 25 Feb 20
Posts: 511
ID: 1241833
Credit: 408,509,608
RAC: 26,999

Message 142701 - Posted: 26 Aug 2020 | 12:24:23 UTC - in response to Message 142698.

I'd have preferred something that Primegrid isn't already working on, so I don't accidentally do numbers that are or will be covered.

For primes of the form b^2^n + 2 it's also not easy to prove their primality?

Scott Brown
Volunteer moderator
Volunteer tester
Project scientist

Joined: 17 Oct 05
Posts: 2329
ID: 1178
Credit: 15,603,704,502
RAC: 12,282,062

Message 142702 - Posted: 26 Aug 2020 | 12:56:55 UTC - in response to Message 142697.

The background ist that I'm trying to find a use for a cheaper card like a 1650. From what I read here it will likely not produce any 1st. While a certain amount of double checking is of course no problem, without any 1st the search feels a bit pointless. So I thought I might use it for manual search of some more exotic primes.

Is there anything else that could be done specifically with a GPU?

I think that your information isn't quite accurate. A GTX 1650 has a similar runtime to a GTX 1060 3GB card. I have a couple of those running the current AP27 project and getting a "first" rate of somewhere in the 25% to 40% range. You will also find it does well on projects like GFN15 with the shorter work and where, without some manual configuration interventions, high-end cards work very inefficiently compared to cards like the 1650. You might also try GFN17 Low--the smaller number of competing GPUs on this less popular subproject will mean a higher "first" rate for cards like the 1650.

Yves Gallot
Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 712
ID: 164101
Credit: 305,166,630
RAC: 0

Message 142705 - Posted: 26 Aug 2020 | 15:28:20 UTC - in response to Message 142701.

For primes of the form b^2^n + 2 it's also not easy to prove their primality?

No, see Finding primes & proving primality.

dannyridel
Volunteer tester

Joined: 3 Feb 19
Posts: 966
ID: 1097922
Credit: 38,502,054
RAC: 179,264

Message 142706 - Posted: 26 Aug 2020 | 15:33:22 UTC - in response to Message 142701.

I'd have preferred something that Primegrid isn't already working on, so I don't accidentally do numbers that are or will be covered.

For primes of the form b^2^n + 2 it's also not easy to prove their primality?

There really isn't much work optimized for GPUs. YOu could try searching for GIMPS with mlucas.

Aside from that, Scott is quite correct. GFN15 and 17low can be run efficiently on 1650s, the better option would be 1650Super though if you want to run AP or other PG subprojects.
____________
My lucky number is 6219*2^3374198+1

Bur
Volunteer tester

Joined: 25 Feb 20
Posts: 511
ID: 1241833
Credit: 408,509,608
RAC: 26,999

Message 142708 - Posted: 26 Aug 2020 | 16:44:53 UTC

Actually, I wanted to try some manual searching. But since I also didn't want to move a CPU away from Primegrid, I thought of buying a relatively cheap GPU and use that.

But apparently all primes that can be efficiently searched for by GPU are already covered by Primegrid... :)

One last idea, is there a GPU software for Proth primes? I couldn't find any though.

Nick

Joined: 11 Jul 11
Posts: 1955
ID: 105020
Credit: 5,790,772,213
RAC: 32,402,484

Message 142709 - Posted: 26 Aug 2020 | 17:03:43 UTC - in response to Message 142708.

One last idea, is there a GPU software for Proth primes? I couldn't find any though.

This may answer the question, or it may not (my money is on not because I am not confident of the subject to know):

Yves Gallot
Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 712
ID: 164101
Credit: 305,166,630
RAC: 0

Message 142710 - Posted: 26 Aug 2020 | 17:26:16 UTC - in response to Message 142708.

One last idea, is there a GPU software for Proth primes? I couldn't find any though.

Yes, proth20 binaries and proth20 sources.

Bur
Volunteer tester

Joined: 25 Feb 20
Posts: 511
ID: 1241833
Credit: 408,509,608
RAC: 26,999

Message 142742 - Posted: 28 Aug 2020 | 7:06:45 UTC

Nick, thanks, I forgot about that completely... :) So, LLR is a waste of GPU. But PRP testing of GFN is working with high efficiency. Can the same be applied to Proth or Riesel?

This would speed up work considerably on almost all PG subprojects.

Yves, thanks for the link, is it doing LLR or PRP? I assume LLR? Will it be possible to include a PRP test? I don't have an OpenCL card, but would certainly be willing to get one if it would help in development.

edit: Btw, I asked a similar question over at mersenneforum.org where the idea of using GPU for PRP testing came up.

Yves Gallot
Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 712
ID: 164101
Credit: 305,166,630
RAC: 0

Message 142748 - Posted: 28 Aug 2020 | 8:12:00 UTC - in response to Message 142742.

Yves, thanks for the link, is it doing LLR or PRP? I assume LLR? Will it be possible to include a PRP test?

Neither LLR nor PRP but Proth's theorem.
For numbers of the form k·2n + 1, k < 2n, Proth's test is as fast as a prp test and is a primality proof. proth20 implements this test with Gerbicz error checking.
Gerbicz algorithm doesn't work with LLR because of the -2 term. Then if you want to search for primes of the form k·2n - 1 and implement Gerbicz error checking, you must do a PRP test to eliminate composite numbers. Only the final primality proof on prp numbers will be LLR test.

Scott Brown
Volunteer moderator
Volunteer tester
Project scientist

Joined: 17 Oct 05
Posts: 2329
ID: 1178
Credit: 15,603,704,502
RAC: 12,282,062

Message 142752 - Posted: 28 Aug 2020 | 12:15:03 UTC - in response to Message 142742.

I don't have an OpenCL card, but would certainly be willing to get one if it would help in development.

Unless you have a very old GPU, almost any modern NVidia or AMD GPU will run OpenCL applications with the correct driver installed.

Bur
Volunteer tester

Joined: 25 Feb 20
Posts: 511
ID: 1241833
Credit: 408,509,608
RAC: 26,999

Message 142758 - Posted: 28 Aug 2020 | 17:00:52 UTC - in response to Message 142748.

Sorry if this is a stupid question, but it means proth20 uses OpenCL to prove primality of Proth numbers? So my plan to buy a 1650 and do both sieving and primality proof of Proth numbers with it, would work?

If so, why isn't proth20 used on PG? Or is CPU still faster and GPUs are generally better used for GFN instead of Proth?

Unless you have a very old GPU, almost any modern NVidia or AMD GPU will run OpenCL applications with the correct driver installed.
One is embedded Intel, the other had some older Radeon card that I think doesn't support OpenCL, but I'd have to check next week when I have access to the physical computer.
____________
1281979 * 2^485014 + 1 is prime ... no further hits up to: n = 5,700,000

Michael Goetz
Volunteer moderator

Joined: 21 Jan 10
Posts: 13804
ID: 53948
Credit: 345,369,032
RAC: 3,564

Message 142762 - Posted: 28 Aug 2020 | 18:45:00 UTC - in response to Message 142758.

If so, why isn't proth20 used on PG? Or is CPU still faster and GPUs are generally better used for GFN instead of Proth?

It's new. We can only do so much, and things take time.
____________
My lucky number is 75898524288+1

Bur
Volunteer tester

Joined: 25 Feb 20
Posts: 511
ID: 1241833
Credit: 408,509,608
RAC: 26,999

Message 142775 - Posted: 29 Aug 2020 | 6:57:26 UTC - in response to Message 142762.

It's new. We can only do so much, and things take time.
I didn't mean that as accusation why it takes so long. ;) I was rather wondering if there's a hidden catch.

I think I'll buy a 1650 then to try how it works out, also then I'll finally be able to efficiently collect AP, PPS SV and GFN badges. :)

____________
1281979 * 2^485014 + 1 is prime ... no further hits up to: n = 5,700,000

Message boards : Generalized Fermat Prime Search : Generalized Fermat with odd base?