mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Archived Projects > NFSNET Discussion

 
 
Thread Tools
Old 2006-07-19, 16:51   #1
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default SQRT Problem




The linear algebra for 2,1044+ finished, but the first 4 dependencies
all failed to compute the square root, so I stopped the code.

Note that I did not say "resulted in trivial factorization".

What I got each time was:

Wrong number of factors (1) for polynomial 2.
Dependency 1 -- Unable to take square roots


Everything seemed OK up to the final CRT construction. Then
the output started showing coefficients that were HUGE: much bigger
than the C153 being factored..

The Final gidwant values looked reasonable up to the end. Then I hit:

Starting Miscellaneous Lattice Ops
Start Final CRT Construction

The next lift that was shown showed:

Left = (C1 alpha^5 + C2 alpha^4 + ...)

where C1, C2, etc. were HUGE (much bigger than the number being factored)

It then showed gfactorization = (1 mod alpha^6 - alpha^3 + 1) X^2 +
[polynomial in alpha with huge coefficients] ) mod (alpha^6 - alpha^3 + 1)

I then got the "Wrong number of factors" error.

I suspect something is going wrong with Pari. I think it is hitting a
stacksize limit or some other limit.

Does anyone have their own windows executable that they could send
me so I could try a different executable? Tracking down this problem
will be a real pain, otherwise. I could try increasing some of the
defined constants in the Pari code, but I would be shooting in the dark.

Advice?

Has anyone seen this problem?

Bob
R.D. Silverman is offline  
Old 2006-07-19, 20:48   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

32×17×71 Posts
Default

Quote:
Originally Posted by R.D. Silverman



The linear algebra for 2,1044+ finished, but the first 4 dependencies
all failed to compute the square root, so I stopped the code.

Note that I did not say "resulted in trivial factorization".

What I got each time was:

Wrong number of factors (1) for polynomial 2.
Dependency 1 -- Unable to take square roots


Everything seemed OK up to the final CRT construction. Then
the output started showing coefficients that were HUGE: much bigger
than the C153 being factored..

The Final gidwant values looked reasonable up to the end. Then I hit:

Starting Miscellaneous Lattice Ops
Start Final CRT Construction

The next lift that was shown showed:

Left = (C1 alpha^5 + C2 alpha^4 + ...)

where C1, C2, etc. were HUGE (much bigger than the number being factored)

It then showed gfactorization = (1 mod alpha^6 - alpha^3 + 1) X^2 +
[polynomial in alpha with huge coefficients] ) mod (alpha^6 - alpha^3 + 1)

I then got the "Wrong number of factors" error.

I suspect something is going wrong with Pari. I think it is hitting a
stacksize limit or some other limit.

Does anyone have their own windows executable that they could send
me so I could try a different executable? Tracking down this problem
will be a real pain, otherwise. I could try increasing some of the
defined constants in the Pari code, but I would be shooting in the dark.

Advice?

Has anyone seen this problem?

Bob
Not seen the problem, neither can I help with a Windows executable.

