mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2021-11-03, 23:37   #1
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

11·13·17 Posts
Default an idea to extend P-1 stage 1 to find more factors

For the first stage, the P-1 algorithm uses the highest power of each prime less than or equal to B1 when computing the product of the primes. However, this means we'll miss factors where k has a repeated factor greater than sqrt(B1).

102646067 and 105144859 are two examples with such factors. P-1 cannot normally find these without the now-unsupported Brent-Suyama extension. So my idea is to add an option to increase the power of each prime by 1 (or more) up to a percentage of the given value. For example, B1=1000000+50000 means that we do the first stage as normal, and then multiply E (or m) again by each prime up to 50000.

I just don't know how successful this method may be as there is no data on how many known factors there are where k has a repeated factor greater than the square root of the suggested B1 value. James could probably run some database queries on his website and find out for us.

Last fiddled with by ixfd64 on 2021-11-03 at 23:44
ixfd64 is offline   Reply With Quote
Old 2021-11-04, 03:19   #2
axn
 
axn's Avatar
 
Jun 2003

34×5×13 Posts
Default

It is not worth it. You're better off just adding new primes into B1 (i.e. extend B1).
axn is offline   Reply With Quote
Old 2021-11-04, 04:27   #3
Zhangrc
 
"University student"
May 2021
Beijing, China

110001012 Posts
Default

It's not worth it, and now people are suggesting to use smaller bounds for P-1 (1 test saved if a factor is found, or B1=400000 B2=1800000) to eliminate exponents as quickly as possible.

Last fiddled with by Zhangrc on 2021-11-04 at 04:27
Zhangrc is offline   Reply With Quote
Old 2021-11-04, 09:26   #4
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

53×11 Posts
Default

Quote:
Originally Posted by Zhangrc View Post
It's not worth it, and now people are suggesting to use smaller bounds for P-1 (1 test saved if a factor is found, or B1=400000 B2=1800000) to eliminate exponents as quickly as possible.
P-1 only "eliminates" an exponent if a factor is found.

I suggest using bounds of at least B1=1M,B2=20M. (I use B1=3M and B2=60M myself).
preda is offline   Reply With Quote
Old 2021-11-04, 13:54   #5
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2×3,049 Posts
Default

Quote:
Originally Posted by preda View Post
P-1 only "eliminates" an exponent if a factor is found.

I suggest using bounds of at least B1=1M,B2=20M. (I use B1=3M and B2=60M myself).
P-1 completion to above modest bounds eliminates a primality test or more than one if a factor is found. If a factor is not found, and bounds sufficient for the server's threshold were used, it eliminates the P-1 phase of testing an exponent. If bounds were so low they did not meet the server's threshold, and no factor was found, P-1 will be assigned again on the same exponent (unless a primality test is reported in first I think).

The bounds stated may be ok for Gpuowl 7.x, with its innovative dual-use of singly-computed powers of 3, for both P-1 stage 1 and PRP performed together, but not other software, or earlier versions of Gpuowl, for which those bounds likely cost more total computing time than skipping P-1 entirely on the exponent. See https://mersenneforum.org/showpost.p...07&postcount=3 for a prime95 test & analysis vs. # of tests-saved. Current # of tests saved on average appears to be ~1.048 at ~107M.

Last fiddled with by kriesel on 2021-11-04 at 14:04
kriesel is online now   Reply With Quote
Old 2021-11-04, 17:16   #6
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

27738 Posts
Default

Quote:
Originally Posted by axn View Post
It is not worth it. You're better off just adding new primes into B1 (i.e. extend B1).
Quote:
Originally Posted by Zhangrc View Post
It's not worth it
Today multiple times I felt the same, but currently I think that this is a working idea, even in P+1/ecm ! Would give a tiny speedup. Let me check my suggestion.
In the general way: for a given T=prod(q_i) exponent the effective score=log2(T)/sum(1/q_i), where smaller score is better.
Since this is a 1st stage idea, let B=B1.

