"Divides Phi" category

Batalov · 2014-09-27, 03:02

This is an interesting category, and Keller, Broadhurst and others submitted many such primes. The test for it is implemented in the old Y.Gallot's Proth.exe (the newest executable is >10 years old but it runs; its SSE2 code emits an error on modern CPUs, so this can be disabled in 'Options').

Because there is no detailed page for the properties of such numbers, I took a sheet of paper and sat for an hour pondering.

Ok, what do we know?
1. Candidates can be primes p = 2q^n+1 with prime q.
2. q ≡ 11 (mod 12) is a well known requirement. (Proof is left to the reader. :wink-wink: ... Seriously though, there probably exists a paper from Keller and probably as early as from 70s)
3. n is odd.
4. $Phi(q^n,2) = {{2^{q^n} -1} \over {2^{q^{n-1}} -1}}$ , so we need 2^q^n ≡ 1 (mod p) but 2^q^{n-1} $\ne$ 1 (mod p)

UTM database carries some more exotic examples: with k>2 (then q is not restricted to 11 (mod 12) and n is not only odd) or with k*q^n+1 | Phi(q^m,2), where m != n.

This category sieves well with sr1sieve (cannot combine multiple bases into one workunit for sr2sieve) and tests with LLR. Final check can be done with the old Proth.exe or with modified LLR (with 2^q $\ne$ 1 (mod p) added test).
_____________________
2 · 10859^87905 + 1 and 2 · 11171^100961+1 are found and are under final check with Proth.exe (this is quite slow)... Both checks finished: both divide Phi(q^n,2).

Batalov · 2014-09-27, 17:53

Keller (with Ingo Buechel) once reported to have searched k=2 for bases 383 (limit 433k), 467 (347k; a prime found in 2006!), 647 (322k), 947 (105k), 67607 (412k !!). These series have no known primes.

These efforts could be of some interest to CRUS; I've seen these values still outstanding when I scanned their status yesterday.

paulunderwood · 2014-09-27, 20:45

http://primes.utm.edu/primes/page.php?id=118560 does not appear on http://primes.utm.edu/top20/page.php?id=37

EDIT: it does now. C.C. was away for a day.

Batalov · 2014-09-27, 21:04

All of these initial labels get manually promoted by C. "The Prime Mogul " C.

Or 'demoted' as the case may be for "Divides xGF(n,a,b)!!!!" that get automatically submitted by the PrimeGrid's engine.

It's the weekend.

P.S. There's another one!

paulunderwood · 2014-09-27, 21:15

Quote:

Originally Posted by Batalov

P.S. There's another one!

Congrats. Are you going for #1?

Citrix · 2014-09-27, 21:53

Quote:

Originally Posted by Batalov

Keller (with Ingo Buechel) once reported to have searched k=2 for bases 383 (limit 433k), 467 (347k; a prime found in 2006!), 647 (322k), 947 (105k), 67607 (412k !!). These series have no known primes.

These efforts could be of some interest to CRUS; I've seen these values still outstanding when I scanned their status yesterday.

You might be interested in http://www.mersenneforum.org/showthr...t=10354&page=3 (This is an extremely big project to work on:( )

Also there used to be a project to search 2*a^a+1....everything under 40k was tested.

Batalov · 2014-09-28, 01:52

Quote:

Originally Posted by paulunderwood

Congrats. Are you going for #1?

Certainly.

But this time with a proof of Dividing Phi first, and submitting second. It should show up in the top in about two hours, with overall rank ~271.

paulunderwood · 2014-09-28, 06:29

Congrats again, this time for 681817 digits

Batalov · 2014-10-03, 19:32

I have modded LLR to run a naively refactored order-of-2-mod p test instead of Proth.exe (and even though naive, this is a fast solution; as fast as the primality test, 1-2 hr max; this is what I used for the current top1 and top3; Proth.exe would have taken cpu-days).

I've scanned all known 155 current and former "Divides Phi" categorized Proth primes and they, of course, all confirmed. After that validity test, I moved on to the untagged prime and composite base q Proth numbers (Proth.exe does not run the order-of-2 test on them), and found half a dozen interesting divisors. The largest of them is Ian's CRUS S695 prime with k=2, and it was large enough to enter the top20.

While the initial identification of such numbers is routine (we can check that 2^(q^n) ≡ 1 (mod k*q^n+1)), the determination of exact Phi() that they divide is more cumbersome than with prime q's. One has to divide away all prime factors of q separately and together until 2^(q^n/factors) !≡ 1. For this particular number, 695 = 5 * 139 and while 2^(q^n/139) already !≡ 1, 2^(q^n/5^k) ≡ 1 for 0<=k<=4 and not for k=5. Hence, as reported, "Divides Phi(695^94625/5^4,2)".

paulunderwood · 2014-10-10, 15:34

Congrats yet again, this time for a megaprime: 2 * 59^608685 + 1

Batalov · 2014-10-10, 18:25

Thanks.

Of course a prime q=383, 647, 947 or 67607 (no known primes) would have been so much nicer, but after quite a bit of time spent on them nothing yet was found. So, a small fishing expedition was sent out to small q's - even though they have known primes, they are much faster (this is a short version of a long story; 67607, unfortunately is "generic FFT" only, which is very significantly slower).

