User TJAOI

[bloodIce]

If you use some clever modulus arithmetic, you might not need to do all divisions. What would be cheaper (division or modulus arithmetic), probably is dependent on your division implementation. Or more strictly if you use simple division as usual, than your lower expos are faster to test by division, or if you exponentiate than higher range is faster to do. There are some turning points in each, where modulus arithmetic would be faster to implement.

I would be glad for a lesson of modulus arithmetic for this problem. If we have given prime q=41234346670140799944889 and the factors of q-1 as set {2, 3, 7, 181, 409, 1721, 43573, 44212963}, which ones we could safely eliminate? So which ones of exponents {2, 3, 7, 181, 409, 1721, 43573, 44212963} we should not bother to test of being divisible by q?

[LaurV]

Originally Posted by bloodIce

So which ones of exponents {2, 3, 7, 181, 409, 1721, 43573, 44212963} we should not bother to test of being divisible by q?

As per your PM, in this example, the factor is 1 (mod 8), you could "safely" eliminate only 2,3,7, because the factor is much bigger than 2^7-1. All the other you have to test (i.e. do the exponentiation, i.e. power mod function). If the factor is prime, and 1 or 7 (mod 8) you can't eliminate anything by "modular arithmetic". You have to test everything. Think about mfaktX, those classes are eliminated because either the resulting candidates q would not be prime, or they would be 3 or 5 (mod 8). But when you start (going in the opposite way) with a candidate which is prime, and 1 or 7 (mod 8), then you can't eliminate any "exponent". If for some exponent the "class" of q would have been eliminated, than you would lose a possible candidate q (which, remember, it is prime, and 1,7 (mod 8)).

So, the only "safe" to eliminate are the exponents which are over 1 billion (those are not interesting for Gimps) or those for which 2^p-1 is higher than q^2, i.e. few small exponents, under p=100, which are already full factored.

A better question would be if you really need to test for primality of q, before factoring (q-1)/2, or (q-1)/8. If you sieve is fast, few more exponentiations for non-prime q (which will end with "no factor" anyhow) would be faster that testing every q for primality.

Somewhere here around there is a pari/gp implementation for this method, which displays the timing for each "activity", primality testing, factoring, overload, etc. I posted some time ago. You can look for it.

[axn]

Originally Posted by LaurV

i.e. few small exponents, under p=100, which are already full factored.

Do you believe that M(181) and M(409) have not been fully factored?

As a practical matter, all exponents under 2000 can be discarded because either they are fully factored or sufficient ECM has been run to rule out the factor candidate.

[LaurV]

You are right, from that point of view.
The OP was interested in eliminating stuff by modular tricks, and I don't know any.

OTOH, exponentiation for 181 and 409 (and even 100k exponents) is so fast as testing if they are so small

The gain would be if he can eliminate larger birds, or avoid factorization somehow. There is an algorithm to get p=\beta(q) such as q | Mp and for any r such as q | Mr, we have p | r. The algorithm works for any odd q, not necesary prime, for example \beta(9)=6, \beta(21)=6, \beta(71)=35, \beta(89)=11, \beta(99)=30, etc, but that algorithm is as slow as factorization.

[bloodIce]

Indeed my question was if it is possible to eliminate exponent candidates through modular arithmetic and LaurV clearly pointed that it is a wrong way of thinking. LaurV, thank you for replying to my stupid question. At least I learned something. I personally would never try anything below M10000 as it is highly improbable that we will have a factor with the range of factorization power (a candidate q above 45-50 digits is hard to factorize and exponents <10000 clearly are tried for such "small" factors).

The gain would be if he can eliminate larger birds, or avoid factorization somehow.

That is where I aim, to kill ranges >200 000, as I use simple division. Modular magic does not apply.

P.S. Avoid factorization? That would be nice, but then we have to construct q, similarly to any search though k.The beauty of the TJAOI's work is in the reverse approach (quite fruitful for small q and a nightmare for the database of course).

[legendarymudkip]

TJAOI Manual testing 302093003 F Sep 27 2014 11:59AM 0.0 0.0000 12766940905816873
TJAOI Manual testing 720779699 F Sep 27 2014 11:59AM 0.0 0.0000 12907469135237953

Oddly the recent cleared report shows just one result out of order - and one that should've been reported yesterday judging by the size. Probably just a q he missed, but it's strange to see that.

[flagrantflowers]

Finished 2^54 today.

Found ~350,000 factors from 2^53-->54.

Started on September 2nd and Finished today.

[casmith789]

It seems to me that the "recent cleared" is not working as intended. If these exponents have already been factored, they aren't being cleared now so there should be a check for an already factored exponent before showing on that page. Then we could see if TJAOI is finding any factors for unfactored exponents.

[flagrantflowers]

Originally Posted by casmith789

Then we could see if TJAOI is finding any factors for unfactored exponents.

They are not finding factors for number which have not been factored as everything has been TF'd above the limits of their search. They also regularly run ECM and all (?most?) of those exponents have previous factors as well.

Short answer: They are not finding factors for any unfactored numbers. I doubt that they will get above 2^61 in less than a couple of years which is the minimum level that all numbers have been TF'd to.

[flagrantflowers]

Finished 2^55 today.

Found ~413000 factors.

[Anonuser]

Originally Posted by flagrantflowers

They are not finding factors for number which have not been factored as everything has been TF'd above the limits of their search. They also regularly run ECM and all (?most?) of those exponents have previous factors as well.

Short answer: They are not finding factors for any unfactored numbers. I doubt that they will get above 2^61 in less than a couple of years which is the minimum level that all numbers have been TF'd to.

Now that's not quite true (please see the links below).

109252799 240874213 252202289 258230057 261399217 263487907 303101047 326566909 359856499 369858761
397461607 412469627 413001497 426275299 442328771 447476401 486509377 497342737 505503371 522960943
537839851 547552667 561825293 562505611 566369017 592582589 603295153 618849137 623325497 623710957
640176941 647528111 660762161 668331623 689381573 695332819 738275149 742897583 747730469 759936811
767251937 774338557 774984037 806753677 813330223 821771833 843585377 846942643 856101901 861840079
878314699 879826861 885371657 915739621 924488843 944011273 963535717 971859341 993797821 997732003