mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Wikis > Prime Wiki

Reply
 
Thread Tools
Old 2020-06-15, 13:33   #1
kar_bon
 
kar_bon's Avatar
 
Mar 2006
Germany

2×3×11×43 Posts
Default Msieve Statistical Data for factored numbers

Seeing projects like (Homogeneous) Cunningham, Brent or x^y+y^x for factoring large numbers using NFS@Home or only private crunching using Msieve, there're always log files with data almost always using pastebin to show.

What about a data collecting effort and therefore comparing such data in a tabular manner?

I've created a sample page in the Wiki for the Homogeneous Cunningham number 11^281 - 5^281 with some data only shown as text so far.
There's also a file of the msieve-log uploaded as ASCII text.
Links to the forum post and to the FactorDB data are also available.

My question:
To compare the data perhaps from the poly file, what data should be included in a template, which can hold the data and can be shown in a table with sorting/comparing?

Some years ago I've create a (now outdated) page for HCN:
Pages with such numbers using templates can be used to create reservations, wanted factorizations and overview tables to be created easily by filling such template.
And all data are available in one place.

Suggestions?

Last fiddled with by kar_bon on 2020-06-15 at 13:34
kar_bon is offline   Reply With Quote
Old 2020-06-15, 15:01   #2
Dylan14
 
Dylan14's Avatar
 
"Dylan"
Mar 2017

24×31 Posts
Default

Quote:
Originally Posted by kar_bon View Post
My question:
To compare the data perhaps from the poly file, what data should be included in a template, which can hold the data and can be shown in a table with sorting/comparing?

For a template, I'm thinking we should have similar data as shown on Makoto Kamada's website for near repunit number factorization:

  • the form of the number
  • the number written out (probably not in a table)
  • ECM depth (could be a simple as the digit level, or perhaps number of curves at some B1 value)
  • SNFS and GNFS difficulty, and highlight which one is easier
  • reservation/last update date
  • link to factordb or msieve log file (if it exists)
  • best poly e score (for poly searches done in this thread or elsewhere), or used poly e score (for a complete factorization)
Dylan14 is offline   Reply With Quote
Old 2020-06-15, 21:40   #3
kar_bon
 
kar_bon's Avatar
 
Mar 2006
Germany

B1616 Posts
Default

Are SNFS/GNFS diff. calculable? Otherwise only a parameter to fill in is possible here.

ECM depth could be collected like a list: #curves at any B1.

Reservations, dates should be standard as in other templates.

Long numbers can be written like in FactorDb: <first 10 digits>...<last 10 digits> or something if the digitlength is greater than 20 to keep a table view short.
The whole number is available via FactorDb link or in the Wiki as separate page/text.

What about the best poly or the poly taken to factor the number? E score the only important value?
kar_bon is offline   Reply With Quote
Old 2020-06-16, 04:45   #4
sweety439
 
sweety439's Avatar
 
Nov 2016

23·3·89 Posts
Default

Quote:
Originally Posted by kar_bon View Post
Are SNFS/GNFS diff. calculable? Otherwise only a parameter to fill in is possible here.

ECM depth could be collected like a list: #curves at any B1.

Reservations, dates should be standard as in other templates.

Long numbers can be written like in FactorDb: <first 10 digits>...<last 10 digits> or something if the digitlength is greater than 20 to keep a table view short.
The whole number is available via FactorDb link or in the Wiki as separate page/text.

What about the best poly or the poly taken to factor the number? E score the only important value?
Will you factorize all forms (k*b^n+c)/gcd(k+c,b-1) (k>=1,b>=2,gcd(k,c)=1,gcd(b,c)=1) (near-repdigit or quasi-repdigit numbers base b)? Also numbers n!+/-1, n!!+/-1, p#+/-1, etc. and Fibonacci(n,k) (n-th Fibonacci polynomial evaluated at x=k ?

