73 digit ECM factor

[R.D. Silverman]

Originally Posted by Mini-Geek

Sometimes, but not all the time? Is there a pattern as to when it does/doesn't happen?
For Mersenne numbers there is such a known identity:


.

Sigh. You need to go back an thoroughly relearn the basic algebra that
you failed to learn in high school. The above identity, which you seem
to think is a mystery, is a trivial consequence of elementary polynomial
algebra. You did study factorization of polynomials, didn't you?


Here's a high school level exercize:

Given the polynomial x^ab - 1 for a,b, odd integers, PROVE that
it is divisible by x^a-1, and x^b-1. (and, of course, x-1).

The proof uses nothing more than elementary facts about polynomials.
Hint: One such proof uses the roots of the polynomials. You do know
the remainder theorem for polynomials?? If not, I give it as
an exercize:

Given a polynomial over R: f(x) = sum a_i x^i, i=0,...N,
PROVE: f(r) = the remainder when f(x) is divisible by (x-r).

I do not know you personally and intend no insult, but anyone who
can not do the above exercizes has no business dabbling in number theory.
Such a person simply lacks too much basic algebra.

[R.D. Silverman]

Originally Posted by Mini-Geek

I'm guessing useless coincidences. (though possibly useless side effects of known-and-used facts, or rediscovered truths; let's find out...)

To put them in other ways:
(2^p-2 is divisible by 6, which is equivalent to...)

This is true for every 2^n-2 with odd n. While I can't properly explain the why of the matter, it is a fact, as is easily seen here:
.

If one can't explain why, one has no business dabbling in this domain.
'Why' comes from trivial first year algebra, plus a little thought
about when an integer might be divisible by 3.

(1) 2^p-2 is trivially divisible by 2.
(2) 2(2^(p-1) - 1) is, with a little more work, easily seen to be divisible by 3.
Think about difference of squares.

The math involved is TRIVIAL HIGH SCHOOL ALGEBRA. If K is even, then
either K+1 or K-1 is divisible by 3. If one can't explain this, one has no
business trying to discuss number theory. Such a person is simply too
ignorant about elementary high school algebra to have any hope of
understanding this subject.

I have said this multiple times, but the message does not get through.
Elementary number theory can be learned with just minimal background,
but that minimal background MUST include mastery of high
school algebra, plus the ability to put together a mathematical argument
from basic principles, rather than just parroting from memory.

[philmoore]

Originally Posted by R.D. Silverman

The math involved is TRIVIAL HIGH SCHOOL ALGEBRA. If K is even, then either K+1 or K-1 is divisible by 3. If one can't explain this, one has no business trying to discuss number theory. Such a person is simply too ignorant about elementary high school algebra to have any hope of understanding this subject.

Hmm, sounds like you need to take your own advice!

[Batalov]

Nice pair, now. Congratulations!

[retina]

Originally Posted by xilman

They are two alternative spellings for the same word. I'm sure you're familiar with that concept.

Hehe, not quite what I meant. Nevermind, all this could lead to a terrible argument over the ambiguity of a word ... or three.

Is it not true that all words are invented words?

[wreck]

Here is the second p73's group order

Magma V2.16-6     Mon Apr 19 2010 20:22:13    [Seed = 2434200602]
   -------------------------------------

[ <2, 2>, <3, 2>, <5, 1>, <23, 1>, <1429, 1>, <28229, 1>, <139133, 1>, <249677, 
1>, <389749, 1>, <15487861, 1>, <47501591, 1>, <111707179, 1>, <431421191, 1>, 
<13007798103359, 1> ]

Total time: 6.549 seconds, Total memory usage: 17.75MB

[frmky]

So using the default B2, a B1 of 8e8 would have been sufficient to find this factor.

Interesting sigmas:
4000027779
3000085158
3000000588

Stepping sequentially from a starting value rather than relying on random numbers not to repeat? Not sure I'd have that much confidence in my coordination skills.

[xilman]

Originally Posted by frmky

Stepping sequentially from a starting value rather than relying on random numbers not to repeat? Not sure I'd have that much confidence in my coordination skills.

This is purely a guess, but perhaps they have a program onto which they offload the co-ordination.

Paul

[bdodson]

Originally Posted by frmky

So using the default B2, a B1 of 8e8 would have been sufficient to find this factor.

Interesting sigmas: ...

With a sequential choice of sigma they can be certain that there
aren't two repetitions. GMP-ECM has kept 32-bit sigmas, perhaps on
the expection that no single number would be run far enough to have
more than one or two duplicate sigma. The BKLM runs have been doing
30000 curves, as in Thorsten's report on the first p73 ... well, still not
much chance of more than one or two; but none-for-sure going
sequentially. I had an impression that there was confidence in 32-bits
of randomness, less so about 64-bits worth. (Being carefull to the new
forum protocol on public attribution of private conversation. The above
version as an "impression" is my own, extrapolated from several sources.)
If DES is our best analyzed attempt at 56-bits, we know that 2^47 chosen
plain texts sufficies to determine the 56-bits --- not that brute force wasn't
far quicker, but under "perfect security" requirements that might be taken
as only 47-bits of randomness achieved? Then there's the "internal" cipher
in the fiestal, using 48-bit keys. I asked an expert on random numbers
about this view (cf. the "Numerical Recipes in C" CD), and got back "47-bits
is pretty good!", rather than a dispute.

I was just looking at 3 months of ecm spread over [c234-c289 plus "the
Mn, Pn up to c366"], with B1 = 260M; and found 62K curves without any
repeated sigma. That's 7t55 or 1.4t60, without finding any more of
Aoki's p50/p51 factors; just a single p54.

Nevermind. On Greg's point, B1=8e8 is rather close to the value
B1=850M sometimes given as p65-optimal, with the ECM-GMP default B2.
Using B1=260M instead, Alex's "expected number of curves" to find
a p65 is 263K. That's after I gave up on being able to run a sufficient
number of 850M-curves to give ecm a chance. With hindsight, the curves
that first broke 50-digits (p53) and 60-digits (p66) using substantially
suboptimal B1's may not have been reliable indicators for an effort to
break 70-digits. I'm not entirely sure that 3 years of ecm on 500 fast pcs
(1500 cpuyears, more or less) is a sufficient test of the effectiveness of
p60-limits at finding a p70; but this second BKLM p73 might suggest that
access to sufficiently many pcs to run step2 with p65-optimal limits for
several hundred cpuyears might have a better chance. (The Cunningham
targets here were mostly < c234, to keep the curve counts up.)

-Bruce

PS - Alternatively, if p60-optimal is insufficient for a plausible chance at
a p70; and the expected factor size in the portion of the current Cunningham
list from c234-c366 is closer to p55, dropping back to p55-limits might be
better use of the (public) cptime. Cf. Jason's reference to my post in
favor of the objective of effectively hitting singles -vs- "swinging for the
fences". It's baseball season over here.

[science_man_88]

Originally Posted by MatWur-S530113

With ECM 2005 the first 6x-digit factor was found (afaik), now 2010 the first factor with 7x digit. When the first 8x will be found?

well with that time line I'm guessing somewhere in 2015

[henryzz]

Originally Posted by science_man_88

well with that time line I'm guessing somewhere in 2015

i would suspect earlier as we have just had a breakthrough in technology(PS3s)
The difference between 2004 and 2009 isnt that great in comparison.