What you all forget that if you include q^e for a possible extended 1st stage in (B,B'), then the extra effort for q^e in (B,B') means only a q-th exponentiation in the method [because in any case you'd process q^(e-1) in the usual way because q^(e-1)<B], and not q^e-th exponentiation, but gives you the largish 1/q>1/B' probability to find a divisor with the P-1 method.

My suggestion is to use B'=2*B, in fact a slightly smaller.
To convince you quickly:

The effective score=log2(T)/sum(1/q^e), where T is the exponent.
You stopped at B, and at that point you've score=log2(B)*B=besteff.

Include all primepowers, but not primes from the (B,2*B) interval, so choose B'=2*B.

For a single primepower the effective score is at most log2(sqrt(2*B))*2*B=0.5*(log2(B)+0.5)*2*B=
=(log2(B)+0.5)*B, almost good, there is a fractional error bit. So shrink it a little:

For a fixed B choose B'=c*B (where c depends on B and e!), then

log2(sqrt(c*B))*c*B=0.5*(log2(B)+log2(c))*c*B<log2(B)*B=besteff for any c<2 if B is "large".

In general the best bound for fixed B and e>1 let B'=U, at an equal effective score you would see:

log2(U^(1/e))*U=log2(B)*B or the same
log(U)*U/e=log(B)*B, because you can change to natural logarithm (and here e>1 is an integer).

Example: for B=10^5 and e=2 this gives U=189482 (as expected close to 2*B for e=2), if we use this same bound
for all e>1 in (B,U) then:

log2(T)=1062.02 (used the product of primepowers's core part).
sum(1/q^e)=0.000954325
and effective score=1112854.2 what is smaller than the base score:
log2(B)*B=1660964.05

ps. as said for e>2 you have to use an even larger bound, and that could be higher than 2*B, so for smallish
primes you have to include more primes, q^2 or more, the analysis is still correct, because in these
cases the algorithm picked up the smaller primepower for a smaller e'<e integer.
R. Gerbicz is offline   Reply With Quote
Old 2021-11-04, 18:09   #7
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

27738 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
Example: for B=10^5 and e=2 this gives U=189482 (as expected close to 2*B for e=2), if we use this same bound
for all e>1 in (B,U) then:

log2(T)=1062.02 (used the product of primepowers's core part).
sum(1/q^e)=0.000954325
and effective score=1112854.2 what is smaller than the base score:
log2(B)*B=1660964.05
correction:
log2(T)=187.0
sum(1/q^e)=0.00018
and effective score=995837.4 what is smaller than the base score:
log2(B)*B=1660964.05
R. Gerbicz is offline   Reply With Quote
Old 2021-11-05, 08:02   #8
axn
 
axn's Avatar
 
Jun 2003

34·5·13 Posts
Default

Does this look right?

Code:
merit(p, n) = log(p) * (p-1) * p^(n-1);
find_count(p, t)=my(m); for(i=2, oo, m=merit(p, i); if(m > t, return(i-1)));
old_find_count(p, B1)=floor(log(B1)/log(p));

B1 = 1000000; last_prime = precprime(B1); target_merit = merit(last_prime, 1);
forprime(p=2, last_prime, c = find_count(p, target_merit); print(p, ":", c, ":", old_find_count(p, B1)); if(c == 1, break()))
Code:
2:25:19
3:15:12
5:10:8
7:8:7
11:6:5
13:6:5
17:5:4
19:5:4
23:4:4
29:4:4
31:4:4
37:4:3
41:4:3
43:4:3
47:3:3
53:3:3
59:3:3
61:3:3
67:3:3
71:3:3
73:3:3
79:3:3
83:3:3
89:3:3
97:3:3
101:3:2
103:3:2
107:3:2
109:3:2
113:3:2
127:3:2
131:3:2
137:3:2
139:3:2
149:2:2
151:2:2
157:2:2
163:2:2
167:2:2
173:2:2
179:2:2
181:2:2
191:2:2
193:2:2
197:2:2
199:2:2
211:2:2
223:2:2
227:2:2
229:2:2
233:2:2
239:2:2
241:2:2
251:2:2
257:2:2
263:2:2
269:2:2
271:2:2
277:2:2
281:2:2
283:2:2
293:2:2
307:2:2
311:2:2
313:2:2
317:2:2
331:2:2
337:2:2
347:2:2
349:2:2
353:2:2
359:2:2
367:2:2
373:2:2
379:2:2
383:2:2
389:2:2
397:2:2
401:2:2
409:2:2
419:2:2
421:2:2
431:2:2
433:2:2
439:2:2
443:2:2
449:2:2
457:2:2
461:2:2
463:2:2
467:2:2
479:2:2
487:2:2
491:2:2
499:2:2
503:2:2
509:2:2
521:2:2
523:2:2
541:2:2
547:2:2
557:2:2
563:2:2
569:2:2
571:2:2
577:2:2
587:2:2
593:2:2
599:2:2
601:2:2
607:2:2
613:2:2
617:2:2
619:2:2
631:2:2
641:2:2
643:2:2
647:2:2
653:2:2
659:2:2
661:2:2
673:2:2
677:2:2
683:2:2
691:2:2
701:2:2
709:2:2
719:2:2
727:2:2
733:2:2
739:2:2
743:2:2
751:2:2
757:2:2
761:2:2
769:2:2
773:2:2
787:2:2
797:2:2
809:2:2
811:2:2
821:2:2
823:2:2
827:2:2
829:2:2
839:2:2
853:2:2
857:2:2
859:2:2
863:2:2
877:2:2
881:2:2
883:2:2
887:2:2
907:2:2
911:2:2
919:2:2
929:2:2
937:2:2
941:2:2
947:2:2
953:2:2
967:2:2
971:2:2
977:2:2
983:2:2
991:2:2
997:2:2
1009:2:1
1013:2:1
1019:2:1
1021:2:1
1031:2:1
1033:2:1
1039:2:1
1049:2:1
1051:2:1
1061:2:1
1063:2:1
1069:2:1
1087:2:1
1091:2:1
1093:2:1
1097:2:1
1103:2:1
1109:2:1
1117:2:1
1123:2:1
1129:2:1
1151:2:1
1153:2:1
1163:2:1
1171:2:1
1181:2:1
1187:2:1
1193:2:1
1201:2:1
1213:2:1
1217:2:1
1223:2:1
1229:2:1
1231:2:1
1237:2:1
1249:2:1
1259:2:1
1277:2:1
1279:2:1
1283:2:1
1289:2:1
1291:2:1
1297:2:1
1301:2:1
1303:2:1
1307:2:1
1319:2:1
1321:2:1
1327:2:1
1361:2:1
1367:2:1
1373:2:1
1381:2:1
1399:1:1
axn is offline   Reply With Quote
Old 2021-11-06, 15:54   #9
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

27738 Posts
Default

Quote:
Originally Posted by axn View Post
Does this look right?
I'm not sure what your code is doing, anyway, for a fixed B bound and e>1, solve the
x*log(x)/e=B*log(B)
equation, say binary search is fine since x*log(x) is monotone increasing (on [exp(-1),inf) interval ).
And put all q^e (for q prime) to the smooth set, where q is in the [B,U] interval, and U is the solution of the above equation.

You could argue that smooth number's factors is not that random, and that is true, say more than half of them is even.
So ran some tests, that is in some way deeper and at once lighter.

General method let the antique pm1 way, and the improved is the improved.
Since we want a comparison we have to adjust the B limit, lowering that in such a way that the exponent will be smaller, but we find more smooth numbers.

Let B=1000, but for simplicity we use the same U bound for all e>1, the algorithm will include 1024,1331,1369,1681 [these are 2^10, 11^3, 37^2, 41^2] and exclude 991 and 997.
Here 2*11*37*41<991*997 gives that the exponent is smaller what used in the general method.
In the [1e13,2e13] interval with a simple backtracking it is possible to find all smooth numbers (for these 2 methods)
The general method found 12988813875 smooth numbers.
The improved found 13058081975 smooth numbers, so slightly more.

You could say that the included 2^10 was the booster, so repeat the search for B=1024 (here B is included in the set), the method will include 1331,1369,1681,1849 [these are 11^3, 37^2, 41^2, 43^2] and exclude 1019 and 1021. [Notice that in this case, basically 1024 would be also dropped out due to the smaller B limit, but ofcourse the improved method would pick up it, in other words: you would drop out some non-primes also, but all of those will reappear in the set.]
Again 11*37*41*43<1019*1021, so the exponent is smaller.
The general method found 13691324851 smooth numbers.
The improved found 13809957083 smooth numbers, slightly more.

In both cases we got a roughly ~0.5% gain over the general method using primepowers out of order. [the gain is smaller for larger B !]

ps. you could still say that this is not a fair test, because p-1 is even for p>2, so it won't be a random smooth number. But it is proven that for any M the p mod M is equally distributed in the mod M reduced residue classes.

Last fiddled with by R. Gerbicz on 2021-11-06 at 16:15
R. Gerbicz is offline   Reply With Quote
Old 2021-11-22, 14:57   #10
axn
 
axn's Avatar
 
Jun 2003

149116 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
I'm not sure what your code is doing
Sorry, I meant to reply to this earlier but somehow slipped my mind.

Anyway, the code computes a cost function of including p^n in the product. It is basically log(p) (i.e proportional to the bits) / probability of p^n dividing a random P-1. i.e. more bits = costlier. Less probable = less useful. This comes out as log(p) * (p-1) * p^(n-1) -> what I call as the merit function.

The code then finds the largest n for each p such that merit(p^n) doesn't exceed the target merit, which is just the cost for a single instance of the largest prime under B1. For comparison, it also prints the count as per the regular method.

Last fiddled with by axn on 2021-11-22 at 14:57
axn is offline   Reply With Quote
Old 2021-11-23, 02:11   #11
tuckerkao
 
"Tucker Kao"
Jan 2020
Head Base M168202123

25×3×7 Posts
Default

Quote:
Originally Posted by ixfd64 View Post
102646067 and 105144859 are two examples with such factors. P-1 cannot normally find these without the now-unsupported Brent-Suyama extension.
Do these type of factors show up with the chance of 1% or more? If not, then the extra time spent may not worth the additional factors found in the long run. The P-1 stages were sped up after Prime95 v30.5, so the larger bounds become more possible for the newer PCs.
tuckerkao is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
How to use PP1 method to find factors? Miszka PrimeNet 2 2021-04-24 08:36
Find factors for non base2 candidates pepi37 GMP-ECM 2 2017-03-07 20:13
Best Way to find large factors mahnouman Information & Answers 19 2013-02-22 06:11
new idea on an older one just can't find thread science_man_88 Miscellaneous Math 2 2011-01-01 18:18
How to find factors I found with TF? edorajh PrimeNet 3 2004-10-01 19:16

All times are UTC. The time now is 23:16.


Wed Jan 19 23:16:05 UTC 2022 up 180 days, 17:45, 0 users, load averages: 1.65, 1.43, 1.38

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