mersenneforum.org  

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

Reply
 
Thread Tools
Old 2019-12-09, 21:37   #12
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

3×53×31 Posts
Default

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.
ewmayer is offline   Reply With Quote
Old 2019-12-09, 23:18   #13
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

307410 Posts
Default

Quote:
Originally Posted by ewmayer View Post
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

Last fiddled with by ATH on 2019-12-09 at 23:23
ATH is online now   Reply With Quote
Old 2019-12-10, 04:08   #14
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

3·53·31 Posts
Default

@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.
ewmayer is offline   Reply With Quote
Old 2019-12-10, 13:35   #15
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2×29×53 Posts
Default

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 2019-12-10 at 13:35
ATH is online now   Reply With Quote
Old 2019-12-10, 22:15   #16
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

3·53·31 Posts
Default

Quote:
Originally Posted by ATH View Post
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.

Quote:
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.
Quote:
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.

Quote:
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.
Quote:
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.
ewmayer is offline   Reply With Quote
Old 2019-12-11, 00:47   #17
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2×29×53 Posts
Default

Quote:
Originally Posted by ewmayer View Post
"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).
ATH is online now   Reply With Quote
Old 2019-12-11, 02:52   #18
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

3×53×31 Posts
Default

Quote:
Originally Posted by ATH View Post
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?
ewmayer is offline   Reply With Quote
Old 2019-12-11, 18:38   #19
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

60028 Posts
Default

I found:

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

M(825899332) = 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*1013:
M(862432),M(1320492),M(2160912),M(12577872),M(29762212),M(69725932),M(134669172),M(304024572),M(431126092),M(578851612),M(772329172)


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

Last fiddled with by ATH on 2019-12-11 at 18:41
ATH is online now   Reply With Quote
Old 2019-12-11, 21:30   #20
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

265518 Posts
Default

Quote:
Originally Posted by ATH View Post
I found:

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

M(825899332) = 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
ewmayer is offline   Reply With Quote
Old 2019-12-11, 22:58   #21
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2·29·53 Posts
Default

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 bounds-setting only allowed for single-word-p case!



Here are more lines that finds factors of M(p2) 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
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

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

Last fiddled with by ATH on 2019-12-11 at 23:24
ATH is online now   Reply With Quote
Old 2019-12-14, 21:44   #22
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

101101011010012 Posts
Default

Quote:
Originally Posted by ATH View Post
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

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 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.)
ewmayer is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Official Ernst (ewmayer) / Richard (cheesehead) feud thread cheesehead Soap Box 50 2014-06-30 01:06
Official "Ernst is a deceiving bully and George is a meanie" thread cheesehead Soap Box 61 2013-06-11 04:30
Running Mfactor M0CZY LMH > 100M 2 2011-02-23 11:48
Mfactor sieve code thread ewmayer Operation Billion Digits 27 2006-11-03 08:05
which program? drakkar67 Prime Sierpinski Project 14 2005-11-29 06:25

All times are UTC. The time now is 06:17.

Thu Apr 15 06:17:52 UTC 2021 up 7 days, 58 mins, 0 users, load averages: 1.86, 1.98, 1.84

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.