![]() |
![]() |
#1 |
May 2004
New York City
5×7×112 Posts |
![]()
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.) |
![]() |
![]() |
![]() |
#2 |
Jun 2012
2×53 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 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. |
![]() |
![]() |
![]() |
#3 | |
May 2004
New York City
108B16 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 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). |
|
![]() |
![]() |
![]() |
#4 |
May 2004
New York City
5·7·112 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> |
![]() |
![]() |
![]() |
#5 |
Oct 2007
Manchester, UK
2×5×137 Posts |
![]()
Interestingly, YAFU really hates this number. After finding a couple of the smaller factors, it repeatably crashes.
|
![]() |
![]() |
![]() |
#6 |
"Dana Jacobsen"
Feb 2011
Bangkok, TH
11100011012 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 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. |
![]() |
![]() |
![]() |
#7 |
Romulan Interpreter
"name field"
Jun 2011
Thailand
2·3·1,669 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 2013-08-26 at 04:47 |
![]() |
![]() |
![]() |
#8 | |
"Dana Jacobsen"
Feb 2011
Bangkok, TH
32×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. |
|
![]() |
![]() |
![]() |
#9 |
Romulan Interpreter
"name field"
Jun 2011
Thailand
2×3×1,669 Posts |
![]()
c) boasting about his new integer calculator...
![]() |
![]() |
![]() |
![]() |
#10 |
May 2004
New York City
5×7×112 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. |
![]() |
![]() |
![]() |
#11 |
"Dana Jacobsen"
Feb 2011
Bangkok, TH
38D16 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 | |
![]() |
||||
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 |