20191209, 21:37  #12 
∂^{2}ω=0
Sep 2002
República de California
11,743 Posts 
Andreas, just curious what were the exponent/factor for the compositep/98bitfactor case you mentioned? I'd like to try that in my local int64based build of the current code and see if it still works.

20191209, 23:18  #13  
Einyen
Dec 2003
Denmark
2^{3}·3^{2}·47 Posts 
Quote:
pass = 1. Factor with k = 18608. Program: E3.0x The exponent is 98.6 bits and the factor is 113.8 bits. It seems the lowest kmax is 16,336,320 even if you choose a smaller value, so the exponent limit is p< 2^128 / (2*16336320) The highest prime below that value is: Mfactor.exe m 10414902711288052127510192241307 kmax 10000000 pass = 1. Factor with k = 3668. Program: E3.0x Exponent 103.0 bits and factor 115.9 bits If you allow composite exponents the highest one is: 10414902711288052127510192241329. M(10414902711288052127510192241329) has 0 factors in range k = [0, 16336320], passes 015 Here is a 122.3 bits factor: Mfactor.exe m 10104654968465468549684654654563 kmax 10000000 pass = 14. Factor with k = 313197. Program: E3.0x Last fiddled with by ATH on 20191209 at 23:23 

20191210, 04:08  #14 
∂^{2}ω=0
Sep 2002
República de California
11,743 Posts 
@Andreas: thanks 
OK, those exponents require P2WORD to be def'd on the command line when building factor.c ... when I try running buildfromcurrentsourceswithpost#2tweaks I get the expected "p too large  limit is 50 bits." assertion. I grepped the 14.1 factor.c source and see that preprocessor flag is also used there, so perhaps you used it and forgot? Do you still have your 14.1 sources? Built a 2nd binary wih that flag on, code now accepts the inputs but then fails in sievesetup: max sieving prime = 2750161 Searching in the interval k=[0, 114354240] Each of 16 (p mod 60) passes will consist of 7 intervals of length 272272 2949120 ones bits of 16336320 in master sieve template. TRYQ = 4, max sieving prime = 2750161 Time to set up sieve = 00:00:00.113 pass = 0ERROR: eGCD called with zero input: x = 0, y = 23 ERROR: at line 4219 of file ../util.c That eGCD is result of a 32bit modinverse call, that is new code since v14.1 related to accelerating the sievesetup ... need to look into this further tomorrow, hopefully nothing overly difficult to fix. Always good to shake out the cobwebs! 478923550381407695195061911293 is prime so it's not anything related to compositeness of the exponent ... I suspect the size of the exponent is breaking some assumption in the fastersievesetup code. 
20191210, 13:35  #15 
Einyen
Dec 2003
Denmark
2^{3}×3^{2}×47 Posts 
Yes, I use DP2WORD, I forgot that was a special option, I just used the guide to compiling 14.1 you sent me back then.
gcc c Wall O3 mavx2 DUSE_AVX2 DFACTOR_STANDALONE DTRYQ=4 DP2WORD DUSE_THREADS factor.c Last fiddled with by ATH on 20191210 at 13:35 
20191210, 22:15  #16  
∂^{2}ω=0
Sep 2002
República de California
11,743 Posts 
Quote:
Quote:
Quote:
Quote:
Factoring selftests completed successfully. p is not prime! Offending p = 10414902711288052127510192241329 ERROR: at line 1273 of file ../factor.c Assertion failed: 0 If you disabled that check yourself, that's fine, as long as you're OK with just looking for that subset of factors which are of the primeexponent required form. Quote:


20191211, 00:47  #17  
Einyen
Dec 2003
Denmark
110100111000_{2} Posts 
Quote:


20191211, 02:52  #18 
∂^{2}ω=0
Sep 2002
República de California
11,743 Posts 

