mersenneforum.org SQRT Problem
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2006-07-19, 16:51 #1 R.D. Silverman     "Bob Silverman" Nov 2003 North of Boston 22×1,877 Posts 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
2006-07-19, 20:48   #2
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

101101100010102 Posts

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

2006-07-19, 21:43   #3
Wacky

Jun 2003
The Texas Hill Country

32·112 Posts

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

2006-07-19, 22:33   #4
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22×1,877 Posts

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.

2006-07-19, 22:39   #5
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

750810 Posts

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....

 2006-07-19, 23:30 #6 Patrick123     Jan 2006 JHB, South Africa 157 Posts 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
2006-07-19, 23:35   #7
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

2×3×29×67 Posts

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

2006-07-20, 00:42   #8
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

750810 Posts

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)

2006-07-20, 13:43   #9
Patrick123

Jan 2006
JHB, South Africa

15710 Posts

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

2006-07-20, 14:32   #10
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22×1,877 Posts
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
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

2006-07-20, 17:01   #11
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

2·3·29·67 Posts

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

 Similar Threads Thread Thread Starter Forum Replies Last Post henryzz Factoring 18 2010-09-26 00:55 tgrdy Msieve 6 2010-08-20 21:51 XYYXF Math 2 2007-12-08 12:31 hallstei Factoring 7 2007-05-01 12:51 Crook Math 3 2005-10-26 21:29

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

Fri Feb 3 07:01:55 UTC 2023 up 169 days, 4:30, 1 user, load averages: 1.13, 0.92, 0.86

Copyright ©2000 - 2023, 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.

โ  ยฑ โ รท ร ยท โ โ โฐ โ โ โ โ โ โค โฅ โฆ โง โจ โฉ โบ โป โผ โฝ โ โ โ โ ยฒ ยณ ยฐ
โ  โ ยฐ โ ~ โ โ โซ
โก โ โ โ โ โช โซ โโ โโ โ โ โ โ โง โจ โฉ โช โจ โ โ ๐ ๐ ๐ โฒ โณ
โ โ โ โฆ โฃ โฉ โช โ โ โ โ โ โ โ โ โ โ โ โ โ โ โค โ โ โ โต โถ โท โธ ๐
ยฌ โจ โง โ โ โ โ โ โ โ โ โ โด โต โค โฅ โข โจ โซค โฃ โฆ โฏ โฎ โฐ โฑ
โซ โฌ โญ โฎ โฏ โฐ โ โ ฮด โ โฑ โ โ
๐ข๐ผ ๐ฃ๐ฝ ๐ค๐พ ๐ฅ๐ฟ ๐ฆ๐๐ ๐ง๐ ๐จ๐ ๐ฉ๐๐ ๐ช๐ ๐ซ๐ ๐ฌ๐ ๐ญ๐ ๐ฎ๐ ๐ฏ๐ ๐ฐ๐ ๐ฑ๐ ๐ฒ๐ ๐ด๐๐ ๐ต๐ ๐ถ๐ ๐ท๐๐ ๐ธ๐ ๐น๐ ๐บ๐