User TJAOI

[Anonuser]

I think that 14 (missed 66-bit) factors were submitted by TJAOI on March 31, 2018.

20244041 35554069 58910141 128481229 168394819 184685483 199002571
199003141 226282967 241398263 312747133 673824449 805355321 963011299

[axn]

Originally Posted by ixfd64

Also, anyone know TJAOI's forum username?

error, I think.

[GP2]

Originally Posted by axn

error, I think.

So, the inventor of the Jacobi check.

[Zanthra]

Originally Posted by LaurV

OK, that's one... It didn't save GIMPS any time, however, because the 6M DC were long passed when the factor was found, but that is a clear GIMPS miss which they (TJAOI) found, and it is ok with us, based on the rule that "is nicer to expose a factor, than to expose a verified LL residue".

This exponent is not so far from the current LL tests, and likely would not have been found by P-1 when the LL test is not that much more expensive than the P-1 test would have been.

http://www.mersenne.ca/exponent/88611311

Either way. I think something important to keep in mind is that whatever source TJAOI is getting their factors from is likely working to a different set of goals from GIMPS. I would expect it's some math or computing department at a university somewhere. TJAOI could be an account opened by one of the people working on the project to copy the factors they find from their own database to the GIMPS database. They don't seem to be using the GIMPS database to decided whether to check factors or not, given that many of the factors they found were in ranges explicitly checked already, so they likely started from scratch.

An interesting question would be if TJAOI has factors for M > M1000000000 . If they are only submitting through the GIMPS system, my understanding is it won't accept anything past that.

A couple questions I have:

If they are doing factor by k, would that not skew the bit depth such that for each given k, the factors found would be smaller at lower exponents and larger at bigger exponents? If that's the case, this suggests that they are not factoring by k, since they seem to submit one bit depth to another. Unless they have a large backlog of factors for high exponents that are not released until the smaller exponents are complete.

If TJAOI started from scratch, and we assume that it has done trial factoring to it's current bit depth on all Mersenne numbers with prime P below 1,000,000,000 (all thing we can reasonably assume). How many GhzDays have they done so far, and how does their pace compare with the rest of the GIMPS? Should we be worried that a university with a billion dollars to spend to going to outpace an amazing and historic cooperative computing project?

[LaurV]

Originally Posted by Zanthra

An interesting question would be if TJAOI has factors for M > M1000000000 . If they are only submitting through the GIMPS system, my understanding is it won't accept anything past that.
<...>
If they are doing factor by k, would that not skew the bit depth such that for each given k, the factors found would be smaller at lower exponents and larger at bigger exponents? If that's the case, this suggests that they are not factoring by k, since they seem to submit one bit depth to another. Unless they have a large backlog of factors for high exponents that are not released until the smaller exponents are complete.

I missed this post for a while, but it came now as I clicked a link in a parallel thread. James site stores factors for mersennes wit expos up to 2^32 (over 4G) and some people store them to 10G.

But the main reason I posted is to point that you have a wrong understanding of what "search by k" means. It is not taking all k's in order - that would be indeed very slow and crazy and it will expose the behavior you point out. The idea is that when you search "by p", you got a "p" and try to find a "k" such that q=2kp+1 divides m=2^p-1. When you search "by k", you pick a prime "q" in your bit range (take all primes which are 1 or 7 mod 8 in order) and then you have a k=(q-1)/2, and try to find "p" (which is one of the factors of this k, not necessarily prime) such as q divides m. It is the other way around, and the "slowness" of the method comes from the fact that "not necessarily prime" part is the one happening most often.

For example, if you pick q=1103, you don't know which mersenne this factors, but you compute kp=(1103-1)/2=551=19*29, so your p can only be 19 or 29. Indeed 2^29-1 is divisible by 1103.

If you pick q=616318177, you don't know which mersenne this factors, but you compute kp=(q-1)/2=308159088, so your p can only be 37, or 167, or 1039. Indeed 2^37-1 is divisible by this q.

