73 digit ECM factor - Page 3

yoyo · 2010-03-10, 16:05

Quote:

Originally Posted by R.D. Silverman

Why should there be?

There seems to be an (unreasonable IMO) attitude among many people
that the achievements of a research group should be made available
to the general public.

Why should epfl give away the results of their intellectual efforts?

I didn't say that they should. I only asked if it is available.
But Brian gave a good explanation why there could be a reason to make it public.

yoyo

WVU Mersenneer · 2010-03-17, 15:09

This is an amazing find, congratulations to all, especially to Mr. Zimmermann for his excellent program.

Two questions:

1. Is GMP-ECM available for Windows? All I have access to are Windows machines and I'm not courageous-enough to attempt to put Linux or any other OS on them, and I have been to Mr. Zimmermann's site but was unable to answer my own question.

2. What is "Group order" per the below post from jrk? I don't have an extensive math background but find the research and results fascinating and would like to learn as much as possible.

Quote:

Originally Posted by jrk

Group order is:

Code:

[2 4]
 
[3 2]
 
[13 1]
 
[23 1]
 
[61 1]
 
[379 1]
 
[13477 1]
 
[272603 1]
 
[12331747 1]
 
[19481797 1]
 
[125550349 1]
 
[789142847 1]
 
[1923401731 1]
 
[10801302048203 1]

Thank you

bsquared · 2010-03-17, 15:16

Quote:

Originally Posted by WVU Mersenneer

1. Is GMP-ECM available for Windows? All I have access to are Windows machines and I'm not courageous-enough to attempt to put Linux or any other OS on them, and I have been to Mr. Zimmermann's site but was unable to answer my own question.

Yep. Also here.

WVU Mersenneer · 2010-03-17, 15:25

Quote:

Originally Posted by bsquared

Yep. Also here.

Outstanding! Thank you very much for your quick help, bsquared.

Does anyone happen to know if GMP-ECM all results are reported here so as to update Mr. Woltman's tables, or if only the impressive successes?

R.D. Silverman · 2010-03-17, 15:35

Quote:

Originally Posted by WVU Mersenneer

2. What is "Group order" per the below post from jrk? I don't have an extensive math background but find the research and results fascinating and would like to learn as much as possible.

Thank you

Read: Crandall & Pomerance: Prime Numbers; A Computational
Perspective. It will explain how ECM works.

Briefly: The set of rational points on an Elliptic curve taken over a
prime field form a group under an operation that looks like addition.
Take any two points and draw a line connecting them. The line intersects
the Elliptic curve at a 3rd point. Reflect that point across the X-axis.
The reflected point is now the "sum" (under the group operation) of
the first two points.

If the field is Z/pZ, then the SIZE of the group (its order) is a random
integer in the range [p - 2sqrt(p) + 1, p+2sqrt(p) + 1]. If this
random integer is SMOOTH, then the elliptic curve algorithm will succeed in finding p.

In practice, p is an unknown divisor of a composite integer N, so the
group computations are done mod N, rather than mod p.

I suggest that you first learn how the Pollard P-1 algorithm works.
Understanding it will make understanding ECM a lot easier.

bsquared · 2010-03-17, 15:59

Quote:

Originally Posted by R.D. Silverman

If the field is Z/pZ, then the SIZE of the group (its order) is a random
integer in the range [p - 2sqrt(p) + 1, p+2sqrt(p) + 1]. If this
random integer is SMOOTH, then the elliptic curve algorithm will succeed in finding p.

To elaborate on this a little bit for the benefit of WVU Mersenneer: the particular group being tested at any given time is usually called a "curve" and is specified by a randomly chosen parameter called sigma. Once we find the factors, we can compute the group order for the lucky curve and then factor that group order in order to determine how smooth it was. This is what jrk did.

This is done in order to see either how close we came to missing the factorization (by seeing how close the largest factors of the group order came to the B1/B2 limits), or how smooth the group order was. As in "wow, we could have found this factor with a B1 100 times smaller than we did because this group order turned out to be so smooth!". If you can get excited about the relative smoothness of elliptic curve group orders, then you belong on this forum

TimSorbet · 2010-03-17, 16:15

Quote:

Originally Posted by WVU Mersenneer

2. What is "Group order" per the below post from jrk? I don't have an extensive math background but find the research and results fascinating and would like to learn as much as possible.

This page has some good info:
http://mersennewiki.org/index.php/Elliptic_curve_method
Compare to:
http://mersennewiki.org/index.php/P-...ization_Method
Now, to provide a very basic explanation of what all that means in the end (instead of the mathematical details of how it works):
Basically:
the P-1 method will find a factor P if P-1 has at most one factor above B1 and no factor above B2 (the rest of the factors would be below B1, of course), and
ECM will find a factor P if P's group order (determined by the sigma, which is chosen randomly) has at most one factor above B1 and no factor above B2 (the rest of the factors would be below B1, of course).

