mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2005-08-07, 19:02   #1
Washuu
 
Mar 2005
Poland

438 Posts
Default is GGNFS checking for SNFS number?

Hi, quick questions for those familiar with polynomial selection tool in new GGNFS suite:

let's assume we have a general number N, that can be represented as SNFS k*x^p+c (example: 3049*1067^37-12321) But, somehow, user forgot to check this.

Can "polyselect" or "pol51m0b" find suitable polynomial for SNFS case? If the answer is: "only by accident", or "only with very small coefficients k,c of k*x^p+c" can you try to precise the conditions?

Maybe we can write some tool to check if the general number N is close to some power, or it's multiple, in some range of k,x,p,c?

In fact, I wrote such a procedure and seems to work (p<1024,k<2^18), hovewer it's very rough and stupid and without any smart optimisations, so I'd prefer not to share it yet. But another questions arises: Which one of the parameters is most important? For now it's sorting results by ascending c, dropping results when c > 10^10.

Washuu
Washuu is offline   Reply With Quote
Old 2005-08-07, 20:37   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

25×7×11 Posts
Default

We've been thinking about something similar for GMP-ECM, so we can identify numbers suitable for George's DWT stage 1. I think writing numbers in base b, b=2,3,... might work.

After all, b^p = 100....00 in base b. Since c is likely going to be small, it will only affect the lowest couple of digits, and the multiplication by k will only affect the highest couple of digits.

So for b=2...(highest base you want to check), write N in base b (check Knuth vol.2 about how to do it quickly), see if there are a lot of zeros in the middle, if there are take the low non-zero digits as c, see how often you can divide b out of N-c to get p and take the remainder as k.

Alex

Edit: in fact, this is something that could go into phi.c. The code to tweak the poly coefficients should be general enough to handle non-unit k and c.
Edit2: this will only detect numbers with positive c. For negative c, look for a lot of b-1 digits in the middle. Neither will work if known factors have been divided out of N already.

Last fiddled with by akruppa on 2005-08-07 at 21:48
akruppa is offline   Reply With Quote
Old 2005-08-08, 06:16   #3
trilliwig
 
trilliwig's Avatar
 
Oct 2004
tropical Massachusetts

3×23 Posts
Exclamation

To Washuu's first question, the simple answer is "no". Or "only by accident". At least with "pol51m0b", it chooses non-monic linear polynomials which I do believe will eliminate any reasonable possibility of finding simple polynomials for numbers of this form. I can't really give a better answer than that; the polynomial selection programs in GGNFS were never intended to check for SNFS numbers.

Second, I don't even think such a program would solve a real problem.
Quote:
Originally Posted by Washuu
let's assume we have a general number N, that can be represented as SNFS k*x^p+c (example: 3049*1067^37-12321) But, somehow, user forgot to check this.
What conceivable circumstance could exist where the user would "forget"? If a user wants to factor a number, he or she should be intimately familiar with where it comes from! It's saner all around to write a program that parses "3049*1067^37-12321" as input and does the right thing automatically, than expecting the user to give the raw decimal expansion and expecting the program to figure out if a good SNFS polynomial exists for it.

Quote:
Originally Posted by akruppa
this will only detect numbers with positive c. For negative c, look for a lot of b-1 digits in the middle. Neither will work if known factors have been divided out of N already.
That will be a fatal deficiency. The proper input value of N requires that all known factors be divided out. If this program is to have any hope of guessing if SNFS is possible on a particular N, it would need the algebraic form in addition to N, and the most convenient method of input should already tell the program everything it needs to know.

--
Sam
trilliwig is offline   Reply With Quote
Old 2005-08-08, 11:59   #4
Washuu
 
Mar 2005
Poland

3510 Posts
Default

Quote:
Originally Posted by trilliwig
I don't even think such a program would solve a real problem.
What conceivable circumstance could exist where the user would "forget"? If a user wants to factor a number, he or she should be intimately familiar with where it comes from! It's saner all around to write a program that parses "3049*1067^37-12321" as input and does the right thing automatically, than expecting the user to give the raw decimal expansion and expecting the program to figure out if a good SNFS polynomial exists for it.
But there is always a chance (small, I know) that general number is close to some multiple of power of some number. Smart program could check this in seconds, and a prize (however not very likely) is pretty big: we can cut factorization time by 30%, I believe. And algorithm seems to be rather easy - why not to try?

And if you want an example: my friend started factoring the number he obtained from comps.gz, from Paul Leyland's website (Cullen and Woodall numbers). These numbers are remaining composites in general form. But some of the numbers can be factorised by SNFS, he just forgot to search the C&W tables for the number he chose. Sieving stage started over 48 hours ago, so it's not worth to start again with another poly, we both were just curious if the polm0b can find better polynomial than in usual case.

BTW: I was thinking also about writing small program for optimal chosing of polynomial for SNFS, when we know algebraic form of the number. It seems to be not very difficult, and could be helpful for beginners - not everyone can see good polynomial in the first sight...
What do you think?

Regards,

Washuu
Washuu is offline   Reply With Quote
Old 2005-08-08, 12:30   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Thumbs up

Quote:
Originally Posted by Washuu
But there is always a chance (small, I know) that general number is close to some multiple of power of some number. Smart program could check this in seconds, and a prize (however not very likely) is pretty big: we can cut factorization time by 30%, I believe. And algorithm seems to be rather easy - why not to try?

And if you want an example: my friend started factoring the number he obtained from comps.gz, from Paul Leyland's website (Cullen and Woodall numbers). These numbers are remaining composites in general form. But some of the numbers can be factorised by SNFS, he just forgot to search the C&W tables for the number he chose. Sieving stage started over 48 hours ago, so it's not worth to start again with another poly, we both were just curious if the polm0b can find better polynomial than in usual case.

