How did Prof.Cole factor M67?

[axn]

Originally Posted by R.D. Silverman

Did I gore your ox, too?

[R.D. Silverman]

Originally Posted by LaurV

Our goal was not to get the fastest factoring method, but to show that even such non-efficient stuff like TF (which is in fact what Mr. Cole used) would factor M67 in "milliseconds" in an average computer. That is what the OP wanted to know.

Which is what I said. I did not specify a particular method.

[xilman]

Originally Posted by R.D. Silverman

I did say "a few milliseconds". But of course, no one listens.

People were listening.

Trust, but verify, as Ronnie would say.

[Uncwilly]

Originally Posted by R.D. Silverman

Which is what I said. I did not specify a particular method.

And for the OP's benefit they are actually showing real world examples to demonstrate this. No need to get your knickers in a knot. You should be thanking them for demonstrating this conclusively to the OP.

[LaurV]

Originally Posted by R.D. Silverman

Which is what I said. I did not specify a particular method.

I was replying to CRG, about "willing to optimize". In fact I was in agreement with you all the way, if you look carefully. Don't be sad, no one listens to me either (I mean, generally, not in this topic), my life's drama...

Better lock this topic before sparks get to flames...
The OP got his answer already.

[CRGreathouse]

Originally Posted by LaurV

Pari, Trial Factoring with 420 classes (script posted here in the past), slow/moderate laptop (i5-3340M at 2.7GHz)

I found a reference to it in a previous thread of mine, but I can't find the script on these forums or elsewhere on the web. Could you post it, please?

[LaurV]

That is easy, because I got recently into a PM exchange with Hans Loeblich who extended my script for more classes and made it faster and parallel, and that is easy to find, I try to keep my PM list in order hehe... All the links are there, in that thread (edit2: posts from #32 to #52 and after, the script is attached to post #52 -- interesting that the examples provided there were exactly for M67, haha)

Edit: I reopened the topic, as long as the argument continues , it didn't feel right that only the mods can post, and other users have to right to reply if they choose so.

[CRGreathouse]

Thank you.

By the way, why 420 instead of 210?

[axn]

Originally Posted by CRGreathouse

By the way, why 420 instead of 210?

There are two classes, 1 and 7 (mod 8)

[LaurV]

Originally Posted by CRGreathouse

Thank you.
By the way, why 420 instead of 210?

Because making it multiple of 4 helps a lot when eliminating classes of k which would result in factors q=2kp+1 being 3 and 5 (mod 8). If the number of classes are 4, 12, 60, 420, 4620 (the double primorials, instead of 2, 6, 30, 210, 2310), then for some k and p, will have q already in the right class (mod 8).

For example: if p is 3 (mod 4) and k is 15 (mod 420), therefore k is 3 (mod 4) (here, you could not say that, in case of k in 210 classes! You would have no information about modularity of k to 4, as 210 is not multiple of 4), therefore q is 2*3*3+1=19 (mod 8, due to the 2 in front, you can double the modulus here), which is 3 (mod 8) and so, when p=3 (mod 4), you can completely eliminate the class k=15 (mod 420), due to the fact that all mersenne factors must be 1 or 7 (mod 8). When p=3 (mod 4), there is no factor q=2kp+1 with k=15 (mod 420). This is how you get from 4620 classes to only 960 to test for each p, or respectively, from 420 to only 96.

That's why. This doubles the testing speed. See those 3 posts of mine in the linked thread where I explained. The idea is not mine, it comes from Oliver and the forum (there are antique discussions from when he was developing mfaktc, in mfaktc thread and archieves).

[CRGreathouse]

Thanks!