mersenneforum.org  

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

Reply
 
Thread Tools
Old 2022-09-18, 01:54   #1
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

22·43·47 Posts
Default ECM group order mystery

Can anyone explain this:

Prime95 reports this:

ECM found a factor in curve #288, stage #2
Sigma=8055078829352661, B1=1000000, B2=2842011315.
UID: xxx, M257189 has a factor: 9076380491288497374472490688721 (ECM curve 288, B1=1000000, B2=2842011315)

Error message from factordb:
Err: Calculated grouporder 9076380491288499231237040277748<31> is not within B1/B2 bounds (B1=1000000, B2=2842011315). Please check your result!

factorization of the group order is (please notice the exceeded B1):
9076380491288499231237040277748<31> = 2^2 · 3^2 · 719 · 967 · 3613543 · 100350976151081387<18>
Prime95 is offline   Reply With Quote
Old 2022-09-18, 06:07   #2
axn
 
axn's Avatar
 
Jun 2003

542710 Posts
Default

Quote:
Originally Posted by Prime95 View Post
Can anyone explain this:
Is the computation repeatable with the same sigma? Perhaps the sigma got corrupted -- either during printing or during computation?

FWIW, Pari agrees with factordb
Code:
ecmgroup(p, s)={
my(v,u,x,b,a,A,E);
s=Mod(s,p);
v=4*s;
u=s^2-5;
x=u^3;
b=4*x*v;
a=(v-u)^3*(3*u+v);
A=a/b-2;
x=x/v^3;
b=x^3+A*x^2+x;
E=ellinit([0,b*A,0,b^2,0]);
ellgroup(E)
}
p=9076380491288497374472490688721;
s=8055078829352661;
ecmgroup(p,s)
[9076380491288499231237040277748]
axn is offline   Reply With Quote
Old 2022-09-18, 18:13   #3
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

2×7×181 Posts
Default

Assuming ecm -param 3 gives a group order of
9076380491288497514442256285656<31> = 2^3 · 3 · 13^2 · 9887 · 863843 · 262008508458197461<18>
That's within B1 but significantly exceeds B2.
frmky is offline   Reply With Quote
Old 2022-09-18, 18:23   #4
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

22×43×47 Posts
Default

Quote:
Originally Posted by axn View Post
Is the computation repeatable with the same sigma?
I could not reproduce the computation. I'll ask user xxx to try.

Corruption of the sigma value is possible -- though it seems unlikely. Corruptions usually result in crashes or incorrect results -- this time a corruption occurred and a factor was still found. But, I have no other explanation.
Prime95 is offline   Reply With Quote
Old 2022-09-18, 18:51   #5
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

2D4016 Posts
Default

Quote:
Originally Posted by Prime95 View Post
I could not reproduce the computation. I'll ask user xxx to try.

Corruption of the sigma value is possible -- though it seems unlikely. Corruptions usually result in crashes or incorrect results -- this time a corruption occurred and a factor was still found. But, I have no other explanation.
I wouldn't spend too much effort investigating it myself. It is interesting, but as long as the factor is valid, who cares in the end?
xilman is offline   Reply With Quote
Old 2022-09-19, 00:01   #6
bbb120
 
"特朗普trump"
Feb 2019
朱晓丹没人草

8416 Posts
Default

Quote:
Originally Posted by Prime95 View Post
Can anyone explain this:

Prime95 reports this:

ECM found a factor in curve #288, stage #2
Sigma=8055078829352661, B1=1000000, B2=2842011315.
UID: xxx, M257189 has a factor: 9076380491288497374472490688721 (ECM curve 288, B1=1000000, B2=2842011315)

Error message from factordb:
Err: Calculated grouporder 9076380491288499231237040277748<31> is not within B1/B2 bounds (B1=1000000, B2=2842011315). Please check your result!

factorization of the group order is (please notice the exceeded B1):
9076380491288499231237040277748<31> = 2^2 · 3^2 · 719 · 967 · 3613543 · 100350976151081387<18>
why you cannot reproduce the computation since you have the sigma and B1 and B2?
and it is really very interesting (B2<<100350976151081387<18>)

Last fiddled with by bbb120 on 2022-09-19 at 00:02
bbb120 is offline   Reply With Quote
Old 2022-09-19, 00:11   #7
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

556010 Posts
Default

If we knew why, we wouldn't have a mystery now, would we?
VBCurtis is offline   Reply With Quote
Old 2022-09-19, 10:06   #8
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

32·137 Posts
Default

