mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Lounge

Reply
 
Thread Tools
Old 2013-08-04, 11:43   #1
davar55
 
davar55's Avatar
 
May 2004
New York City

3×1,409 Posts
Default 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.)
davar55 is offline   Reply With Quote
Old 2013-08-04, 12:28   #2
f1pokerspeed
 
Jun 2012

2×53 Posts
Default

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.
f1pokerspeed is offline   Reply With Quote
Old 2013-08-04, 23:13   #3
davar55
 
davar55's Avatar
 
May 2004
New York City

3·1,409 Posts
Default

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.
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
for this trade-off).
davar55 is offline   Reply With Quote
Old 2013-08-16, 11:52   #4
davar55
 
davar55's Avatar
 
May 2004
New York City

10000100000112 Posts
Default

I checked with faactordb.

The factorization of 3^10000+2 is currently:

Code:
3^10000+2<4772> = 8099873 · 2710826977<10> · 67301887049<11> · 3977361893042794097<19> · 2775523049...31<4726>
The large last known factor is composite.
davar55 is offline   Reply With Quote
Old 2013-08-23, 08:41   #5
lavalamp
 
lavalamp's Avatar
 
Oct 2007
London, UK

1,297 Posts
Default

Interestingly, YAFU really hates this number. After finding a couple of the smaller factors, it repeatably crashes.
lavalamp is offline   Reply With Quote
Old 2013-08-24, 07:17   #6
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2·11·41 Posts
Default

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 tree sieve. 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 everywhere in factoring and primality code, so improving those makes almost everything else go faster.
danaj is offline   Reply With Quote
Old 2013-08-26, 04:46   #7
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

2×7×613 Posts
Default

Quote:
Originally Posted by danaj View Post
I tried with yafu and also got a a crash with svn revision 317 (the latest one as of today).
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...

Last fiddled with by LaurV on 2013-08-26 at 04:47
LaurV is online now   Reply With Quote
Old 2013-08-26, 06:51   #8
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

38616 Posts
Default

Quote:
Originally Posted by LaurV View Post
[...]but if this is supposed to be a yafu bug, can someone post in the yafu thread so Ben gets knowledge/awareness of it? [...].
Done, 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.
danaj is offline   Reply With Quote
Old 2013-08-26, 08:00   #9
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

2·7·613 Posts
Default

c) boasting about his new integer calculator...
LaurV is online now   Reply With Quote
Old 2013-08-26, 08:37   #10
davar55
 
davar55's Avatar
 
May 2004
New York City

3·1,409 Posts
Default

Quote:
Originally Posted by LaurV View Post
c) boasting about his new integer calculator...
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.
davar55 is offline   Reply With Quote
Old 2013-08-26, 09:17   #11
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

38616 Posts
Default

(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.
danaj is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
GPU sieving drive part III: k<10000 n=3M-6M mdettweiler No Prime Left Behind 19 2011-02-17 21:13
GPU sieving drive part II: k<10000 n=2M-3M mdettweiler No Prime Left Behind 44 2010-11-28 10:59
Bigger and better GPU sieving drive: k<10000 n<2M mdettweiler No Prime Left Behind 61 2010-10-29 18:48
10000 posts! 10metreh Factoring 24 2009-04-06 07:52
lag in factoring Mersenne numbers (P < 10000)? ixfd64 Factoring 1 2006-01-02 08:25

All times are UTC. The time now is 04:32.

Sun Jul 5 04:32:21 UTC 2020 up 102 days, 2:05, 1 user, load averages: 1.26, 1.29, 1.35

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