mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2010-05-30, 22:38   #1
Karl M Johnson
 
Karl M Johnson's Avatar
 
Mar 2010

3×137 Posts
Default Which poly to use?

Howdy, folks. So I decided to factor RSA-100.Again.
I got 2 Polys using Msieve 1.45 with a CUDA GPU.

Here's first:
Code:
N 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139
SKEW 554753.83
R0 -532756497435146513887571
R1  103288101097409
A0  6146189103866429094136080
A1 -308188141461002143706
A2 -28188889873255477
A3  2347896070
A4  18900
Second:
Code:
N 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139
SKEW 900108.23
R0 -635116372672313959258675
R1  91841463772921
A0  2510713546966177126893631144
A1  5674926898539175329782
A2 -10050582327235661
A3 -15172642638
A4  9360
Now, the question is, which one is better to use?
And, how can I tell it's better?

Karl.
Karl M Johnson is offline   Reply With Quote
Old 2010-05-31, 01:31   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

2×23×197 Posts
Default

The first one is a bit better:
it has larger norm, larger (in abs.value) alpha, and larger Murpy E score.

p1: skew 554753.83, size 1.511335e-13, alpha -5.390549, combined = 1.409e-08
p2: skew 900108.23, size 1.389628e-13, alpha -5.127882, combined = 1.383e-08
Batalov is offline   Reply With Quote
Old 2010-05-31, 08:17   #3
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

2×23×197 Posts
Default

I found a slightly better poly:
Code:
# norm 1.472430e-013 alpha -5.486015 e 1.429e-008
skew: 894207.14
c0:  258649450348138371326825455
c1:  5399499758071374808669
c2:  11401030669362863
c3: -10289778325
c4:  3450
Y0: -815128765602942897511404
Y1:  86029790665901
(and yes, this c4 doesn't divide by 60 )
Batalov is offline   Reply With Quote
Old 2010-05-31, 09:53   #4
Karl M Johnson
 
Karl M Johnson's Avatar
 
Mar 2010

3·137 Posts
Default

I bet that poly was found using GGNFS.
I wasnt able to get poly.exe running from that suite.
It crashed right after initialization.
Karl M Johnson is offline   Reply With Quote
Old 2010-06-01, 15:26   #5
Karl M Johnson
 
Karl M Johnson's Avatar
 
Mar 2010

6338 Posts
Default

What is a "degree" of a polynominal?
GGNFS polyselector didnt want to start untill I specified the degree.

I try to use GGNFS siever(gnfs-lasieve4I13e.exe) for sieving phase.
Here's how rsa100.poly looks like:
Code:
name: rsa100
n: 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139
Y0: -532756497435146513887571
Y1: 103288101097409
c0: 6146189103866429094136080
c1: -308188141461002143706
c2: -28188889873255477
c3: 2347896070
c4: 18900
skew: 554753.83
type: gnfs
Now, when I try to feed it to gnfs-lasieve4I13e.exe) , it says "Please set all bounds to reasonable values!"
Now, why is that?How can I fix it?
Karl M Johnson is offline   Reply With Quote
Old 2010-06-01, 16:17   #6
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2×52×127 Posts
Default

Quote:
Originally Posted by Karl M Johnson View Post
Now, when I try to feed it to gnfs-lasieve4I13e.exe) , it says "Please set all bounds to reasonable values!"
Now, why is that?How can I fix it?
You need to set the eight bounds: alim, rlim, lpbr, lpba, mfbr, mfba, alambda, rlambda. The factMsieve.pl script encodes a fair amount of the knowledge we have on how to set these bounds for numbers of different sizes; for 100 digits, alim=rlim=2000000, lpbr=lpba=24 should be about right. And in general alambda=rlambda=2.6 and mfbr=2*lpbr, mfba=2*lpba seem to work well.
fivemack is offline   Reply With Quote
Old 2010-06-01, 17:25   #7
Karl M Johnson
 