I think you should list the primes of these forms first, then the list of the factorizations of the numbers of these forms, e.g. there are currently no primes pages "repunit b" (primes of the forms (b^p-1)/(b-1) with prime p) and "homogeneous Cunningham M a b" (primes of the form (a^p-b^p)/(a-b) with prime p) and "homogeneous Cunningham P a b" (primes of the form (a^p+b^p)/(a+b) with odd prime p) in the wiki.
sweety439 is offline   Reply With Quote
Old 2020-06-16, 04:47   #5
sweety439
 
sweety439's Avatar
 
Nov 2016

23·3·89 Posts
Default

Quote:
Originally Posted by kar_bon View Post
Are SNFS/GNFS diff. calculable? Otherwise only a parameter to fill in is possible here.

ECM depth could be collected like a list: #curves at any B1.

Reservations, dates should be standard as in other templates.

Long numbers can be written like in FactorDb: <first 10 digits>...<last 10 digits> or something if the digitlength is greater than 20 to keep a table view short.
The whole number is available via FactorDb link or in the Wiki as separate page/text.

What about the best poly or the poly taken to factor the number? E score the only important value?
I think <first 10 digits>...<last 10 digits> is ok, note that in FactorDb it is only <first 10 digits>...<last 2 digits>, which is too short, note that FactorDb shows the whole number for all numbers with digit length <= 50, but you think we should show the whole number only for the numbers with digit length <= 20 ....
sweety439 is offline   Reply With Quote
Old 2020-06-16, 04:53   #6
sweety439
 
sweety439's Avatar
 
Nov 2016

23·3·89 Posts
Default

Quote:
Originally Posted by kar_bon View Post
Are SNFS/GNFS diff. calculable? Otherwise only a parameter to fill in is possible here.

ECM depth could be collected like a list: #curves at any B1.

Reservations, dates should be standard as in other templates.

Long numbers can be written like in FactorDb: <first 10 digits>...<last 10 digits> or something if the digitlength is greater than 20 to keep a table view short.
The whole number is available via FactorDb link or in the Wiki as separate page/text.

What about the best poly or the poly taken to factor the number? E score the only important value?
Also, we should show the number of digits if the digit length is >10, e.g. for 2^1151-1, we can list 284278475807<sub>12</sub> * 81344898763887260484533897<sub>26</sub> * 658622107254745112979229913<sub>27</sub> * 391462657172...695585290297<sub>41</sub> * 831191943103...100663804047<sub>103</sub> * 617195483481...843075029479<sub>139</sub>
sweety439 is offline   Reply With Quote
Old 2020-06-16, 07:05   #7
kar_bon
 
kar_bon's Avatar
 
Mar 2006
Germany

2×3×11×43 Posts
Default

sweety439:
- learn how to quote a post or even don't: 3 posts with same quoting in 8 minutes is redundant, you can edit your posts in a 5 minute period when send
- stop talking about 'we/we should', as almost always in your posts and stop asking people do something
- I will not factorize any number in the Wiki, I try to collect and show data for factoring efforts
- I can't implement any type of number you given, this is not doable
- Why should I create pages for the form (a^p+b^p)/(a+b), if the general form a^p+b^p is the same with small factors included? Specialising is more work to do.
- This thread is a first sight for collecting suggestions and nothing yet done in this direction in the Wiki. Perhaps only links to the FactoDB are better than doing the same as there like listing all factors. Keep in mind: someone has to keep those pages current.
kar_bon is offline   Reply With Quote
Old 2020-06-16, 14:15   #8
Dylan14
 
Dylan14's Avatar
 
"Dylan"
Mar 2017

24×31 Posts
Default

I'll try to answer each of kar_bon's questions in turn.