2014-09-27, 17:53	#2
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2·13·359 Posts	Keller (with Ingo Buechel) once reported to have searched k=2 for bases 383 (limit 433k), 467 (347k; a prime found in 2006!), 647 (322k), 947 (105k), 67607 (412k !!). These series have no known primes. These efforts could be of some interest to CRUS; I've seen these values still outstanding when I scanned their status yesterday. Last fiddled with by Batalov on 2014-09-27 at 18:29 Reason: fixed a typo (in the quoted message)

2014-09-27, 20:45	#3
paulunderwood Sep 2002 Database er0rr 2·7·257 Posts	http://primes.utm.edu/primes/page.php?id=118560 does not appear on http://primes.utm.edu/top20/page.php?id=37 EDIT: it does now. C.C. was away for a day. Last fiddled with by Batalov on 2014-09-29 at 17:28 Reason: (official comment was updated)

2014-10-03, 19:32	#9
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2·13·359 Posts	the order-of-2 (mod p) test I have modded LLR to run a naively refactored order-of-2-mod p test instead of Proth.exe (and even though naive, this is a fast solution; as fast as the primality test, 1-2 hr max; this is what I used for the current top1 and top3; Proth.exe would have taken cpu-days). I've scanned all known 155 current and former "Divides Phi" categorized Proth primes and they, of course, all confirmed. After that validity test, I moved on to the untagged prime and composite base q Proth numbers (Proth.exe does not run the order-of-2 test on them), and found half a dozen interesting divisors. The largest of them is Ian's CRUS S695 prime with k=2, and it was large enough to enter the top20. While the initial identification of such numbers is routine (we can check that 2^(q^n) ≡ 1 (mod kq^n+1)), the determination of exact Phi() that they divide is more cumbersome than with prime q's. One has to divide away all prime factors of q separately and together until 2^(q^n/factors) !≡ 1. For this particular number, 695 = 5 139 and while 2^(q^n/139) already !≡ 1, 2^(q^n/5^k) ≡ 1 for 0<=k<=4 and not for k=5. Hence, as reported, "Divides Phi(695^94625/5^4,2)".

2014-10-10, 15:34	#10
paulunderwood Sep 2002 Database er0rr 2·7·257 Posts	Congrats yet again, this time for a megaprime: 2 * 59^608685 + 1 Last fiddled with by paulunderwood on 2014-10-10 at 15:34

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Any fast paths out of Category 3 purgatory	NookieN	PrimeNet	9	2018-06-18 19:14
Option to prefer higher category work?	Runtime Error	PrimeNet	4	2018-01-07 20:20
646730219521 Divides F19	Buckle	Factoring	7	2010-03-29 22:56
p^n - 1 divides p^m - 1 ==> n divides m	jinydu	Homework Help	10	2008-08-06 19:17

2014-09-27, 03:02	#1
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2×13×359 Posts	"Divides Phi" category This is an interesting category, and Keller, Broadhurst and others submitted many such primes. The test for it is implemented in the old Y.Gallot's Proth.exe (the newest executable is >10 years old but it runs; its SSE2 code emits an error on modern CPUs, so this can be disabled in 'Options'). Because there is no detailed page for the properties of such numbers, I took a sheet of paper and sat for an hour pondering. Ok, what do we know? 1. Candidates can be primes p = 2q^n+1 with prime q. 2. q ≡ 11 (mod 12) is a well known requirement. (Proof is left to the reader. :wink-wink: ... Seriously though, there probably exists a paper from Keller and probably as early as from 70s) 3. n is odd. 4. $Phi(q^n,2) = {{2^{q^n} -1} \over {2^{q^{n-1}} -1}}$ , so we need 2^q^n ≡ 1 (mod p) but 2^q^{n-1} $\ne$ 1 (mod p) UTM database carries some more exotic examples: with k>2 (then q is not restricted to 11 (mod 12) and n is not only odd) or with kq^n+1 \| Phi(q^m,2), where m != n. This category sieves well with sr1sieve (cannot combine multiple bases into one workunit for sr2sieve) and tests with LLR. Final check can be done with the old Proth.exe or with modified LLR (with 2^q $\ne$ 1 (mod p) added test). _____________________ 2 · 10859^87905 + 1 and 2 · 11171^100961+1 are found and are under final check with Proth.exe (this is quite slow)... Both checks finished: both divide Phi(q^n,2). Last fiddled with by Batalov on 2014-09-27 at 17:54 Reason: some fluff removed*

2014-09-27, 21:04	#4
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2·13·359 Posts	All of these initial labels get manually promoted by C. "The Prime Mogul " C. Or 'demoted' as the case may be for "Divides xGF(n,a,b)!!!!" that get automatically submitted by the PrimeGrid's engine. It's the weekend. P.S. There's another one!

2014-09-28, 06:29	#8
paulunderwood Sep 2002 Database er0rr 2×7×257 Posts	Congrats again, this time for 681817 digits

2014-10-10, 18:25	#11
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 9334₁₀ Posts	Thanks. Of course a prime q=383, 647, 947 or 67607 (no known primes) would have been so much nicer, but after quite a bit of time spent on them nothing yet was found. So, a small fishing expedition was sent out to small q's - even though they have known primes, they are much faster (this is a short version of a long story; 67607, unfortunately is "generic FFT" only, which is very significantly slower).