20191211, 18:38  #19 
Einyen
Dec 2003
Denmark
110100111000_{2} Posts 
I found:
M(74207281^{2}) = M(5506720553412961) Factor with k = 46126737231. Program: E3.0x M(82589933^{2}) = M(6821097032944489) Factor with k = 823899. Program: E3.0x The rest of the known factors are small, I found them with my own GMP code before I got Mfactor. But I trial factorered the remaining exponent without any factors to slightly above k=2*10^{13}: M(86243^{2}),M(132049^{2}),M(216091^{2}),M(1257787^{2}),M(2976221^{2}),M(6972593^{2}),M(13466917^{2}),M(30402457^{2}),M(43112609^{2}),M(57885161^{2}),M(77232917^{2}) I also had a modified mfaktc build that could do M(p^{2}), but that only worked up to M(44497^{2}). Last fiddled with by ATH on 20191211 at 18:41 
20191211, 21:30  #20  
∂^{2}ω=0
Sep 2002
República de California
11,743 Posts 
Quote:
WARNING: p = 5506720553412961 is not prime ... proceeding anyway, on presumption user wants this. ...and quickly found another sievesetup bug, this one in the bmin/bmax boundssettingusingmaxfactorbits option. I see the v14.1 code also supports this  what happens in your build of that if you try the following set of inputs? ./Mfactor m 5506720553412961 bmax 90 

20191211, 22:58  #21 
Einyen
Dec 2003
Denmark
3384_{10} Posts 
I only use kmin and kmax since bmin and bmax does not work with DP2WORD in 14.1
Code:
ERROR: at line 768 of file factor.c Assertion failed: bmin/bmax form of boundssetting only allowed for singlewordp case! Here are more lines that finds factors of M(p^{2}) if you need to debug: Code:
./Mfactor m 1818493763727601 kmax 10000000 or ./Mfactor m 1818493763727601 bmax 75 ./Mfactor m 1380617902548889 kmax 30000000 or ./Mfactor m 1380617902548889 bmax 76 ./Mfactor m 1061629537179649 kmax 10000000 or ./Mfactor m 1061629537179649 bmax 74 ./Mfactor m 577757322315889 kmax 10000000 or ./Mfactor m 577757322315889 bmax 73 ./Mfactor m 93876721 kmin 408000000000 kmax 409000000000 or ./Mfactor m 93876721 bmin 66 bmax 67 ./Mfactor m 572805271921 kmax 100000000 or ./Mfactor m 572805271921 bmax 67 Code:
Time to set up sieve = 00:00:00.190 pass = 0. pass = 1. Factor with k = 608. Program: E3.0x ERROR: at line 2455 of file mi64.c Assertion failed: Unexpected borrow! mi64.c line 2455: ASSERT(HERE, !bw, "Unexpected borrow!"); Last fiddled with by ATH on 20191211 at 23:24 
20191214, 21:44  #22  
∂^{2}ω=0
Sep 2002
República de California
26737_{8} Posts 
Quote:
grep __pshift *cgrep eax grep __pshift *cgrep slq In the case of the above missed M5506720553412961 factor, the offending routine is twopmodq96_q4() in twopmodq96.c ... but that asmblockloopbody routine is also present in 14.1, so that left me puzzled as to why your run found said factor (and any similar case with p > 32bit). Turns out whether that intermediatelength (between 64bit and 128bit, i.e. 1 and 2word q) modpow routine gets used depends on whether the preprocessor flag USE_128x96 is set, and said flag is off by default in v14.1 but enabled by default in v19. Mystery solved. Now to your other hoarded zeroday exploits: The above assertion (in the quote) manifests in a slightly different way in v19 due to the acceleratedsievesetup code in the latter, but in both cases the failure can be traced to the compositeness of the exponent. The sievesetup was coded with prime p in mind, and there is a specialcasing if() in there to the effect of "if the current small sieving prime == p, skip the remaining sievesetup and proceed to the next small prime". To properly handle composite exponents n it needs to be modified to "if the current small sieving prime divides n...", specifically when we hit small prime 756839, since 572805271921 = 756839^2. With that, it finds both small factors, k = 608 and k = 55568048. (And all of your other factorfound testcases also succeed.) 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Official Ernst (ewmayer) / Richard (cheesehead) feud thread  cheesehead  Soap Box  50  20140630 01:06 
Official "Ernst is a deceiving bully and George is a meanie" thread  cheesehead  Soap Box  61  20130611 04:30 
Running Mfactor  M0CZY  LMH > 100M  2  20110223 11:48 
Mfactor sieve code thread  ewmayer  Operation Billion Digits  27  20061103 08:05 
which program?  drakkar67  Prime Sierpinski Project  14  20051129 06:25 