mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > GMP-ECM

Reply
 
Thread Tools
Old 2006-11-30, 12:01   #1
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

19·181 Posts
Default

Quote:
Since we don't know which sigma values are going to be lucky in finding factors (because we don't know what the factors are!), implementations of ECM select the sigma value at random.
If a factor is known can the sigma be calculated that will produce that factor? Not much use, I'm just curious if that is how it works.
ATH is offline   Reply With Quote
Old 2006-11-30, 12:29   #2
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

149710 Posts
Default

Quote:
Originally Posted by ATH View Post
If a factor is known can the sigma be calculated that will produce that factor? Not much use, I'm just curious if that is how it works.
I read that it is possible. But if you can also select the number to factor, you can make ECM find huge factors. Quoting from Richard Brent's Web site:

Quote:
Originally Posted by http://wwwmaths.anu.edu.au/~brent/ftp/champs.txt
I reserve the right to exclude factorizations that were possibly obtained by "artificial" means. See for example Research Problem 7.27 of the book "Prime Numbers: a Computational Perspective" by Crandall and Pomerance.
David Broadhurst has shown that this enables us to concoct examples where ECM finds factors of over 30,000 decimal digits!

Last fiddled with by alpertron on 2006-11-30 at 12:30
alpertron is offline   Reply With Quote
Old 2006-11-30, 12:34   #3
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

For a given prime p, you can construct a curve of any order in the Hasse interval around p by a technique called Complex Multiplication. That is, I think to construct any valid order you may need to define the curve over an algebraic closure of GF(p), I'm not sure. Afaik, "usually" it works over GP(p) as well. This will give you the curve parameters, i.e. for a curve in Weierstraß form, the a and b parameters. Curves in Montgomery parameterisation are a subset of the curves in Weierstraß form, so not every curve generated by Complex Multiplicaion may be suitable for converting to Montgomery form. Furthermore, generating a curve in Montgomery form from the sigma value is not a bijective function either, so even for a valid curve in Montgomery form there may not be a suitable sigma value. If there is, the sigma value will be very large, more or less a random value (mod p).

I think David Broadhurst did some experimenting with producing "fake" ECM sucesses by constructing curves with Complex Multiplication. Iirc, he managed to make ECM "find" factors >1000 digits that way, but usually the size of the sigma value gave them away, as the random number generator we use in GMP-ECM chooses sigma <2^32.

Alex
akruppa is offline   Reply With Quote
Old 2006-11-30, 12:50   #4
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

46438 Posts
Default

Here is a posting of David Broadhurst to the NMBRTHRY mailing list on the subject:

Quote:
Originally Posted by David Broadhurst on NMBRTHRY
Richard Brent asked me if I could contrive to make GMP-ECM
extract a large prime factor, for example p > 1074,
with a much smaller seed, for example sigma < 232.

Construction [CM with squares in order]: Let
f(x) = (8*(x-5)4 + (x-1)2*(x-25)2)/211
g(x) = (x-1)2*(8*(x-9)2 + (x-25)2)/211
If sigma is odd and p = f(sigma2) is prime, then the curve
of Crandall and Pomerance Theorem 7.4.3 has complex
multiplication with discriminant D = -8 and order
#E(F_p) = g(sigma2).

GMP-ECM, when run with limits B1 and B2, will factorize a
composite input divisible by p if #E(F_p) is of the form C*q
where no prime power in C exceeds B1 and q is an outlying
prime that does not exceed B2.

Amusingly, extraction of p > 1074, with sigma < 232, can now
be accomplished when the order contains both B12 and B22:
http://lists.fousse.info/pipermail/e...er/000388.html

Note that the construction allows us to "forge" a GMP-ECM
factorization that appears to be a "champ" (as defined by
Richard Brent) but is in fact a "chimp" (a term coined by
Bouk de Water) that may be found by demanding smoothness of
8*(sigma2-32)2 + (sigma2-52)2 \approx 96*sqrt(2*p)
and primality of p = f(sigma2).

For example, the seed sigma = 4278674929 will factorize
c175 = p75*p101 = f(sigma2)*(2333+285) in 5 seconds:

Using B1=128657, B2=53194859, polynomial x2, sigma=4278674929
Step 1 took 3000ms
Step 2 took 1720ms
Found probable prime factor of 75 digits:
493613348917766417426006591803225943649556875046256846631045789294232301761

For extraction of a p74 without a large square in the order, see
http://lists.fousse.info/pipermail/e...er/000380.html
which exploits complex multiplication with D = -3 for a prime p dividing
the numerator of 3*(u3+u)2 - (3*u2-1)2, with u = (sigma2-5)/(4*sigma)
and sigma = 9344229. The Cornacchia-Smith algorithm then gives
#E(F_p) = 26*33*37*397*601*787*25183*68881*1257463*2020663*113756239
*176982499*496654231*33145894274179 and GMP-ECM factors p74*p89 in 8 hours.

Of course, these games pale into insignificance when compared
with the amazing true "champs" in
http://wwwmaths.anu.edu.au/~brent/ftp/champs.txt

I thank Richard Brent, Alex Kruppa, Bouk de Water and Paul Zimmermann
for their encouragement.

David Broadhurst
Alex

Last fiddled with by akruppa on 2006-11-30 at 12:53 Reason: Moved to separate thread, CM isn't a beginners question at all!
akruppa is offline   Reply With Quote
Old 2006-11-30, 23:10   #5
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

668610 Posts
Default