But when you pick q=121369 (you have to test all primes which are 1 or 7 mod 8) you get kp=60684 which has factors 3, 13, and 389, and none of these make a mersenne number divisible by q, because in this case p is composite (q divides 2^39-1, i.e. 13*3, which is of no value for you).

Of course, this method can be optimized a lot (sieving, or whatever, as already discussed), but it will be always slower than "by p", and moreover, it does not help GIMPS much (sometimes he gets "lucky" as few guys missed factors in the past, but as GIMPS progresses, you can see that "by p" is getting faster (less exponents, less candidates at the same bitlevel as the exponent is bigger), while "by k" is getting slower. TJAOI was reporting 10k factors per day 3 years ago, only 5-6 k per day last year, and only 2k per day now, and this only 3 days per week.

My argument is only the fact that their resources can be used much better if they join gpu72, or make their own enterprise, but do "normal" TF, which is "proved by the time", it stood the eons we are using it.

But of course, I can be totally wrong, they may have special hardware which is mostly suitable to this method (more calculus, but much simpler), or they may be some math dept in a uni, or some encry/decry company, etc who needs this kind of work for whatever reason only they know. Or maybe some badass teenager guy hacking in a supercomputer, or having some bot army, in unsuspecting computers around the world, hehe.

Whatever their goal is, they were very consistent (and persistent) along the time with the clocks they contribute, which worth a lot of admiration.

[GP2]

In another thread, James Heinrich mentioned that he has a page which tracks TJAOI's contributions. The patterns are very regular.

Originally Posted by LaurV

But when you pick q=121369 (you have to test all primes which are 1 or 7 mod 8) you get kp=60684 which has factors 3, 13, and 389, and none of these make a mersenne number divisible by q, because in this case p is composite (q divides 2^39-1, i.e. 13*3, which is of no value for you).

The Cunningham project cares about factors for non-prime exponents. Maybe TJAOI does too?

you can see that "by p" is getting faster (less exponents, less candidates at the same bitlevel as the exponent is bigger), while "by k" is getting slower. TJAOI was reporting 10k factors per day 3 years ago, only 5-6 k per day last year, and only 2k per day now, and this only 3 days per week.

But a few thousand factors a day is the maximum of what the entire project accomplishes. So he is contributing more new factors overall than everyone doing "by p" combined. Although obviously they are mainly second-and-higher factors of already-factored Mersenne numbers, whereas others are mainly looking for first factors.

they may have special hardware which is mostly suitable to this method (more calculus, but much simpler)

Is this the sort of thing that could be programmed on an FPGA by any chance?

One benefit of knowing all factors of size less than X bits for all Mersenne numbers with exponents less than a billion is that you can try to datamine and analyze to see if the distribution of factors matches expectations, for instance Wagstaff's heuristics. Currently, X = 65 bits, due to TJAOI's efforts.

[LaurV]

Sure. That, nobody contests...

[kriesel]

Originally Posted by Zanthra

An interesting question would be if TJAOI has factors for M > M1000000000 . If they are only submitting through the GIMPS system, my understanding is it won't accept anything past that.

If he is obtaining factors for 10⁹<M<2³², he could submit those at mersenne.ca.
I don't know if he _is_ finding or submitting such.

Should we be worried that a university with a billion dollars to spend [is] going to outpace an amazing and historic cooperative computing project?

No. I used to work at a university with a billion-plus US$ annual research budget (and multibillion dollar alumni research fund endowment). Those funds must be spent for the designated research purposes, or someone can go to prison for diverting them. It would surface during one of the regularly occurring audits. The funding sources would get very cranky about diversion. I think the probability of $10⁹ being made available for number theory computing to one university is a very good approximation of the integer zero. The probability of it going unnoticed either in the financial reports or the number theory community or the press is even lower. Such large sums go to varied, targeted, applied research projects; lots of them, which usually are MUCH smaller individual awards. Largest project budget I recall being involved with in 35 years was 1/3 billion spread over many years and hundreds of institutions.

Now, if there was a way that such factors as TJAOI reports fell out as a side effect of the NSA's computing, or Russian or Chinese government efforts, that did not constitute a usable information leak about what they're up to, and TJAOI had written permission from a suitable authority to share those factors locked in a safe, as the proverbial get out of jail free card, that's another matter.

[ATH]

Originally Posted by LaurV

But the main reason I posted is to point that you have a wrong understanding of what "search by k" means. It is not taking all k's in order - that would be indeed very slow and crazy and it will expose the behavior you point out. The idea is that when you search "by p", you got a "p" and try to find a "k" such that q=2kp+1 divides m=2^p-1. When you search "by k", you pick a prime "q" in your bit range (take all primes which are 1 or 7 mod 8 in order) and then you have a k=(q-1)/2, and try to find "p" (which is one of the factors of this k, not necessarily prime) such as q divides m. It is the other way around, and the "slowness" of the method comes from the fact that "not necessarily prime" part is the one happening most often.

I would not call this "search by k", I would call it "seach by q" meaning searching by increasing size of q=2kp+1. The "normal" factoring we do in GIMPS we would call "search by p", which means keeping p fixed and searching for factors of a single exponent.

In my opinion "search by k" would likewise be holding k fixed and searching through all p values for factors with this particular k, as I described here .

But this way would not find factors in order or even in bit depth order.

[LaurV]

The name itself has a longer history, mainly referring to the product ”kp” in q, where you either have the first or the second and try to find the other one. For this, there were algorithms shown and discussions in the forum, but all of them revolves around the idea (shown here in post #417 last time, and shown by me in 2011 when I joined the forum, one of my first posts, but most probably shown by other people long before):

q=10^3;
while(q<10^5,
   v=factorint(q-1)~[1,];
   for(i=1,#v,
      if(v[i]<10^9&&Mod(2,q)^v[i]==1,
         print(q" divide 2^"v[i]"-1");
         break
      )
   );
   until(Mod(q,8)==1||Mod(q,8)==7,
      q=nextprime(q+1)
   )
)

Here the costly part is to factor q-1, which is very fast, as we factor numbers of 20-40 digits, but still takes 70% of the time. If you avoid the ”nextprime” which takes the rest of 30%, with some super-fast wheel sieving, like you say ”eliminating stuff which is not x mod some n# primorial” (not all q left need to be prime, even MfaktX does exponentiation for few non-primes, because after a while, doing exponentiation is faster than continuing to sieve) then you are left with 95% of the time ”factoring q-1” stuff, and here, even if you can make it very fast, or avoid it completely by some sieving or magic, you are still left with a lot of cases where the q you picked divides a mersenne with a composite exponent (most of them).

But you are right about the name, it should be called ”by q” hehe...

The same way (I proposed this long time ago, more like a joke) the Pollard's P-1 method, when applied to mersenne numbers, i.e. reduced to "k being smooth" instead of "p-1 being smooth", should be called either "K method", or "Q-1 method", because the terminology here (name of the variables) is quite fixed, p is always the prime exponent, and the factor is called q. We always have m=2^p-1, p is prime, and q=2kp+1 with arbitrary k. So, the ”prime factor minus 1 is smooth” means here ”q-1 is smooth”, which is ”kp is smooth”, and because we know p, it is in fact, ”k is smooth”. So, let's call it "K" instead of "P-1" (which will be more confuse, haha). Or just "Q-1" and satisfy everybody.

Except maybe Mr. Pollard (some say the "P" in the name doesn't come from the "prime" factor we hunt ).

Of course we can not change the name of a well known method... This was just a joke. (But it may catch... hopefully )

So you see, it is all politics...

[James Heinrich]

Originally Posted by LaurV

James site stores factors for mersennes wit expos up to 2^32 (over 4G) and some people store them to 10G

Originally Posted by kriesel

If he is obtaining factors for 10⁹<M<2³², he could submit those at mersenne.ca

Actually that is now 10⁹<M<10¹⁰, although the space above 2³² is not advertised mostly because the mainstream software (mfakt_) can't handle larger exponents.