Quote:
Originally Posted by kar_bon View Post
Are SNFS/GNFS diff. calculable? Otherwise only a parameter to fill in is possible here.
GNFS difficulty appears to be simple to calculate: it's the log base 10 of the composite to be factored (for example the composite here) has GNFS difficulty 162.77 which corresponds to the (rounded) log 10 of the composite.
For SNFS the difficulty is based on the original number (so for the number I just mentioned it's ~189.72). Of course, whether SNFS or GNFS is quicker depends on a number of factors (factors found previously, degree of the SNFS polynomial, etc.).

Showing all curves makes sense - although perhaps in a table it's a bit too much to show - maybe just show the highest B1 curves, and then on the page show all curves known.
For showing the number - I thought some more about it, and since we can find the number elsewhere, it would seem redundant to show the full form in a table. Besides, if the number has a numerical form, then one could calculate it. But what about numbers that don't have that, or depend on the previous number's factors (home primes and aliquot sequences)?

Quote:
Originally Posted by kar_bon View Post
What about the best poly or the poly taken to factor the number? E score the only important value?
E score tends to be an indication of the quality of the polynomial - the higher it is, the better (in general) - which means you'll get more relations per range of Q's. Although if two polynomials are close in E-value, then by score alone it's not enough - one must do test sieving.
There are also anorm and rnorm scores which can be seen by using the poly generator on cownoise. But this appears only for Cunningham numbers, Brent numbers and OPN's - I am not sure how this would be calculated for other, more general numbers. At least one can test both sides (algebraic and rational) to see which one sieves better.
I'm sure someone with more experience (VBCurtis, EdH, RDS) would have more information on the e score.
Dylan14 is offline   Reply With Quote
Old 2020-06-16, 14:45   #9
sweety439
 
sweety439's Avatar
 
Nov 2016

1000010110002 Posts
Default

Quote:
Originally Posted by Dylan14 View Post
GNFS difficulty appears to be simple to calculate: it's the log base 10 of the composite to be factored (for example the composite here) has GNFS difficulty 162.77 which corresponds to the (rounded) log 10 of the composite.
Why base 10? Not base 2?
sweety439 is offline   Reply With Quote
Old 2020-06-16, 15:00   #10
Dylan14
 
Dylan14's Avatar
 
"Dylan"
Mar 2017

24×31 Posts
Default

The reason why it’s base 10 is because all pages give the difficulty in terms of digits, which is base 10. Same with the rule of thumb with GNFS (increasing the difficulty by 5-6 digits doubles the factoring effort). One can simply convert over to base 2 difficulty simply by multiplying the base 10 value by log(10)/log(2). Although I don’t see why you want to do that.
Dylan14 is offline   Reply With Quote
Old 2020-06-16, 15:56   #11
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

5×7×112 Posts
Default

Quote:
Originally Posted by Dylan14 View Post
There are also anorm and rnorm scores which can be seen by using the poly generator on cownoise. But this appears only for Cunningham numbers, Brent numbers and OPN's - I am not sure how this would be calculated for other, more general numbers. At least one can test both sides (algebraic and rational) to see which one sieves better.
I'm sure someone with more experience (VBCurtis, EdH, RDS) would have more information on the e score.
I am flattered for the shoutout, but EdH and I are merely button-pushers, not mathematicians. Thank you, all the same.
I am very interested in collecting data about anorm and rnorm values- the literature and the smart people around here indicate that lim's and LP values should be chosen based somewhat on those values, but I have never done so- I just guess and iterate over what finds speed. If that data is gathered for SNFS jobs, I feel like I'll personally gain insight into possible parameter choices that may find speed (e.g. when to try a larger lim or more unbalanced lim choice than standard practice).
VBCurtis is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Condition on composite numbers easily factored (Challenger) baih Factoring 1 2019-10-10 11:14
Condition on composite numbers easily factored baih Factoring 16 2019-09-29 15:48
Runs of factored numbers henryzz Factoring 8 2017-03-09 19:24
Use Msieve NFS for small numbers? skan Msieve 8 2013-02-26 20:35
Same team factored RSA challenge numbers in recent time koders333 Factoring 12 2006-03-31 16:06

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

Mon Aug 3 09:10:30 UTC 2020 up 17 days, 4:57, 0 users, load averages: 1.12, 1.10, 1.09

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.