I see no reason why this can't also be a challenge for people to "make" the largest factors using a small sigma. As long a people don't try to misrepresent the result as "real" factors then it could be fun to try generating huge factors. We might even learn something of mathematically interesting in the process.
retina is offline   Reply With Quote
Old 2006-12-01, 15:44   #6
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

I don't see much of a challenge here... David showed that it is possible to fake record ECM factors that are indistinguishable from the real thing. What would even larger fakes prove? CM is greatly refined and studied in detail for Elliptic Curve Primality Proving, and imho that's where it makes sense to invest the effort.

Alex
akruppa is offline   Reply With Quote
Old 2006-12-01, 16:02   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

165248 Posts
Default

Quote:
Originally Posted by retina View Post
I see no reason why this can't also be a challenge for people to "make" the largest factors using a small sigma. As long a people don't try to misrepresent the result as "real" factors then it could be fun to try generating huge factors. We might even learn something of mathematically interesting in the process.
I doubt it. Here is (IMO) a better challenge:

Be the first to find a 70 digit factor of a Cunningham number via ECM.
R.D. Silverman is offline   Reply With Quote
Old 2006-12-01, 19:58   #8
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

27318 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
I doubt it. Here is (IMO) a better challenge:

Be the first to find a 70 digit factor of a Cunningham number via ECM.
... using only one computer. That's a real challenge.
alpertron is offline   Reply With Quote
Old 2006-12-01, 20:11   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

22×1,877 Posts
Default

Quote:
Originally Posted by alpertron View Post
... using only one computer. That's a real challenge.

And that's a real understatement!!!!
R.D. Silverman is offline   Reply With Quote
Old 2006-12-01, 20:15   #10
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

101110110012 Posts
Default

If I instruct one thousand computers with multiple cores to run random curves in all remaining Cunningham numbers, one of them will eventually find the 70-digit or larger factor. Where is the merit?
alpertron is offline   Reply With Quote
Old 2006-12-02, 06:33   #11
bdodson
 
bdodson's Avatar
 
Jun 2005
lehigh.edu

210 Posts
Default wondering, too

Quote:
Originally Posted by alpertron View Post
If I instruct one thousand computers with multiple cores to run random curves in all remaining Cunningham numbers, one of them will eventually find the 70-digit or larger factor. Where is the merit?
Uhm, let's count. C. 750 fast xps, 110 Opterons, 90 old P3's comes to
950, but that's including dual cpus, counted as 2; 50 short and no
multiple cores. Not counting 30 xeons and macs running NFSNET. For
one thing, the scheduling software running the xps --- U Wisc's condor --
clearly isn't quite up to the task yet; we're hoping the new core due
over the semester break is more robust. I can assure you that it isn't
a case of submitting the number of expected curves and waiting!

For one, the gmp-ecm-6.1 README doesn't even go up to 70; stops
at 65-digits. Same for Alex's -v. The old gmp-ecm-5.0 gives the optimal
b1 = 2,700,000,000 for p70 (with 850M for p65), and (with a smaller
default b2 than 6.1 would use), 120,000 curves. So the first problem
you'll have is that these type of commodity chips don't come with enough
memory to run even 850M, much less 2700M. I have 250Mb on the P3s
and c. 300 of the xps; 500Mb on the other 450 xp; 1Gb/cpu on the
Opterons. That gets me to 250-digits with b1 = 260M (p60-optimal) on
the Opterons; and b1=43M on the xps and P3s. Our expensive machine
has 128Gb for 32 Itanium2's, so just 4Gb/cpu --- I tried 850M there for
a while, with step1 on the (faster) Opterons, to best use the expensive
memory in step 2's. Just on c175-c185 to get more curves. Too labor
intensive. Looks like 15K curves, all told.

So that's probably a second point; you'd do better dropping the c251-c366's
anyway, something like 1/3 of the 850 on the current list. If you're going to
find a p70, you'd want to have it meet Brent's restriction, so that means
droping numbers under c150, or so (hardly any of them anyway, headed
towards 2*t50 soon). But it's worse than that, if you found a p70 in
a c170, someone would likely point out that you'd have done better using
gnfs; so probably you'd do better staying in the range c200-c250. Uhm,
well, I'm just finishing a run on c195-c233, something like 230 numbers out
of the 850. No p7x's yet. Looks like 300K curves with b1=260M (p60
optimal). Supposed to be enough for a p65; found a p67.

Next problem is that -- if you're spending this amount of cputime -- you
most likely would want to make sure to get something for the effort.
Grinding on the above 230-numbers might make best sense for an ecm
p7x, but there are still p4x's left in c250-c366 --- Brent's claim was/is
that one might justify at most 10% of an ecm effort on looking for
champion factors (viz his p40 from F10). I found myself rather annoyed
that people were running snfs and finding p47; and am somewhat happier
that small factors these days have been p52-p54, instead of p4x's. So
that argues for time on numbers that aren't in what I'd consider best
p7x range.

bdodson (ecm records: p57, p59, p66 and p67, so far)
bdodson is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
the unit circle, tangens and the complex plane bhelmes Math 0 2018-03-04 18:50
Basic Number Theory 10: complex numbers and Gaussian integers Nick Number Theory Discussion Group 8 2016-12-07 01:16
radius of convergence of a complex power series wildrabbitt Math 3 2016-08-16 08:38
Complex, but deceptively simple question about Prime95 failures? halcion Software 6 2004-12-16 20:10
Complex number problem dave_0273 Math 3 2004-11-08 17:15

All times are UTC. The time now is 22:21.


Tue Feb 7 22:21:29 UTC 2023 up 173 days, 19:50, 1 user, load averages: 1.26, 1.23, 1.19

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