SQRT Problem

[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

[xilman]

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

[Wacky]

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

[R.D. Silverman]

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]

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

[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

[xilman]

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

[R.D. Silverman]

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)

[Patrick123]

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

[R.D. Silverman]

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

[xilman]

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