The group order posted is really the group order's prime factorization. The format shown is:

Code:

[p1 q1]
[p2 q2]
...
[pz qz]

where N=p1^q1*p2^q2*...*pz^qz is N's prime factorization.
As its largest factors are 1923401731 and 10801302048203, we know that the minimum B1 and B2 to find this factor in step 2 are 1923401731 and 10801302048203, respectively. Or the minimum B1 to find this factor in step 1 is 10801302048203 (without step 2, the B2 value doesn't matter).

WVU Mersenneer · 2010-03-17, 16:43

Sincere respect, appreciation, and thanks to Dr. Silverman and bsquared for the summarized yet powerful explanation and education. I will do my best to locate the text suggested and I thank you for that additional suggestion.

Might I also ask what "branch" of mathematics best deals with the teachings Dr. Silverman and bsquare provided above? Perhaps I can also pick up a text book or two from the library and learn more or find the appropriate professor on campus of whom to ask further questions.

I was also wondering, and forgive me if this is an ignorant question or will be answered by reading the text Dr. Silverman suggested, but I have noticed that Mersenne numbers, when subtracted by and additional 1, are always divisible by 6 and then easily divisible into other small prime factors, one of the factors always being the power of 2 used to obtain the Mersenne number.

For example:
(2^31 - 1) - 1 = 2,147,483,646
2,147,483,646 / 6 = 357,913,941
357,913,941 = 3 * 7 * 11 * 31 * 151 * 331

(2^89 - 1) - 1 = 618,970,019,642,690,137,449,562,110
618,970,019,642,690,137,449,562,110 / 6 = 103,161,669,940,448,356,241,593,685
103,161,669,940,448,356,241,593,685 = 5 * 17 * 23 * 89 * 353 * 397 * 683 * 2113 * 2,931,542,417

Furthermore, some of the factors found using this "method" are found in more than one "Mersenne - 1", sometimes the factors being factors of non-prime Mersennes.

Is this "related" in any way to the Pollard P-1 algorithm or any other legitimate algorithm, or is this just a useless coincidence upon which I stumbled?

WVU Mersenneer · 2010-03-17, 16:47

Mini-Geek, please consider yourself added to the appropriate thanks I hopefully gave to Dr. Silverman and bsquared above.

I have read the links you provided dozens of times prior to posting here, and as you have assuredly already guessed, it was far above my comprehension. However, I do also appreciate your "dumbing down" those explanations for me, and I feel I can almost grasp that. Hopefully once I learn what "branch" this all falls under I can locate a book or two to study and learn more, or that I remember more from the Number Theory course I took 12 years ago.

My thanks to all.

TimSorbet · 2010-03-17, 17:28

Quote:

Originally Posted by WVU Mersenneer

Is this "related" in any way to the Pollard P-1 algorithm or any other legitimate algorithm, or is this just a useless coincidence upon which I stumbled?

I'm guessing useless coincidences.

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

Quote:

Originally Posted by WVU Mersenneer

I was also wondering, and forgive me if this is an ignorant question or will be answered by reading the text Dr. Silverman suggested, but I have noticed that Mersenne numbers, when subtracted by and additional 1, are always divisible by 6 and then easily divisible into other small prime factors, one of the factors always being the power of 2 used to obtain the Mersenne number.

Furthermore, some of the factors found using this "method" are found in more than one "Mersenne - 1", sometimes the factors being factors of non-prime Mersennes.

To put them in other ways:
(2^p-2 is divisible by 6, which is equivalent to...)
$2^p-2 \equiv 0 \pmod 6$
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:
$2^1 \equiv 2 \pmod 6$
$2^2 \equiv 4 \pmod 6$
$2^3 \equiv 2 \pmod 6$
$2^4 \equiv 4 \pmod 6$
And this pattern repeats (2*2=4 mod 6, 4*2=2 mod 6). So 2^n-2 with odd n is always divisible by 6.
(while we're sort of on the subject, there's a trivially-proven observation that all primes above 3 are of the form 6*n-1 or 6*n+1 for some n)

(2^p-2 is divisible by p, which is equivalent to...)
$2^p-2 \equiv 0 \pmod p$
This is Fermat's Little Theorem with a=2:
$a^p \equiv a \pmod{p}$ (Little Theorem)
$2^p-2 \equiv 0 \pmod p$ (your observation)
So your observation is correct.

(2^p-2 is pretty smooth)
(see below)

Quote:

Originally Posted by WVU Mersenneer

Furthermore, some of the factors found using this "method" are found in more than one "Mersenne - 1", sometimes the factors being factors of non-prime Mersennes.

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:

$2^{ab}-1=(2^a-1)\cdot \left(1+2^a+2^{2a}+2^{3a}+\cdots+2^{(b-1)a}\right)\$
(from http://en.wikipedia.org/wiki/Mersenn...ersenne_primes)
This means that the factors of 2^a-1 will also be in the factors of every 2^(ab)-1.

And, as 2^p-2=2*(2^(p-1)-1), (e.g. 2^61-2=2*(2^60-1)=2*(2^2-1)*...) you might be running in to this with your 2^p-2 numbers.
Maybe you're seeing that?

That might also explain the smoothness of 2^p-2. If p-1 is itself quite smooth (as with 60), then it will leave only very small prime factors.

R.D. Silverman · 2010-03-18, 11:26

Quote:

Originally Posted by WVU Mersenneer

I was also wondering, and forgive me if this is an ignorant question or will be answered by reading the text Dr. Silverman suggested, but I have noticed that Mersenne numbers, when subtracted by and additional 1, are always divisible by 6 and then easily divisible into other small prime factors, one of the factors always being the power of 2 used to obtain the Mersenne number.

Is this "related" in any way to the Pollard P-1 algorithm or any other legitimate algorithm, or is this just a useless coincidence upon which I stumbled?

A basic requirement for studying this subject (Number Theory) is that you
thoroughly understand basic secondary school level algebra. The
"coincidence" you discuss above results from totally trivial FIRST YEAR
algebra.

If N = 2^p-1, then N-1 = 2^p-2. Now factor this expression.
Pull out the factor of 2. What remains is trivially the difference of two
squares. You do know how to factor the difference of two squares, don't
you?

More high school algebra: You do know how to show that n(n+1)(2n+1)
is divisible by 6, don't you? (for n \in Z), This expression should be
familiar to anyone who has mastered high school level mathematics.

Now use the same technique on 2^p-2.

2010-03-17, 16:43	#30
WVU Mersenneer Mar 2010 Morgantown, WV 29₁₀ Posts	Sincere respect, appreciation, and thanks to Dr. Silverman and bsquared for the summarized yet powerful explanation and education. I will do my best to locate the text suggested and I thank you for that additional suggestion. Might I also ask what "branch" of mathematics best deals with the teachings Dr. Silverman and bsquare provided above? Perhaps I can also pick up a text book or two from the library and learn more or find the appropriate professor on campus of whom to ask further questions. I was also wondering, and forgive me if this is an ignorant question or will be answered by reading the text Dr. Silverman suggested, but I have noticed that Mersenne numbers, when subtracted by and additional 1, are always divisible by 6 and then easily divisible into other small prime factors, one of the factors always being the power of 2 used to obtain the Mersenne number. For example: (2^31 - 1) - 1 = 2,147,483,646 2,147,483,646 / 6 = 357,913,941 357,913,941 = 3 * 7 * 11 * 31 * 151 * 331 (2^89 - 1) - 1 = 618,970,019,642,690,137,449,562,110 618,970,019,642,690,137,449,562,110 / 6 = 103,161,669,940,448,356,241,593,685 103,161,669,940,448,356,241,593,685 = 5 * 17 * 23 * 89 * 353 * 397 * 683 * 2113 * 2,931,542,417 Furthermore, some of the factors found using this "method" are found in more than one "Mersenne - 1", sometimes the factors being factors of non-prime Mersennes. Is this "related" in any way to the Pollard P-1 algorithm or any other legitimate algorithm, or is this just a useless coincidence upon which I stumbled? Last fiddled with by WVU Mersenneer on 2010-03-17 at 17:01 Reason: 391 = 17 23*

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Factor a 108-digit number	sweety439	sweety439	9	2016-12-21 21:22
New 70 digit factor	R.D. Silverman	Cunningham Tables	16	2016-01-23 22:16
44-digit factor found using ECM w/ B1=1e6 & B2=1e8	WVU Mersenneer	Factoring	8	2010-04-24 17:01
Probability of n-digit factor?	roger	Factoring	3	2007-05-09 22:51
160 digit factor found of 366 digit (PRP-1)	AntonVrba	Factoring	7	2005-12-06 22:02

2010-03-17, 16:47	#31
WVU Mersenneer Mar 2010 Morgantown, WV 29 Posts	Mini-Geek, please consider yourself added to the appropriate thanks I hopefully gave to Dr. Silverman and bsquared above. I have read the links you provided dozens of times prior to posting here, and as you have assuredly already guessed, it was far above my comprehension. However, I do also appreciate your "dumbing down" those explanations for me, and I feel I can almost grasp that. Hopefully once I learn what "branch" this all falls under I can locate a book or two to study and learn more, or that I remember more from the Number Theory course I took 12 years ago. My thanks to all.