Karl M Johnson's Avatar
 
Mar 2010

3×137 Posts
Default

Thanks Tom for the advice.

Is there a way to feed a poly to factmsieve.py script?

Last fiddled with by Karl M Johnson on 2010-06-01 at 17:30
Karl M Johnson is offline   Reply With Quote
Old 2010-06-01, 17:39   #8
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

13·19·23 Posts
Default

just put the stuff in post 5 into a file with extension .poly
henryzz is offline   Reply With Quote
Old 2010-06-01, 17:43   #9
Karl M Johnson
 
Karl M Johnson's Avatar
 
Mar 2010

3×137 Posts
Default

Results in
Code:
C:\Program Files (x86)\msieve\ggnfs\example>factmsieve.py example.poly
-> ________________________________________________________________
-> | Running factmsieve.py, a Python driver for MSIEVE with GGNFS |
-> | sieving support. It is Copyright, 2010, Brian Gladman and is |
-> | a conversion of factmsieve.pl that is Copyright, 2004, Chris |
-> | Monico.  Version 0.68 (Python 2.6 or later) 24th April 2010. |
-> |______________________________________________________________|
-> This is client 1 of 1
-> Using 4 threads
-> Working with NAME = example
Could not find default parameter file ../def-par.txt!

Last fiddled with by Karl M Johnson on 2010-06-01 at 17:43
Karl M Johnson is offline   Reply With Quote
Old 2010-06-01, 18:32   #10
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

13·19·23 Posts
Default

Quote:
Originally Posted by Karl M Johnson View Post
Results in
Code:
C:\Program Files (x86)\msieve\ggnfs\example>factmsieve.py example.poly
-> ________________________________________________________________
-> | Running factmsieve.py, a Python driver for MSIEVE with GGNFS |
-> | sieving support. It is Copyright, 2010, Brian Gladman and is |
-> | a conversion of factmsieve.pl that is Copyright, 2004, Chris |
-> | Monico.  Version 0.68 (Python 2.6 or later) 24th April 2010. |
-> |______________________________________________________________|
-> This is client 1 of 1
-> Using 4 threads
-> Working with NAME = example
Could not find default parameter file ../def-par.txt!
is def-par.txt in the ggnfs directory?
also permissions probably wont be right in programfiles in either vista or windows 7
we have learnt to avoid it like the plague here
henryzz is offline   Reply With Quote
Old 2010-06-01, 18:56   #11
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

2×23×197 Posts
Default

Quote:
Originally Posted by Karl M Johnson View Post
I bet that poly was found using GGNFS.
I wasnt able to get poly.exe running from that suite.
It crashed right after initialization.
No, polyselect only searches a subspace with Y1=1, so it is not competitive here. Interesting historically, but otherwise now msieve is what you want to use for any degree. (Unless you have access to close-source software.)

Here's how the funny looking poly was found. I recompiled msieve_gpu with MULTIPLIER relaxed to 30, ...and later to 2 (and then I found a poly with c4=72, e=1.438e-08; this is probably as good a poly as it gets. Your standard polys were also reported, rank #3,4. This was done out of curiosity. Bottom line: this trick steals from the speed of search and the increment in the poly is insignificant. Also, with a difference in E so small, I won't be surprised if a test sieving would rerank these polys, anyway).
Batalov is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Poly search candidates schickel Msieve 32 2013-11-05 19:11
Good enough poly for c155? theuser Msieve 4 2012-10-07 09:00
GNFS poly selection frmky Factoring 14 2012-07-23 01:57
Can someone run a couple of poly searches for me? schickel Msieve 12 2012-05-25 03:45
poly selection in MPQS bsquared Factoring 3 2007-02-28 14:22

All times are UTC. The time now is 09:16.

Tue Jul 14 09:16:31 UTC 2020 up 111 days, 6:49, 0 users, load averages: 1.02, 1.24, 1.27

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