mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2011-01-22, 00:21   #1
davar55
 
davar55's Avatar
 
May 2004
New York City

23×232 Posts
Default Yet another basic-factoring-questions thread

Perhaps you could transfer him some of yours.
davar55 is offline   Reply With Quote
Old 2011-01-22, 18:39   #2
davar55
 
davar55's Avatar
 
May 2004
New York City

423210 Posts
Default

Quote:
Originally Posted by xilman View Post
People: do you really think Nicolas and I haven't tried to factor that p210? Have a go at it if you wish, but you are very likely not to find small factors.
Nicolas has run P-1 to b1=100G and P+1 to B1=10G. Between us we've run enough ECM to be pretty sure that there are no factors under 40 digits. Our ECM efforts are continuing because a c210 is far beyond what we can manage between us.
Just a convenient place to ask:

What do b1 and B1 bounds refer to in
their respective P-1 and P+1 factoring programs?

How sure is pretty sure?


Who if anyone can manage a C210 at this point?
Could anyone manage a C1000 right now?

You don't have to give away anything you don't want to.
davar55 is offline   Reply With Quote
Old 2011-01-22, 19:01   #3
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default Yet another basic-factoring-questions thread

Quote:
Originally Posted by davar55 View Post
What do b1 and B1 bounds refer to in
their respective P-1 and P+1 factoring programs?
Quote:
Originally Posted by Mini-Geek View Post
P-1 and P+1 can find a factor P of a number N when P-1 or P+1 is smooth to certain bounds.
One of these bounds is called B1, the other is B2. b1 and B1 are the same. Put simply, to find the factor P, P-1 or P+1 must be smooth to B1, except for at most one factor, which must be smooth to B2.
Quote:
Originally Posted by davar55 View Post
Could anyone manage a C1000 right now?
No. At least, not to definitely be able to factor it, as in factoring with SNFS or GNFS. It is possible for people to look for small factors of a C1000 or larger, and in some cases these might completely factor the number, but that's not the same. You can see the records for integer factorization here, the largest done yet for general and special forms are 232 and 313 digits, respectively.

Last fiddled with by Mini-Geek on 2011-01-22 at 19:04
Mini-Geek is offline   Reply With Quote
Old 2011-01-22, 19:13   #4
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

101001010110112 Posts
Default

Quote:
Originally Posted by davar55 View Post
Just a convenient place to ask:

What do b1 and B1 bounds refer to in
their respective P-1 and P+1 factoring programs?

How sure is pretty sure?


Who if anyone can manage a C210 at this point?
Could anyone manage a C1000 right now?

You don't have to give away anything you don't want to.
b1 and B1 are the same quantity. It usually has an uppercase letter and "b1" was probably a (harmless) error.

B1 in P-1, P+1 and ECM indicated that every prime power e <= B1 has been included in the computation of a^x where x = Product e. a is the initial value and arithmetic is performed in the appropriate ring.

I estimate that the probability pf finding a factor under 40 digits is below 1%, given the amount of computation already performed. I can't give a more precise estimate because I don't know how much work has been done.


Factoring a general 210-digit composite could be done by at most a few (<5) teams known to be currently active in the field. Finding out who those people are is left as a simple exercise in the use of Google or the search engine of your choice.

State of the art is <250 digits for a general composite. 1000 digits is likely to be inaccessible for a very long time unless there is a major breakthrough in theory. I have a bet open with RDS that 310 digits will be achievable before 2020. Even if I win the bet, I doubt I will collect much more than 2 years ahead of the deadline.

Paul

Last fiddled with by xilman on 2011-01-22 at 19:15
xilman is offline   Reply With Quote
Old 2011-01-22, 19:16   #5
davar55
 
davar55's Avatar
 
May 2004
New York City

23·232 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
One of these bounds is called B1, the other is B2. b1 and B1 are the same. Put simply, to find the factor P, P-1 or P+1 must be smooth to B1, except for at most one factor, which must be smooth to B2.

No. At least, not to definitely be able to factor it, as in factoring with SNFS or GNFS. It is possible for people to look for small factors of a C1000 or larger, and in some cases these might completely factor the number, but that's not the same. You can see the records for integer factorization here, the largest done yet for general and special forms are 232 and 313 digits, respectively.
OK since I'm still catching up, a few more questions, if it's OK.

Is SNFS the Special Number Factor Sieve?
Is GNFS the General Number Factor Sieve?

What's special about those special numbers? Are they a^b +/- c ?

What's general about those general numbers? (I know there's
a long answer to that question, but I'd be glad for a good short one).

That's all I've got for now .....
davar55 is offline   Reply With Quote
Old 2011-01-22, 19:22   #6
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

426710 Posts
Default

Quote:
Originally Posted by davar55 View Post
OK since I'm still catching up, a few more questions, if it's OK.

Is SNFS the Special Number Factor Sieve?
Is GNFS the General Number Factor Sieve?

What's special about those special numbers? Are they a^b +/- c ?

What's general about those general numbers? (I know there's
a long answer to that question, but I'd be glad for a good short one).

That's all I've got for now .....
Finish reading this earlier reply and at least glance at the link(s) that are relevant to your current questions:
http://www.mersenneforum.org/showthr...734#post247734

