mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Lounge (https://www.mersenneforum.org/forumdisplay.php?f=7)
-   -   3^10000+2 is composite (https://www.mersenneforum.org/showthread.php?t=18419)

 davar55 2013-08-04 11:43

3^10000+2 is composite

Testing my integer calculator, I tried factoring 3^10000+2,
a 4772 digit integer of previously unknown status.
No small ( <= 2099963) factors found.
Then the PRP tester kicked in.
Eventually (not too long), it reported COMPOSITE.

I checked with factordb.
Its smallest prmie factor is 8099873.

(This post probably belongs outside the LOUNGE.)

 f1pokerspeed 2013-08-04 12:28

So, what functionality does your integer calculator have? I assume that with your PRP test and trial division that it's within the realms of a mini prime test-suite.

Unless your method for trial division is very slow, maybe you should increase the limits of the process to save you having to perform the PRP test on the number.

 davar55 2013-08-04 23:13

[QUOTE]So, what functionality does your integer calculator have? I assume that with your PRP test and trial division that it's within the realms of a mini prime test-suite.
Unless your method for trial division is very slow, maybe you should increase the limits of the process to save you having to perform the PRP test on the number.[/QUOTE]In addition to the four basic operations, it can exponentiate, take
nth roots (rounded down), take integral logarithms to a positive
integral base > 1 (rounding down), compute factorials and nCk and
nPk, gcd, generate some long random numbers, and about a dozen
more simple number theoretic functions. It can factor small numbers
( <= 4.21 trillion ) and tries to PRP the last factor left over. It has
a Mersenne tester, but since the data representation is integer, it
runs much slower than a float-based similar program.

I'm still tweaking it. The current limit is 1 million bytes of
representation of an integer, which gives approximately
2.42 million decimal digits. At least it should; I haven't tried
multiplying a pair of million digit numbers yet. The startup
prime generator computes and stores primes <= 2099963,
and I'm still adjusting this parameter (you know the reasons

 davar55 2013-08-16 11:52

I checked with faactordb.

The factorization of 3^10000+2 is currently:

[code]

[URL="http://factordb.com/index.php?id=1100000000628547860"][COLOR=#002099]3^10000+2[/COLOR][/URL]<4772> = [URL="http://factordb.com/index.php?id=8099873"][COLOR=#000000]8099873[/COLOR][/URL] · [URL="http://factordb.com/index.php?id=2710826977"][COLOR=#000000]2710826977[/COLOR][/URL]<10> · [URL="http://factordb.com/index.php?id=67301887049"][COLOR=#000000]67301887049[/COLOR][/URL]<11> · [URL="http://factordb.com/index.php?id=1100000000628758960"][COLOR=#000000]3977361893042794097[/COLOR][/URL]<19> · [URL="http://factordb.com/index.php?id=1100000000628758961"][COLOR=#002099]2775523049...31[/COLOR][/URL]<4726>

[/code]The large last known factor is composite.

 lavalamp 2013-08-23 08:41

Interestingly, YAFU really hates this number. After finding a couple of the smaller factors, it repeatably crashes.

 danaj 2013-08-24 07:17

I tried with yafu and also got a a crash with svn revision 317 (the latest one as of today).

The first four factors are small enough that my p-1 and ecm can easily find them. Likewise GMP-ECM can find them easily.

While it may be "previously unknown status", it takes Pari/GP 0.82 seconds on my computer to indicate it is composite. My Perl package (using GMP) takes 0.77 seconds, as does WraithX's mpz_prp (also using GMP). yafu's bpsw() function takes 0.80 seconds. PFGW 3.7.7 takes 0.2 seconds. I'm sure there are many other tools giving quick results. Clearly this isn't fair, as Pari, GMP, and PFGW have had years of work put into them.

For primes, you're going to need a segment siever of some sort. Not only is it going to be the only way to do big ranges without running out of memory or falling back to nextprime-style loops, but the cache effects ought to actually give you a quite large speedup for large ranges even if you're starting at 2. The fastest and easiest solution is to link with primesieve, but I assume you don't want to do that.

What I did for my software was make a prime iterator class (I stuck with plain C so it's a struct and functions, but same concept) which the various other code could use. Internally it maintains a static shared primary sieve, then fills in a segment as needed. A little 24k primary sieve is enough for primes up to 736800 (fairly standard bitmask with 30 numbers per byte), with 16k segments usually being fine for my use, and it isn't even created unless the caller goes over the primary size. You could adjust sizes as needed -- I went on the low side to keep memory use down, but your application may want higher. Anyway, it gives the effect of unlimited primes while constraining memory use to whatever you'd like. The segment sieves are really fast so it's not really an issue for me, but my primary application isn't trial factoring either.

Sieving that 4772-digit number past 8M seems high to me, but I have the luxury of using GMP's mpz_powm so M-R tests are pretty fast at that size. I'm still fiddling with the exact amounts, but currently I'm using 850k for that size. PFGW seems to be in the same ballpark -- it chooses 1.28M as the 100% factor amount. It's all going to depend on the relative speeds of your trial factoring and modular exponentiations. If you do a lot of trial divisions on big inputs, I'd recommend experimenting with a [URL="http://www.mersenneforum.org/showpost.php?p=152965&postcount=8"]tree sieve[/URL]. I added a simple fixed-height one and it helps with very large numbers, and may help more for you given GMP has lots of optimizations already.

I've never done a bignum library, but at least when doing the native C implementation, mulmod and powmod were the basic functions that got used [I]everywhere[/I] in factoring and primality code, so improving those makes almost everything else go faster.

 LaurV 2013-08-26 04:46

[QUOTE=danaj;350688]I tried with yafu and also got a a crash with svn revision 317 (the latest one as of today).[/QUOTE]
Did not read all the long post (job! sorry!) yet, but if this is supposed to be a yafu bug, can someone post in the yafu thread so Ben gets knowledge/awareness of it? I think he is kind of too busy with serious things, and he does not read lounge threads...

 danaj 2013-08-26 06:51

[QUOTE=LaurV;350880][...]but if this is supposed to be a yafu bug, can someone post in the yafu thread so Ben gets knowledge/awareness of it? [...].[/QUOTE][URL="http://mersenneforum.org/showpost.php?p=350884&postcount=212"]Done[/URL], thanks for the reminder. It looks like yafu isn't acting nicely when getting very large inputs.

The bit about yafu was more a side issue. I'm not entirely sure what the OP had in mind, but I think it was either (a) news that this number is composite, for all those who have been holding their breath for the answer; or (b) starting a conversation about primality testing of large numbers with custom software. (a) is silly, (b) is interesting IMO.

 LaurV 2013-08-26 08:00

c) boasting about his new integer calculator... :razz:

 davar55 2013-08-26 08:37

[QUOTE=LaurV;350889]c) boasting about his new integer calculator... :razz:[/QUOTE]

Maybe. And it's not yet a speed demon compared to these others.
But it does wwork, it did check this special form number of 4772 digits,
(big perhaps only by ordinary standards), and the fact that facttordb
hadn't factored it meant it was worth factoring.

 danaj 2013-08-26 09:17

(c) is fine too. After working hard on something like this for a while, it's nice to tell someone who might care (or at least can immediately grasp the idea and some applications). My family pretends to be interested when I discuss it, but everyone else loses interest after about the 5th word. "Elliptic Curves? Oh, you're going to the gym?"

"the fact that facttordb hadn't factored it meant it was worth factoring." factordb will always have a large supply of unfactored ~5000 digit numbers. This is akin to saying all numbers are worth factoring.

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