What I can suggest is trying to use a Linux box (possibly from a bootable CD if you don't want to find a new machine or build a dual-boot machine) and then try using a recent CWI binary that I can supply (as I believe you already have permission to use the CWI toolkit.

Alternatively, if you can get the dependencies, relations and polynomial files to me (email me for postal address and send me a CD, or perhaps put the files on a mutually accessible machine) I can run the SQRT here.


Paul
xilman is offline  
Old 2006-07-19, 21:43   #3
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

32×112 Posts
Default

Quote:
Originally Posted by xilman
Not seen the problem, neither can I help with a Windows executable.

What I can suggest is trying to use a Linux box (possibly from a bootable CD if you don't want to find a new machine or build a dual-boot machine) and then try using a recent CWI binary that I can supply (as I believe you already have permission to use the CWI toolkit.

Alternatively, if you can get the dependencies, relations and polynomial files to me (email me for postal address and send me a CD, or perhaps put the files on a mutually accessible machine) I can run the SQRT here.


Paul
Bob,
I can only make a similar offer. I also have SQRT running on Mac OSX if that helps. Sorry that I cannot be more helpful.
Richard
Wacky is offline  
Old 2006-07-19, 22:33   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Default

Quote:
Originally Posted by xilman
Not seen the problem, neither can I help with a Windows executable.

What I can suggest is trying to use a Linux box (possibly from a bootable CD if you don't want to find a new machine or build a dual-boot machine) and then try using a recent CWI binary that I can supply (as I believe you already have permission to use the CWI toolkit.

Alternatively, if you can get the dependencies, relations and polynomial files to me (email me for postal address and send me a CD, or perhaps put the files on a mutually accessible machine) I can run the SQRT here.


Paul
I am going to try a few things first. I am waiting to see if CWI has
any ideas. Then I will try an older sqrt code. Then I will try
increasing some of the array sizes in size Pari and recompile.

If all else fails I will put the files on a couple of CD's and send them
by snail mail to you or Richard.
R.D. Silverman is offline  
Old 2006-07-19, 22:39   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by xilman
Not seen the problem, neither can I help with a Windows executable.

What I can suggest is trying to use a Linux box (possibly from a bootable CD if you don't want to find a new machine or build a dual-boot machine) and then try using a recent CWI binary that I can supply (as I believe you already have permission to use the CWI toolkit.

Alternatively, if you can get the dependencies, relations and polynomial files to me (email me for postal address and send me a CD, or perhaps put the files on a mutually accessible machine) I can run the SQRT here.


Paul
Might you have a binary for SUN or HPUX? We don't have Linux and
security restrictions keep me from modifying machines....
R.D. Silverman is offline  
Old 2006-07-19, 23:30   #6
Patrick123
 
Patrick123's Avatar
 
Jan 2006
JHB, South Africa

157 Posts
Default

I've zipped the executable with the accompanying dlls & library for version 2.2.11 built 20 Oct 2005 if it will help you. You can download it from http://www.onyxsa.co.za/PARI.zip
I did not compile it, but downloaded the Installation file from the Pari Website quite a while ago.

Regards
Patrick
Patrick123 is offline  
Old 2006-07-19, 23:35   #7
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

32×17×71 Posts
Default

Quote:
Originally Posted by R.D. Silverman
Might you have a binary for SUN or HPUX? We don't have Linux and
security restrictions keep me from modifying machines....
Not sure about Sparc Solaris, but probably can. Not tried to install Pari on one of those for several years. Good chance, anyway. HP-SUX is not possible as I don't have one of those.

If you have a personal X86-machine at home you could, presumably, boot that into Linux ...


Paul
xilman is offline  
Old 2006-07-20, 00:42   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Default

Quote:
Originally Posted by Patrick123
I've zipped the executable with the accompanying dlls & library for version 2.2.11 built 20 Oct 2005 if it will help you. You can download it from http://www.onyxsa.co.za/PARI.zip
I did not compile it, but downloaded the Installation file from the Pari Website quite a while ago.

Regards
Patrick
I don't need PARI. I have gp. I need the CWI sqrt code (which uses the
PARI libraries)
R.D. Silverman is offline  
Old 2006-07-20, 13:43   #9
Patrick123
 
Patrick123's Avatar
 
Jan 2006
JHB, South Africa

2358 Posts
Default

Quote:
Originally Posted by R.D. Silverman
I don't need PARI. I have gp. I need the CWI sqrt code (which uses the
PARI libraries)
My apologies. Sorry I cant help you further.

Regards
Patrick
Patrick123 is offline  
Old 2006-07-20, 14:32   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default 2,1044+

Quote:
Originally Posted by R.D. Silverman



The linear algebra for 2,1044+ finished, but the first 4 dependencies
all failed to compute the square root, so I stopped the code.

Note that I did not say "resulted in trivial factorization".

What I got each time was:

Wrong number of factors (1) for polynomial 2.
Dependency 1 -- Unable to take square roots


<snip>
With the vague hope that whatever was causing the bug might not apply
for all of the dependencies, I let the code run.........

It succeeded on the 14th try. Weird. :surprised

2,1044+ C153 = p56.p98

p56 = 25582121116971797723434440295709382794690160485178612721
R.D. Silverman is offline  
Old 2006-07-20, 17:01   #11
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

32×17×71 Posts
Default

Quote:
Originally Posted by R.D. Silverman
With the vague hope that whatever was causing the bug might not apply
for all of the dependencies, I let the code run.........

It succeeded on the 14th try. Weird. :surprised

2,1044+ C153 = p56.p98

p56 = 25582121116971797723434440295709382794690160485178612721
Ah. I wonder ...

Do the primes used for CRT reconstruction overlap with the primes appearing in relations? They shouldn't, obviously, but if they do you would find that a dependency not using any CRT primes would succeed but the others would fail.

I ran into something similar once when combining relations from Franke's lattice siever, which used large primes to 2^30, with CWI-generated relations which were limited to 10^9. The CWI sqrt code uses primes just larger than 10^9 for CRT purposes...


Paul
xilman is offline  
 

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
NFS sqrt by hand henryzz Factoring 18 2010-09-26 00:55
msieve C157 sqrt error: relation xxxx corrupt tgrdy Msieve 6 2010-08-20 21:51
127*Sqrt(62) XYYXF Math 2 2007-12-08 12:31
ggnfs sqrt problem hallstei Factoring 7 2007-05-01 12:51
P(n+1)<(sqrt(P(n))+1)^2 Crook Math 3 2005-10-26 21:29

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


Sat Sep 25 21:43:19 UTC 2021 up 64 days, 16:12, 0 users, load averages: 1.40, 1.29, 1.37

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.