Last fiddled with by Mini-Geek on 2011-01-22 at 19:22
Mini-Geek is offline   Reply With Quote
Old 2011-01-22, 19:27   #7
davar55
 
davar55's Avatar
 
May 2004
New York City

23·232 Posts
Default

Quote:
Originally Posted by xilman View Post
b1 and B1 are the same quantity. It usually has an uppercase letter and "b1" was probably a (harmless) error.

B1 in P-1, P+1 and ECM indicated that every prime power e <= B1 has been included in the computation of a^x where x = Product e. a is the initial value and arithmetic is performed in the appropriate ring.

I estimate that the probability pf finding a factor under 40 digits is below 1%, given the amount of computation already performed. I can't give a more precise estimate because I don't know how much work has been done.


Factoring a general 210-digit composite could be done by at most a few (<5) teams known to be currently active in the field. Finding out who those people are is left as a simple exercise in the use of Google or the search engine of your choice.

State of the art is <250 digits for a general composite. 1000 digits is likely to be inaccessible for a very long time unless there is a major breakthrough in theory. I have a bet open with RDS that 310 digits will be achievable before 2020. Even if I win the bet, I doubt I will collect much more than 2 years ahead of the deadline.
Before I go mathing (what ring besides the integers can they factor in)
let me computify: if I were given a large number in terms of its digits,
say what appears to be a 400-digit random decimal number, my first
attempt would be check the units digit for 0 or 2 or 4 or 6 or 8 or 5.
Then I would quickly check one-digit 3 and 7 to get 10-smooth.

Then because I'm not a computer and long division takes a bit longer,
I'd write an arbitrary precision integer decimal calculator to handle
the big number arithmetic (using Knuth), which I did a few years ago.

So I'd let it divide by the small primes.
My last version went as high as 10 billion, but of course slows down
when the highest TF factors exceed 2^32.

Not being familiar with ECM yet, I'd then turn to Mersenne forum
for the next suggested step in factoring Y400 (the given number).

What next?
davar55 is offline   Reply With Quote
Old 2011-01-22, 19:28   #8
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

3×3,529 Posts
Default

Quote:
Originally Posted by davar55 View Post
OK since I'm still catching up, a few more questions, if it's OK.

Is SNFS the Special Number Factor Sieve?
Is GNFS the General Number Factor Sieve?

What's special about those special numbers? Are they a^b +/- c ?

What's general about those general numbers? (I know there's
a long answer to that question, but I'd be glad for a good short one).

That's all I've got for now .....
Yesand yes to the first two, as long as you substitute "Field" for "Factor". Otherwise, no and no..

Numbers of the form a^b+/-c, where a, b and c are all small, are just a special case of special numbers.

They can (resp .can not) be represented by a polynomial with "small" coefficients. This last point is rather subtle and you should read up on the Number Field Sieve for what that statement actually means.


Paul
xilman is offline   Reply With Quote
Old 2011-01-22, 19:32   #9
davar55
 
davar55's Avatar
 
May 2004
New York City

23×232 Posts
Default

Quote:
Originally Posted by xilman View Post
Yesand yes to the first two, as long as you substitute "Field" for "Factor". Otherwise, no and no..

Numbers of the form a^b+/-c, where a, b and c are all small, are just a special case of special numbers.

They can (resp .can not) be represented by a polynomial with "small" coefficients. This last point is rather subtle and you should read up on the Number Field Sieve for what that statement actually means.
Do you really want me to google, wikipedia, or whatever else
to get info on Number Field Sieve (NFS)? No simple link right
here from this thread to keep things simple and organized?
davar55 is offline   Reply With Quote
Old 2011-01-22, 20:29   #10
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

245338 Posts
Default

Quote:
Originally Posted by davar55 View Post
Do you really want me to google, wikipedia, or whatever else
to get info on Number Field Sieve (NFS)? No simple link right
here from this thread to keep things simple and organized?
Yes, I really want you to get off your metaphorical backside and do some work for yourself instead of expecting me to spoon-feed you like a baby.

Paul

Last fiddled with by xilman on 2011-01-22 at 20:30
xilman is offline   Reply With Quote
Old 2011-01-22, 20:31   #11
davar55
 
davar55's Avatar
 
May 2004
New York City

23·232 Posts
Default

Quote:
Originally Posted by xilman View Post
Yes, I really want you to get off your metaphorical backside and do some work for yourself instead of expecting me to spoon-feed you like a baby.
Another insult echoing what I decided NOT to say to you.
davar55 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Extremely basic questions schwerlin Information & Answers 6 2015-01-20 19:26
The thread for mundane questions that Google fails at jasong jasong 9 2014-02-08 01:54
Basic ECM questions VictordeHolland Information & Answers 5 2013-09-04 01:47
Basic Question about ECM factoring? drake2 Math 1 2006-01-12 07:40
Questions on factoring koders333 Factoring 2 2005-09-20 14:25

All times are UTC. The time now is 01:59.

Thu Feb 25 01:59:53 UTC 2021 up 83 days, 22:11, 0 users, load averages: 2.67, 2.64, 2.73

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