This has happened to me before and I also recall someone else mentioning it on the forum (starting from post #7). So this is not an one-off.
kruoli is online now   Reply With Quote
Old 2022-09-19, 12:22   #9
Neptune
 
Jul 2022

3·7 Posts
Default

Looking at the parameterization of the curve between line 3232 and 3305 in ecm.cpp (version 30.8b15):

u = sig2 - 5
v = 4sig;
x = u3
z = v3
An = (v - u)3 (3u + v)
Ad4 = 4u3 v

seems all OK to me up to here, but for:

/* Normalize so that An is one */ <line 3283>
Ad4 = Ad4 ( (1 / An) % n)
Ad4 = 4Ad4

I'm not sure about.
Ad4 the former denominator now becomes the (normalized) numerator.

Suggestion:
Montgomery form requires A24 = (A + 2) / 4 (which can be of course precalculated).
As Suyama Parameterization already substracts A = A-2 in the last step we can ommit A-2 / A+2
and multiply the denomintaor Ad4 with four. Then one normalization in the last step to get the right parameterization:

u = sig2 - 5
v = 4sig;
x = u3
z = v3
An = (v - u)3 (3u + v)


all as above but now:
Ad4 = 16u3 v
and
/* Normalize so that Ad4 is one */
Ad4 = An ( (1 / Ad4) % n)

That's all nothing more needs to be changed.

Last fiddled with by Neptune on 2022-09-19 at 12:25 Reason: clarification. Btw how much time do i have for editing ? Need endless :)
Neptune is offline   Reply With Quote
Old 2022-09-19, 13:33   #10
axn
 
axn's Avatar
 
Jun 2003

34·67 Posts
Default

Quote:
Originally Posted by Prime95 View Post
Corruptions usually result in crashes or incorrect results -- this time a corruption occurred and a factor was still found.
Technically, finding a factor when it is not supposed to /is/ an incorrect result.

I just searched nearby values for sigmas that work. s+18 and s+2^168 (1-bit hamming distance) work. Of course it proves nothing. If we search enough sigmas, we'll get some that work.
axn is offline   Reply With Quote
Old 2022-09-19, 22:11   #11
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

5·683 Posts
Default

GMP-ECM does not find it with that sigma:

Code:
ecm.exe -c 1 -v -savea M257189out.txt -maxmem 12000 -sigma 8055078829352661 1e6 2842011315 < M257189.txt
GMP-ECM 7.0.5-dev [configured with GMP 6.2.1, --enable-asm-redc] [ECM]
Input number is 2^257189-1 (77422 digits)
Using special division for factor of 2^257189-1
Using B1=1000000, B2=2842011315, polynomial Dickson(6), sigma=0:8055078829352661
dF=6720, k=6, d=66990, d2=13, i0=2
Expected number of curves to find a factor of n digits (assuming one exists):
35      40      45      50      55      60      65      70      75      80
749     6987    78397   1016542 1.5e+07 2.5e+08 4.8e+09 1.1e+11 8.5e+15 1.1e+21
Step 1 took 10437781ms
Estimated memory usage: 10.27GB
Initializing tables of differences for F took 26937ms
Computing roots of F took 247094ms
Building F from its roots took 338281ms
Computing 1/F took 99125ms
Initializing table of differences for G took 49281ms
Computing roots of G took 219203ms
Building G from its roots took 342281ms
Computing roots of G took 223500ms
Building G from its roots took 342797ms
Computing G * H took 65703ms
Reducing  G * H mod F took 106078ms
Computing roots of G took 224125ms
Building G from its roots took 341438ms
Computing G * H took 65344ms
Reducing  G * H mod F took 105906ms
Computing roots of G took 223250ms
Building G from its roots took 340969ms
Computing G * H took 65625ms
Reducing  G * H mod F took 105781ms
Computing roots of G took 222906ms
Building G from its roots took 341360ms
Computing G * H took 65469ms
Reducing  G * H mod F took 106062ms
Computing roots of G took 222500ms
Building G from its roots took 341406ms
Computing G * H took 65421ms
Reducing  G * H mod F took 105641ms
Computing polyeval(F,G) took 544062ms
Computing product of all F(g_i) took 18641ms
Step 2 took 5568125ms
Expected time to find a factor of n digits:
35      40      45      50      55      60      65      70      75      80
138.67d 3.55y   39.79y  515.94y 7648y   126232y 2e+06y  6e+07y  4e+12y  6e+17y
Peak memory usage: 7738MB
ATH is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Group order not accepted for some GMP-ECM factors? rwwh FactorDB 2 2015-06-19 06:26
ECM curve group order Brain Miscellaneous Math 1 2010-12-08 01:00
What is this group? wpolly Math 1 2008-06-09 12:14
how to join a group gian92 Software 0 2008-02-22 21:08
Lie group E8 mapped ixfd64 Lounge 13 2007-03-23 15:06

All times are UTC. The time now is 10:03.


Thu Dec 8 10:03:35 UTC 2022 up 112 days, 7:32, 0 users, load averages: 0.90, 1.03, 1.04

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

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