BTW: I was thinking also about writing small program for optimal chosing of polynomial for SNFS, when we know algebraic form of the number. It seems to be not very difficult, and could be helpful for beginners - not everyone can see good polynomial in the first sight...
What do you think?

Regards,

Washuu

Define "close". What you suggest is certainly not trivial.

As for writing a program, I suspect you have not considered alll of
the ramifications. What polynomial would you choose for (say)
2, 1450L?
R.D. Silverman is offline   Reply With Quote
Old 2005-08-08, 17:28   #6
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2×3×1,699 Posts
Default

Quote:
Originally Posted by R.D. Silverman
Define "close". What you suggest is certainly not trivial.

As for writing a program, I suspect you have not considered alll of
the ramifications. What polynomial would you choose for (say)
2, 1450L?
Not trivial. put probably worth attempting, even if only as a learning exercise.

Even when one has considered all the ramifications, should that even be possible, one doesn't have to write a program that deals with every case. If 2,1450L turns out to be too hard, and I'm not claiming it is, a program that deals correctly with enough other interesting cases can still be very useful.

Some time ago I wrote a program to help maintain my factor tables. It deduces which table it may be processing by examining the first few lines of the table. It doesn't recognize all tables by any means, but because it recognizes Cunningham, BMtR, Cullen, Woodall, Generalized (Cullen&Woodall) and N!\pm1 I find it incredibly useful. Extending it to more cases will be straightforward if the need arises.

Rule of thumb: good may not be perfect, but can be useful.


Paul
xilman is offline   Reply With Quote
Old 2005-08-08, 18:30   #7
Washuu
 
Mar 2005
Poland

5·7 Posts
Default

Quote:
Originally Posted by R.D. Silverman
Define "close". What you suggest is certainly not trivial.

As for writing a program, I suspect you have not considered alll of
the ramifications. What polynomial would you choose for (say)
2, 1450L?
Hey, you are the master of poly selection! You tell me! :)

OK, seriously: I was only thinking about rather simple cases (at least in the beginning), for numbers like k*x^p+c. The program should make a few tests (about presence of Aurfeillian factors, for example), and try to compute some polynomials, and present the one with smallest coefficents. There are some tricks to do, and beginner not always can see it, and even more advanced (but still amateur) can miss, or simply miscalculate. (I can for sure).
Simple example from ggnfs doc: for N=16*10^143-1 obvious poly could be f(x)=4*x^5-25, but a slightly less obvious would be f(x)=x^5-200. Newbie can easily miss this, and amateur should check if his poly is good enough. (Experts can manage by themselves.) :)

As for program checking for "closeness" of N to some multiple of some power of some number :), I also would ask you about advice, what "closeness" condition should be. I thought about range of k,c<10^((logN)/10), so for n=10^120 cutoff point would be at 10^12.

For now, I have got mainly ideas, and want to listen what others are thinking and advicing. If someone wants to write such a program, you are very welcome, I am not good at it.

Washuu

Last fiddled with by Washuu on 2005-08-08 at 18:40
Washuu is offline   Reply With Quote
Old 2005-08-08, 20:19   #8
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

29×41 Posts
Default

Quote:
Originally Posted by Washuu
And if you want an example: my friend started factoring the number he obtained from comps.gz, from Paul Leyland's website (Cullen and Woodall numbers). These numbers are remaining composites in general form. But some of the numbers can be factorised by SNFS, he just forgot to search the C&W tables for the number he chose. Sieving stage started over 48 hours ago, so it's not worth to start again with another poly, we both were just curious if the polm0b can find better polynomial than in usual case.
I guess he is doing a General Cullen/Woodall numbers? What number is he doing? I've done all remaining with SNFS difficulty below 153 and currently doing the smallest available composite (c111) by GNFS. Planning to do a few more general numbers <115 digits so i would like to avoid duplication.
smh is offline   Reply With Quote
Old 2005-08-09, 00:09   #9
Washuu
 
Mar 2005
Poland

2316 Posts
Default

Quote:
Originally Posted by smh
I guess he is doing a General Cullen/Woodall numbers? What number is he doing? I've done all remaining with SNFS difficulty below 153 and currently doing the smallest available composite (c111) by GNFS. Planning to do a few more general numbers <115 digits so i would like to avoid duplication.
It was for sure >C115, something about C120, maybe C119 or C121, don't quite remember now, hovewer when we calculated the time we used approx. data for C120 (and calculated that whole factorization will take about 120 hrs, so 30% will be less than 48hrs, for his computer, so starting again won't be faster at this point). I will ask him tomorrow, and let you know in priv.

Washuu
Washuu is offline   Reply With Quote
Old 2005-08-09, 07:53   #10
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

29×41 Posts
Default

Quote:
It was for sure >C115, something about C120
Great. I plan to work my way up the smallest composites, so please let me know if you do anything < 115 digits
smh is offline   Reply With Quote
Old 2005-08-11, 05:09   #11
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13×89 Posts
Default

Is it possible to calculate a Murphy_E score for a SNFS polynomial and compare it to the score for a GNFS polynomial as given by pol51opt?
geoff is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
checking very large number for primality. WhoCares Math 51 2017-04-20 17:17
Round Off Checking and Sum (Inputs) Error Checking Forceman Software 2 2013-01-30 17:32
Number of relations from ggnfs Greebley Msieve 2 2012-03-05 21:56
SNFS basics (ggnfs + factLat) CRGreathouse Factoring 4 2009-05-25 08:05
checking smaller number fortega Data 2 2005-06-16 22:48

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

Fri Nov 27 09:43:33 UTC 2020 up 78 days, 6:54, 4 users, load averages: 0.94, 1.01, 1.06

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.