20130804, 11:43  #1 
May 2004
New York City
5·7·11^{2} Posts 
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.) 
20130804, 12:28  #2 
Jun 2012
1101010_{2} Posts 
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 testsuite.
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. 
20130804, 23:13  #3  
May 2004
New York City
10213_{8} Posts 
Quote:
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 floatbased 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 tradeoff). 

20130816, 11:52  #4 
May 2004
New York City
1000010001011_{2} Posts 
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> 
20130823, 08:41  #5 
Oct 2007
Manchester, UK
2535_{8} Posts 
Interestingly, YAFU really hates this number. After finding a couple of the smaller factors, it repeatably crashes.

20130824, 07:17  #6 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
3^{2}×101 Posts 
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 p1 and ecm can easily find them. Likewise GMPECM 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 nextprimestyle 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 4772digit number past 8M seems high to me, but I have the luxury of using GMP's mpz_powm so MR 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 fixedheight 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. 
20130826, 04:46  #7 
Romulan Interpreter
"name field"
Jun 2011
Thailand
3×5×683 Posts 
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 20130826 at 04:47 
20130826, 06:51  #8  
"Dana Jacobsen"
Feb 2011
Bangkok, TH
3^{2}×101 Posts 
Quote:
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. 

20130826, 08:00  #9 
Romulan Interpreter
"name field"
Jun 2011
Thailand
3·5·683 Posts 
c) boasting about his new integer calculator...

20130826, 08:37  #10 
May 2004
New York City
5×7×11^{2} Posts 
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. 
20130826, 09:17  #11 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
3^{2}·101 Posts 
(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. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
GPU sieving drive part III: k<10000 n=3M6M  mdettweiler  No Prime Left Behind  19  20110217 21:13 
GPU sieving drive part II: k<10000 n=2M3M  mdettweiler  No Prime Left Behind  44  20101128 10:59 
Bigger and better GPU sieving drive: k<10000 n<2M  mdettweiler  No Prime Left Behind  61  20101029 18:48 
10000 posts!  10metreh  Factoring  24  20090406 07:52 
lag in factoring Mersenne numbers (P < 10000)?  ixfd64  Factoring  1  20060102 08:25 