Ernst's Mfactor program

[ewmayer]

Andreas, just curious what were the exponent/factor for the composite-p/98-bit-factor case you mentioned? I'd like to try that in my local int64-based build of the current code and see if it still works.

[ATH]

Originally Posted by ewmayer

Andreas, just curious what were the exponent/factor for the composite-p/98-bit-factor case you mentioned? I'd like to try that in my local int64-based build of the current code and see if it still works.

Mfactor.exe -m 478923550381407695195061911293 -kmax 100000000
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 k-max 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 0-15


Here is a 122.3 bits factor:
Mfactor.exe -m 10104654968465468549684654654563 -kmax 10000000
pass = 14.
Factor with k = 313197. Program: E3.0x

[ewmayer]

@Andreas: thanks -

OK, those exponents require P2WORD to be def'd on the command line when building factor.c ... when I try running build-from-current-sources-with-post-#2-tweaks 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 sieve-setup:

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 32-bit mod-inverse call, that is new code since v14.1 related to accelerating the sieve-setup ... 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 faster-sieve-setup code.

[ATH]

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

[ewmayer]

Originally Posted by ATH

Mfactor.exe -m 478923550381407695195061911293 -kmax 100000000
pass = 1.
Factor with k = 18608. Program: E3.0x

The exponent is 98.6 bits and the factor is 113.8 bits.

Found the bug that was hosing my v19/P2WORD run of this one ... fix will be included in next update of the v19 beta tarball, unless someone needs it sooner.

It seems the lowest k-max is 16,336,320 even if you choose a smaller value, so the exponent limit is p< 2^128 / (2*16336320)

Yes, that min-kmax is the number of bits in the small-primes sieve, we always do complete passes through it, not worth adding logic to quit early when the user's requested kmax has been hit.

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

With above-noted factor.c fix, v19 finds this as well.

If you allow composite exponents the highest one is: 10414902711288052127510192241329.
M(10414902711288052127510192241329) has 0 factors in range k = [0, 16336320], passes 0-15

"If you allow composite exponents" -- did your v14.1 build accept this without modifications, or did you disable the prime-p check? Because both v14.1 and the current version of factor.c have the same is-PRP check on p, in v14.1 at line 1017 and in v19 at line 1270, and both (I built v14.1 factor just now, just to be sure) throw the same assertion, just from those different line numbers:

Factoring self-tests 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 prime-exponent required form.

Here is a 122.3 bits factor:
Mfactor.exe -m 10104654968465468549684654654563 -kmax 10000000
pass = 14.
Factor with k = 313197. Program: E3.0x

Fixed-up v19 also finds.

[ATH]

Originally Posted by ewmayer

"If you allow composite exponents" -- did your v14.1 build accept this without modifications, or did you disable the prime-p check? Because both v14.1 and the current version of factor.c have the same is-PRP check on p, in v14.1 at line 1017 and in v19 at line 1270, and both (I built v14.1 factor just now, just to be sure) throw the same assertion, just from those different line numbers:

You showed me where to disable it, because back then I wanted to trial factor M(p^2).

[ewmayer]

Originally Posted by ATH

You showed me where to disable it, because back then I wanted to trial factor M(p^2).

Ah, it's been too long ... did you find any factors of such using your customized build?

[ATH]

I found:

M(74207281²) = M(5506720553412961)
Factor with k = 46126737231. Program: E3.0x

M(82589933²) = 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¹³:
M(86243²),M(132049²),M(216091²),M(1257787²),M(2976221²),M(6972593²),M(13466917²),M(30402457²),M(43112609²),M(57885161²),M(77232917²)


I also had a modified mfaktc build that could do M(p²), but that only worked up to M(44497²).

[ewmayer]

Originally Posted by ATH

I found:

M(74207281²) = M(5506720553412961)
Factor with k = 46126737231. Program: E3.0x

M(82589933²) = M(6821097032944489)
Factor with k = 823899. Program: E3.0x

Those were useful in my current v19-TF-code debug ... I changed the p-must-be-prime code to simply warn on odd composite p's (p must be odd is only remaining constraint):

WARNING: p = 5506720553412961 is not prime ... proceeding anyway, on presumption user wants this.

...and quickly found another sieve-setup bug, this one in the bmin/bmax bounds-setting-using-max-factor-bits 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

[ATH]

I only use -kmin and -kmax since -bmin and -bmax does not work with -DP2WORD in 14.1

ERROR: at line 768 of file factor.c
Assertion failed: bmin/bmax form of bounds-setting only allowed for single-word-p case!

Here are more lines that finds factors of M(p²) if you need to debug:

./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

This one should find 2 factors but it fails in 14.1 after the first factor:

./Mfactor -m 572805271921 -kmax 100000000
or
./Mfactor -m 572805271921 -bmax 67

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 2442: bw = 0x1ull << (i-j);
mi64.c line 2455: ASSERT(HERE, !bw, "Unexpected borrow!");

[ewmayer]

Originally Posted by ATH

This one should find 2 factors but it fails in 14.1 after the first factor:

./Mfactor -m 572805271921 -kmax 100000000
or
./Mfactor -m 572805271921 -bmax 67

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 2442: bw = 0x1ull << (i-j);
mi64.c line 2455: ASSERT(HERE, !bw, "Unexpected borrow!");

You've been holding out on me! :) I knew there was at least one remaining bug when my run-to-90-bits of M5506720553412961 completed and failed to find the factor you found using 14.1. That needed some sleuthing, the upshot of which proved to be, paraphrasing myself a few weeks ago when your build-and-generate-debug-data of the pre-release v19 code helped me find a bug in the new avx-512 assembly code needed for supporting PRP/Gerbicz-check: I did something very naughty. My modpow routines for q < 2^128 were all primarily focused on p < 2^32 and k up to 64 bits, so adding support for 64-bit p was a bit of an afterthought there, and was trivially done ... until it wasn't. Namely, several of the specialized x86_64 asm routines still used 32-bit loads, you can see which ones (in both the v14.1 and v19 code) this way:

grep __pshift *c|grep eax
grep __pshift *c|grep slq

In the case of the above missed M5506720553412961 factor, the offending routine is twopmodq96_q4() in twopmodq96.c ... but that asm-block-loop-body 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 > 32-bit). Turns out whether that intermediate-length (between 64-bit and 128-bit, i.e. 1 and 2-word 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 zero-day exploits:

The above assertion (in the quote) manifests in a slightly different way in v19 due to the accelerated-sieve-setup code in the latter, but in both cases the failure can be traced to the compositeness of the exponent. The sieve-setup was coded with prime p in mind, and there is a special-casing if() in there to the effect of "if the current small sieving prime == p, skip the remaining sieve-setup 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 factor-found testcases also succeed.)